Reconfiguring Multiple Connected Components with Size Multiset Constraints

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.