Abstract | ||
---|---|---|
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $kgeq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is NP-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial length is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that takes a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors. |
Year | Venue | DocType |
---|---|---|
2019 | arXiv: Discrete Mathematics | Journal |
Volume | Citations | PageRank |
abs/1902.10765 | 0 | 0.34 |
References | Authors | |
13 | 8 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hugo A. Akitaya | 1 | 11 | 9.76 |
Matthew D. Jones | 2 | 0 | 0.34 |
Matias Korman | 3 | 178 | 37.28 |
Christopher Meierfrankenfeld | 4 | 0 | 0.34 |
Michael J. Munje | 5 | 0 | 0.34 |
Diane L. Souvaine | 6 | 480 | 77.99 |
Michael Thramann | 7 | 0 | 0.34 |
Csaba D. Tóth | 8 | 0 | 1.35 |