Is this kind of "Gerrymandering" NP-complete?

Question

_{[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]}

---

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).

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?

Answer 1

Yes, this problem is NP-hard. Before we start, notice that it doesn't matter that we want a majority, instead the desired number of districts could be a part of the input. This is because somewhere neatly separated from the rest of the square/rectangle we could place many voters for ourselves with which we can claim any fixed amount of districts. Therefore, the problem I study also has a parameter $k$ which denotes the districts we need to win.

I will sketch a reduction from Planar Monotone 3-Sat problem, which was shown NP-complete in M. de Berg and A. Khosravi: Optimal binary space partitions for segments in the plane. Here the goal is to decide the satisfiability of a conjunctive normal form (CNF), where each clause contains at most 3 literals, all of which are either negated, or all unnegated, along with a planar embedding of the incidence structure in the following way:

• Each variable corresponds to an interval node in the horizontal line $y=0$; these intervals are pairwise disjoint.

• Each clause corresponds to an axis-parallel rectangle node; these rectangles are pairwise disjoint.

• If a clause contains only negated (resp. unnegated) variables, then its rectangle is entirely contained in the $y < 0$ (resp. $y > 0$) halfplane.

• Every rectangle is connected to (the intervals corresponding to) the variables contained in (the clause corresponding to) it by a vertical segment, which does not pass through any other rectangles.

To reduce one such instance, we will have to realize the embedding of the underlying graph. This is achieved as follows: For each node (variable or clause), we put about $n/2$ voters in its vicinity. The edges are drawn to be far enough from each other so as they don't interfere. An edge of length $L$ is divided into $L/n$ parts and $n/2$ voters alternate with $n/2$ non-voters. This will allow us to reach one node from another in an edge. Note that we can put each $n/2$ voters of the edge in a district each, so these won't influence the number of districts. Instead, we set the parameter $k$ such that we win if we can also include each $n/2$ voter group of the variable and clause nodes in a winning district.

In the variable nodes, we place the voters such that most of them are in the center (at $y=0$), and to make a winning district, we can either go upwards or downwards (but not both!) to collect all the voters there. This corresponds to the variable being false or true, respectively. E.g., if we go upwards, then all the voters in the vicinity of the variable node with $y>0$ will be used up in the variable district, but the ones for which $y<0$ remain free. These free voters can be grabbed through the edges by clause nodes with $y< 0$ that are connected to the variable. This is because the voters are placed in each edge at regular intervals that gives us some freedom.

This is the end of the sketch. Below is a very simple example of how this voter-grabbing is realized. Note that this is 1-dim instead of 2-dim. District boundaries are denoted by | while the (imaginary) node and edge boundaries are denoted by a comma. In this example the variable x was set to, say false (it went towards left), so the voter from its right could be grabbed by a clause.

|0100111|0010,111|1000111|1000111|1,000111|

variable x up to, edge can be this long, clause with x

Note that we didn't check many details, like whether we can ensure that all districts without a voter can have area exactly $n$ etc, but these should not pose a great issue, and the length of this answer is already significantly above a usual Mathoverflow post...

Answer 2

This is somewhat complementary to domotorp's existing answer, explaining the first paragraph in more detail.

Let's consider the tightest possible case, where $n = 2m - 1$ and there are $m^2$ A-squares and $n^2 - m^2$ B-squares. The problem is to partition the $n \times n$ grid into $n$ polyominoes of $n$ squares each, such that $m$ of the polyominoes each contain exactly $m$ A-squares and $m-1$ B-squares (and the other $m - 1$ polyominoes contain only B-squares).

Consider the following diagram, where $n = 69$ and $m = 35$:

The red triangle in the upper-left contains $m^2$ squares. The green triangle in the lower-right has the property that there's no polyomino of length $n$ which contains both red and green cells. This means that if the A-squares are entirely contained in the union of the red and green triangles, then they behave as 'disjoint' problems.

That is to say, if we have $m(m-k)$ A-squares in the upper-left (red) triangle and $mk$ A-squares in the lower-right (green) triangle, then solving the full problem is equivalent to covering the A-squares in the upper-left with $m - k$ polyominoes (each containing exactly $m$ of the A-squares) and covering the A-squares in the lower-right with $k$ polyominoes (each containing exactly $m$ of the A-squares).

We'll put the 'interesting' part of the problem entirely in the green lower-right triangle, and just use the upper-left triangle for storing extraneous A-squares.

The side-length of the red triangle is $\frac{1}{\sqrt{2}} n + O(1)$, so the side-length of the green triangle is $(1 - \frac{1}{\sqrt{2}}) n + O(1)$. When $n$ is sufficiently large, this is comfortably larger than $\frac{1}{4}n$. This contains a rectangle of size $a \times b$ provided $a + b \leq \frac{m}{2}$.

Consequently, it suffices to show that we can embed our favourite NP-complete problem as an instance of the following problem:

• We have an $a \times b$ rectangle and parameters $k, m$ where $m \geq 2(a + b)$.
• The top and left edges of the rectangle are 'open' and the bottom and right edges are 'closed'.
• There are $km$ squares marked 'A' inside this rectangle.
• The decision problem is to cover the 'A'-squares with $k$ polyominoes of size $2m - 1$, where each polyomino contains $m$ of those 'A'-squares, such that the remaining space is sufficiently connected that it can be covered with polyominoes of the correct size (which are allowed to escape out of the two 'open' edges of the rectangle).

The answer by domotorp gives one approach here. Another approach is to choose $k = 1$ and providing a reduction from the (NP-complete) rectilinear minimum Steiner tree problem. Here's an illustration of how you'd reduce rectilinear minimum Steiner tree to a gerrymandering problem:

We attach the chicane at the bottom to the lowermost point, solely with the purpose of ensuring that there are $m$ A-squares (shown in green) which need to be engulfed in a polyomino using at most $m - 1$ B-squares (shown in red). The chicane packs the desired number of A-squares into a region with side-length $O(\sqrt{m})$, sufficient to ensure that the problem comfortably fits into an $a \times b$ rectangle with $2(a + b) \leq m$.