NP-Hardness of Connected Components Reconfiguration under Component Jumping on Caterpillar Graphs

Abstract

We study the Connected Components Reconfiguration problem (CCR), in which connected components on a graph are transformed according to a specified reconfiguration rule. CCR generalizes Independent Set Reconfiguration by treating tokens not as individual vertices but as connected components of prescribed sizes. Among the variants of CCR, we focus on the component-jumping model, denoted by \CCRCJ. Nakahata.\ introduced this problem and showed that the decision problem for \CCRCJ~can be solved in $O(n^2)$ time on path graphs for arbitrary component sizes, and in polynomial time on chordal graphs when all connected components have the same size. However, the complexity on chordal graphs under a multiset size constraint remained open. In this paper, we study this multiset version of \CCRCJ~from both complexity-theoretic and algorithmic viewpoints. First, we prove that \CCRCJ~is NP-hard even on caterpillar graphs, which is a very restricted subclass of trees and chordal graphs minimally above path graphs. This result immediately implies NP-hardness for chordal graphs under a multiset size constraint, thereby resolving Nakahata's open problem on chordal graphs under multiset size constraints. Second, we revisit \CCRCJ~on path graphs. We improve the previous $O(n^2)$-time algorithm for the decision problem by giving an $O(n\log n)$-time decision algorithm. Moreover, when the instance has sufficiently large empty space, we show that there exists a reconfiguration sequence of length $O(n\log n)$, and such a sequence can be output efficiently.