Reconfiguration of Connected Graph Partitions via Recombination
share
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 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 Balanced Connected k-Partition with slack s, denoted (k,s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n_1,… , n_k with |n_i-n/k|≤ s, each of which induces a connected subgraph (when s=0, the k parts are perfectly balanced, and we call it k-BCP for short). A 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 s≥ 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 ≥ n/k, and (3) we provide negative instances for s ≤ n/(3k). (4) We show that the problem is PSPACE-complete when k ∈ O(n^ε) and s ∈ O(n^1-ε), for any constant 0 < ε≤ 1, even for restricted settings such as when G is an edge-maximal planar graph or when k=3 and G is planar.
READ FULL TEXT