Reconfiguration of connected graph partitions |
| |
Authors: | Hugo A Akitaya Matthew D Jones Matias Korman Oliver Korten Christopher Meierfrankenfeld Michael J Munje Diane L Souvaine Michael Thramann Csaba D Tóth |
| |
Institution: | 1. Department of Computer Science, University of Massachusetts Lowell, Lowell, Massachusetts, USA;2. Khoury College of Computer Sciences, Northeastern University, Boston, Massachusetts, USA;3. Siemens Electronic Design Automation, Wilsonville, Oregon, USA;4. Department of Computer Science, Columbia University, New York, New York, USA;5. Department of Computer Science, Tufts University, Medford, Massachusetts, USA;6. Department of Computer Science, California State University Northridge, Los Angeles, California, USA |
| |
Abstract: | Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph and an integer , a -district map of is a partition of into nonempty subsets, called districts, each of which induces a connected subgraph of . A switch is an operation that modifies a -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 -district maps of a graph 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 PSPACE-complete to decide whether there exists a sequence of 1-switches that takes a given -district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial lengths is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that take a given -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. |
| |
Keywords: | gerrymandering graph algorithms reconfiguration algorithms |
|
|