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 $G$. A partition of $V(G)$ is emph{connected} 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 $s$. A emph{Balanced Connected $k$-Partition with slack $s$}, denoted emph{$(k,s)$-BCP}, is a partition of $V(G)$ into $k$ nonempty subsets, of sizes $n_1,ldots , n_k$ with $|n_i-n/k|leq s$, each of which induces a connected subgraph (when $s=0$, the $k$ parts are perfectly balanced, and we call it emph{$k$-BCP} for short). A emph{recombination} is an operation that takes a $(k,s)$-BCP of a graph $G$ and produces another by merging two adjacent subgraphs and repartitioning them. Given two $k$-BCPs, $A$ and $B$, of $G$ and a slack $sgeq 0$, we wish to determine whether there exists a sequence of recombinations that transform $A$ into $B$ via $(k,s)$-BCPs. We obtain four results related to this problem: (1) When $s$ is unbounded, the transformation is always possible using at most $6(k-1)$ recombinations. (2) If $G$ is Hamiltonian, the transformation is possible using $O(kn)$ recombinations for any $s ge n/k$, and (3) we provide negative instances for $s leq n/(3k)$. (4) We show that the problem is PSPACE-complete when $k in O(n^{varepsilon})$ and $s in O(n^{1-varepsilon})$, for any constant $0 < varepsilon le 1$, even for restricted settings such as when $G$ is an edge-maximal planar graph or when $k=3$ and $G$ is planar.