[EM] solving the NP-hard problem? no. The CRV approach to gerrymandering.

[Warren Smith]

The "graph partitioning" problem is NP-complete:

problem ND14 in Garey & Johnson: Comnputers and Intractibility, a guide
to the theory of NP completeness, freeman 1978.

Thus even if the country is to be divided into only 2 districts we have NP-hardness.

It is conceivable this could be escaped because we have a planar graph not
a general graph.  A polynomial time algorithm to find
an APPROXIMATE grpah partitioning for a planr graph, is

T. N. Bui and A. Peck. Partitioning planar graphs. SIAM J. on Computing, 21(2):203-- 215, 1992.

But their algorithm is exponential time if you make the aprpoximation too good.
http://locus.siam.org/SICOMP/volume-21/art_0221016.html

See also even worse news showing APX-completeness
Chlebikova, J. (1996), 
``Approximability of the Maximally balanced connected partition problem in graphs'', 
Inform. Process. Lett. 60, 225-230. 

but again this is about general graphs.  For planar graphs it remains conceiveable
there is a polytime algorithm but I doubt it.  I think it will be shown NP-complete
some day, and I also think this is even more likely if the number of districts exceeds 2.
wds