Finding Shortest Flip Sequences Between Connected Graph Partitions

Motivated by recent literature in computational political redistricting, we consider the problem of transforming one connected graph partition into another via a sequence of single-vertex transfers that maintain connected parts (i.e., flips). Given a vertex weight on the underlying graph, the weight of such a flip sequence is the sum of the weight-values transferred with each flip. To find a shortest (i.e., minimum-weight) flip sequence between two connected partitions, we design an A* search algorithm that uses the transfer distance to heuristically estimate the weight of a flip sequence needed to transform one connected partition into another (i.e., the flip distance). Although this A* algorithm is tractable for some instances, it is not for others; to provide insight into when A* may be tractable, we analyze the relationship between flip distance and transfer distance. Then we propose a heuristic that decomposes a given instance into several smaller instances. Computational experiments on complete graph and grid graph instances compare the performance of both algorithms; these experiments demonstrate that the heuristic is more consistently tractable than exact A* and can produce near-optimal flip sequences.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2024.0050.