Adversarial Configurations for the ReCom Transition Function
This work identifies a worst-case exponential runtime for a widely used redistricting algorithm, highlighting a fundamental limitation for practitioners relying on ReCom.
The paper shows that the ReCom algorithm for sampling balanced graph partitions requires an exponentially large expected number of steps to re-split a specific family of 3-partitions on planar square grid graphs, proving it does not run in polynomial time in the worst case.
ReCom is a leading Markov Chain Monte Carlo algorithm for sampling balanced graph partitions in computational redistricting. At each step, its transition function proposes a new partition by merging two adjacent districts and if possible re-splitting the conjoined region. The transition function is efficient in practice, however, it is unknown whether it is guaranteed to run in polynomial time. In this report we exhibit an explicit family of 3-partitions on planar square grid graphs from which ReCom requires an exponentially large expected number of steps to re-split the graph (even if we admit approximately balanced splits), showing that in the worst case ReCom does not run in polynomial time. Notably, this result implies that ReCom is not technically rapidly mixing (if started from an adversarial configuration, ReCom requires exponential many steps to reach the stationary distribution).