Reconfiguration of connected graph partitions via recombination

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph . A partition of is if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack . A , denoted , is a partition of into nonempty subsets, of sizes with , each of which induces a connected subgraph (when , the parts are perfectly balanced, and we call it for short).A is an operation that takes a -BCP of a graph and produces another by merging two adjacent subgraphs and repartitioning them. Given two -BCPs, and , of and a slack , we wish to determine whether there exists a sequence of recombinations that transform into via -BCPs. We obtain four results related to this problem: (1) When is unbounded, the transformation is always possible using at most recombinations. (2) If is Hamiltonian, the transformation is possible using recombinations for any , (3) there exist negative instances for , and (4) we show that determining whether a sequence of recombination that connects two -BCP of a graph exists is PSPACE-complete when and , for any constant . This statement holds even for restricted settings such as when is an edge-maximal planar graph or when and is planar.