Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |