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

[Paul Kislanko]

Warren Smith wrote in part: 

> The "graph partitioning" problem is NP-complete:

I didn't express myself very well. Yes, the "graph-partitioning problem" is
NP-complete, but my suggestion was that we didn't need the full power of
that result. Instead we could reformulate the problem into a disection form
(which as Adam Tarr has since pointed had already been suggested) and THAT
class of problems is entirely P.

Just remove the "minimize strength of broken connections" requirement and
substitute "build up 'molecules' from the 'most connected' atoms that do not
violate the population maximum criterion' and then accept ANY solution that
cuts the entire state into N connected districts that all have about the
same population." 

Techniques to do this in P-time are widely used (OK, I've used 'em to
classify sports schedules. If they're not widely used it is not my fault).