Finding Shortest Flip Sequences Between Connected Graph Partitions

Research story. The idea of finding a “path” between two district plans developed alongside the political redistricting compromise work in Dobbs et al. (2024a). After working with the transfer distance in Dobbs et al. (2024a) and reading about the existence of flip sequences on biconnected graphs in Akitaya et al. (2023), the authors were curious about the relationship between transfer distance and shortest flip sequences. The authors used this relationship to design two algorithms (one exact and one heuristic) that seek a shortest flip sequence between connected graph partitions.