2025/05/12 by Yu Nakahata, Nakahata, Yu
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2505.07268
openalex publication_date 2025/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 M. ISR is a special case of CCR where 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 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.