Reconfiguration of connected graph partitions

DOI10.1002/JGT.22856MaRDI QIDQ6093138zbMATH OpenOpenAlexFDO

Authors Hugo A. Akitaya, Matthew Jones, Matias Korman, Oliver Korten, Diane L. Souvaine, Csaba D. Tóth

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10765

zbMATH Keywords

gerrymanderinggraph algorithmsreconfiguration algorithms

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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 $kgeq1$, 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.

Recommendations

• Reconfiguration of connected graph partitions via recombination
• The complexity of gerrymandering over graphs: paths and trees
• Algorithms for gerrymandering over graphs
• Optimal partisan districting on planar geographies
• Priced gerrymandering

Cites work

• A computational approach to unbiased districting
• A linear-time algorithm for the feasibility of pebble motion on trees
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation and hardness of token swapping
• Automated Redistricting Simulation Using Markov Chain Monte Carlo
• Balanced connected partitioning of unweighted grid graphs
• Bicolored graph partitioning, or: gerrymandering at its worst
• Colored pebble motion on graphs
• Complexity of token swapping and its variants
• Connectivity preserving transformations for higher dimensional binary images
• Distributed Evolutionary Graph Partitioning
• Fair redistricting is hard
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• Graph puzzles, homotopy, and the alternating group
• Linear-time algorithm for sliding tokens on trees
• Local search algorithms for political districting
• Multi-agent pathfinding with \(n\) agents on graphs with \(n\) vertices: combinatorial classification and tight algorithmic bounds
• Multi-color pebble motion on graphs
• On the complexity of partitioning graphs into connected subgraphs
• On-Line Planarity Testing
• Optimal partisan districting on planar geographies
• Optimal redistricting under geographical constraints: why ``pack and crack does not work
• Political districting: from classical models to recent approaches
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Pushing squares around
• Swapping colored tokens on graphs
• Swapping labeled tokens on graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The connectivity of token graphs
• Token graphs
• Token sliding on chordal graphs
• Weighted Voronoi region algorithms for political districting

Cited in

(7)

• Reconfiguration on nowhere dense graph classes
• Reconfiguration of graphs with connectivity constraints
• Reconfigurations in Graphs and Grids
• Reconfiguration of connected graph partitions via recombination
• ZDD-based algorithmic framework for solving shortest reconfiguration problems
• Irreducibility of recombination Markov chains in the triangular lattice
• Perfect hierarchical matchings in graphs

This page was built for publication: Reconfiguration of connected graph partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093138)