Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" for one of two parties. The task is to divide the set of squares into $n$ subsets of the same size $n$ such that one of the parties, say $1$, has the majority in more than half of the regions - if that's possible at all. The main geometrical restriction is that each region has to be connected in the sense that two squares are connected if they share a whole edge (and not only a corner).

example picture

I wrote a backtracking algorithm to solve this problem which essentially tries all possible ways of assigning connected regions. It works, but it of course gets much slower as $n$ increases. I was wondering if this problem (or some variant of it) might be NP-complete. I would think, though, that to be able to find a polynomial-time reduction of a known NP-complete problem to this one, this problem has to be a bit more general. Obviously, there are various ways to generalize it:

  • In its easiest form, the above only works for odd $n$ as for even $n$ there's the chance of a draw. But one could of course also allow draws and stipulate that, say, you've "won" in a $6\times6$ matrix if you can find three regions with a draw and two where your party wins.
  • One could require that you have to win by a certain margin: $1$ needs to win at least $k$ more regions than $0$.
  • The matrix doesn't have to be a square matrix.
  • The regions don't have to have the exact same size.
  • More than two parties...

I would want to keep the connectedness restriction, though.

I searched the web to find similar problems but wasn't really successful; maybe I didn't use the right words. I found some results about the math of Gerrymandering, but they are about different (and more complicated) problems. I also tried to find known problems that are obviously related to this one, but so far to no avail. So my questions are:

  • Is this a known problem (maybe a game or puzzle)? And if so, what's its name?
  • If not, does this look similar to a known problem?
  • Any other hints where to look for more information?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.