Reconfiguration of Connected Graph Partitions

Understand

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\geq 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.