Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2501.14450 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929685739339776 |
|---|---|
| author | Suga, Tatsuhiro Suzuki, Akira Tamura, Yuma Zhou, Xiao |
| author_facet | Suga, Tatsuhiro Suzuki, Akira Tamura, Yuma Zhou, Xiao |
| contents | In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other, with the steps dictated by specific reconfiguration rules. Traditionally, most studies on reconfiguration problems have focused on rules that allow changing a single element at a time. In contrast, this paper considers scenarios in which $k \ge 2$ elements can be changed simultaneously. We investigate the general reconfiguration problem of isomorphisms. For the Induced Subgraph Isomorphism Reconfiguration problem, we show that the problem remains $\textsf{PSPACE}$-complete even under stringent constraints on the pattern graph when $k$ is constant. We then give two meta-theorems applicable when $k$ is slightly less than the number of vertices in the pattern graph. In addition, we investigate the complexity of the Independent Set Reconfiguration problem, which is a special case of the Induced Subgraph Isomorphism Reconfiguration problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14450 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules Suga, Tatsuhiro Suzuki, Akira Tamura, Yuma Zhou, Xiao Data Structures and Algorithms In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other, with the steps dictated by specific reconfiguration rules. Traditionally, most studies on reconfiguration problems have focused on rules that allow changing a single element at a time. In contrast, this paper considers scenarios in which $k \ge 2$ elements can be changed simultaneously. We investigate the general reconfiguration problem of isomorphisms. For the Induced Subgraph Isomorphism Reconfiguration problem, we show that the problem remains $\textsf{PSPACE}$-complete even under stringent constraints on the pattern graph when $k$ is constant. We then give two meta-theorems applicable when $k$ is slightly less than the number of vertices in the pattern graph. In addition, we investigate the complexity of the Independent Set Reconfiguration problem, which is a special case of the Induced Subgraph Isomorphism Reconfiguration problem. |
| title | Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.14450 |