Item

Abstract

Redistricting is the problem of dividing a state into a number $k$ of
regions, called districts. Voters in each district elect a representative. The
primary criteria are: each district is connected, district populations are
equal (or nearly equal), and districts are "compact". There are multiple
competing definitions of compactness, usually minimizing some quantity.
One measure that has been recently promoted by Duchin and others is number of
cut edges. In redistricting, one is given atomic regions out of which each
district must be built. The populations of the atomic regions are given.
Consider the graph with one vertex per atomic region (with weight equal to the
region's population) and an edge between atomic regions that share a boundary.
A districting plan is a partition of vertices into $k$ parts, each connnected,
of nearly equal weight. The districts are considered compact to the extent that
the plan minimizes the number of edges crossing between different parts.
Consider two problems: find the most compact districting plan, and sample
districting plans under a compactness constraint uniformly at random. Both
problems are NP-hard so we restrict the input graph to have branchwidth at most
$w$. (A planar graph's branchwidth is bounded by its diameter.) If both $k$ and
$w$ are bounded by constants, the problems are solvable in polynomial time.
Assume vertices have weight~1. One would like algorithms whose running times
are of the form $O(f(k,w) n^c)$ for some constant $c$ independent of $k$ and
$w$, in which case the problems are said to be fixed-parameter tractable with
respect to $k$ and $w$). We show that, under a complexity-theoretic assumption,
no such algorithms exist. However, we do give algorithms with running time
$O(c^wn^{k+1})$. Thus if the diameter of the graph is moderately small and the
number of districts is very small, our algorithm is useable.