Reconfiguring Multiple Connected Components with Size Multiset Constraints
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915283364478976 |
|---|---|
| author | Nakahata, Yu |
| author_facet | Nakahata, Yu |
| contents | We propose a novel generalization of Independent Set Reconfiguration (ISR): Connected Components Reconfiguration (CCR). In CCR, we are given a graph $G$, two vertex subsets $A$ and $B$, and a multiset $\mathcal{M}$ of positive integers. The question is whether $A$ and $B$ are reconfigurable under a certain rule, while ensuring that each vertex subset induces connected components whose sizes match the multiset $\mathcal{M}$. ISR is a special case of CCR where $\mathcal{M}$ only contains 1. We also propose new reconfiguration rules: component jumping (CJ) and component sliding (CS), which regard connected components as tokens. Since CCR generalizes ISR, the problem is PSPACE-complete. In contrast, we show three positive results: First, CCR-CS and CCR-CJ are solvable in linear and quadratic time, respectively, when $G$ is a path. Second, we show that CCR-CS is solvable in linear time for cographs. Third, when $\mathcal{M}$ contains only the same elements (i.e., all connected components have the same size), we show that CCR-CJ is solvable in linear time if $G$ is chordal. The second and third results generalize known results for ISR and exhibit an interesting difference between the reconfiguration rules. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07268 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reconfiguring Multiple Connected Components with Size Multiset Constraints Nakahata, Yu Data Structures and Algorithms We propose a novel generalization of Independent Set Reconfiguration (ISR): Connected Components Reconfiguration (CCR). In CCR, we are given a graph $G$, two vertex subsets $A$ and $B$, and a multiset $\mathcal{M}$ of positive integers. The question is whether $A$ and $B$ are reconfigurable under a certain rule, while ensuring that each vertex subset induces connected components whose sizes match the multiset $\mathcal{M}$. ISR is a special case of CCR where $\mathcal{M}$ only contains 1. We also propose new reconfiguration rules: component jumping (CJ) and component sliding (CS), which regard connected components as tokens. Since CCR generalizes ISR, the problem is PSPACE-complete. In contrast, we show three positive results: First, CCR-CS and CCR-CJ are solvable in linear and quadratic time, respectively, when $G$ is a path. Second, we show that CCR-CS is solvable in linear time for cographs. Third, when $\mathcal{M}$ contains only the same elements (i.e., all connected components have the same size), we show that CCR-CJ is solvable in linear time if $G$ is chordal. The second and third results generalize known results for ISR and exhibit an interesting difference between the reconfiguration rules. |
| title | Reconfiguring Multiple Connected Components with Size Multiset Constraints |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.07268 |