We study the computational complexity of the map redistricting problem
(gerrymandering). Mathematically, the electoral district designer
(gerrymanderer) attempts to partition a weighted graph into $k$ connected
components (districts) such that its candidate (party) wins as many districts
as possible. Prior work has principally concerned the special cases where the
graph is a path or a tree. Our focus concerns the realistic case where the
graph is planar. We prove that the gerrymandering problem is solvable in
polynomial time in $\lambda$-outerplanar graphs, when the number of candidates
and $\lambda$ are constants and the vertex weights (voting weights) are
polynomially bounded. In contrast, the problem is NP-complete in general planar
graphs even with just two candidates. This motivates the study of approximation
algorithms for gerrymandering planar graphs. However, when the number of
candidates is large, we prove it is hard to distinguish between instances where
the gerrymanderer cannot win a single district and instances where the
gerrymanderer can win at least one district. This immediately implies that the
redistricting problem is inapproximable in polynomial time in planar graphs,
unless P=NP. This conclusion appears terminal for the design of good
approximation algorithms -- but it is not. The inapproximability bound can be
circumvented as it only applies when the maximum number of districts the
gerrymanderer can win is extremely small, say one. Indeed, for a fixed number
of candidates, our main result is that there is a constant factor approximation
algorithm for redistricting unweighted planar graphs, provided the optimal
value is a large enough constant.

计算复杂性、选区分割、地图重新划分问题、平面图和逼近算法。