Premium
Reconfiguration of connected graph partitions
Author(s) -
Akitaya Hugo A.,
Jones Matthew D.,
Korman Matias,
Korten Oliver,
Meierfrankenfeld Christopher,
Munje Michael J.,
Souvaine Diane L.,
Thramann Michael,
Tóth Csaba D.
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22856
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , sequence (biology) , social connectedness , discrete mathematics , control reconfiguration , time complexity , partition (number theory) , computer science , psychology , genetics , psychotherapist , biology , embedded system
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 k ≥ 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 PSPACE‐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 lengths is known to exist). We also present efficient algorithms for computing a sequence of 1‐switches that take 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.