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