Gerrymandering

In 1812, Governor Elbridge Gerry of Massachusetts signed off on a district so contorted it looked like a salamander. A newspaper fused the two words — "gerrymander" — and the name stuck. Two centuries later the trick is the same: keep every vote exactly as it is, and just redraw the boundaries so your side wins more seats.

The arithmetic is brutally simple. Suppose a region splits 50/50 between two parties. Group your opponents tightly into a few districts they win in landslides ("packing"), and spread your own voters thinly so they win many districts by small margins ("cracking"). Not a single person changed their mind, yet the seat count can swing from a tie to a rout.

That raises a precise question for a computer: given the voters and where they live, does a map exist that gives my party a majority of seats? It turns out this is not just politically thorny — it is among the computationally hardest problems we know.

Below is a 5×5 grid of voters: each cell is blue or red. There are 13 blue and 12 red, so blue is the majority. The grid is carved into 5 districts of 5 cells each, and a district is won by whichever color holds the majority of its cells. Pick a preset and watch the seat totals.

<p class="hint">{{hint}}</p>
<div class="presets">
  <button data-map="0" type="button" class="active">{{btn_fair}}</button>
  <button data-map="1" type="button">{{btn_blue}}</button>
  <button data-map="2" type="button">{{btn_gerry}}</button>
</div>
<div id="grid" class="grid"></div>
<div class="tally">
  <div class="bar"><span id="seatBlue" class="seg seg-bl"></span><span id="seatRed" class="seg seg-rd"></span></div>
  <div id="score" class="score"></div>
</div>
<div id="note" class="note"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.bl { color: #2a6fdb; } .rd { color: #d23b4e; }
.presets { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
.presets button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
  background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
.presets button.active { background: #1d3557; color: #fff; }
.grid { display: grid; grid-template-columns: repeat(5, 52px); grid-template-rows: repeat(5, 52px);
  gap: 0; width: max-content; margin: 0 auto; }
.cell { width: 52px; height: 52px; display: flex; align-items: center; justify-content: center;
  font: 700 16px ui-monospace, monospace; color: rgba(255,255,255,.9); position: relative; }
.cell.b { background: #4a86e8; } .cell.r { background: #e8616f; }
/* {{c_borders}} */
.cell.t { border-top: 3px solid #16233a; } .cell.l { border-left: 3px solid #16233a; }
.cell.rt { border-right: 3px solid #16233a; } .cell.bm { border-bottom: 3px solid #16233a; }
.tally { margin: .9rem auto 0; max-width: 320px; }
.bar { display: flex; height: 26px; border-radius: 6px; overflow: hidden; border: 1px solid #cdd9e3; }
.seg { display: flex; align-items: center; justify-content: center; color: #fff; font: 700 13px system-ui; transition: flex-grow .35s; }
.seg-bl { background: #2a6fdb; } .seg-rd { background: #d23b4e; }
.score { text-align: center; font: 700 1.05rem system-ui; margin-top: .5rem; }
.note { text-align: center; font-size: .9rem; color: #555; margin-top: .5rem; min-height: 2.8em; line-height: 1.4; }

// Code not found

The votes never change — only the district borders do. A fair map turns blue's narrow voter majority into a 3–2 seat majority; one map stretches it to 4–1; and a gerrymander hands the minority red voters 3 of 5 seats. That swing is the whole game. Checking a finished map is instant: count colors per district. Finding a map that hits a target seat count, while keeping districts equal-sized and connected, is the hard part — and the number of possible maps explodes far faster than any computer can enumerate.

How hard is it to draw the best map? Not for a few cells — at the scale of real states.

• Checking a proposed map is trivial: count the voters of each color in each district and tally the seats.
• Brute force would enumerate every legal partition of the precincts into equal, connected districts. The number of such partitions grows super-exponentially; even a modest state has astronomically many.
• It's NP-hard. Formulating "is there a districting that wins party A at least k seats, with districts of equal population and connected on the precinct map?" is an optimization problem that has been proven NP-hard. The connectivity-and-balance constraints let you encode classic hard problems (graph partition, set-packing-style choices) directly into the map.
• So even deciding whether a target outcome is achievable sits with the SAT-and-friends NP-complete family — and finding the optimal map is at least as hard.

That is the uncomfortable punchline: there is no known efficient algorithm that, in general, finds the map maximizing one party's seats — and unless P vs NP is resolved in the surprising direction, there may be none. Mapmakers don't search all maps; they use heuristics, and so do the courts and watchdogs trying to catch them.

"Cut this network into balanced, connected pieces to hit some objective" is a shape that shows up far beyond elections:

• Fair redistricting: because finding the optimal map is intractable, analysts generate huge ensembles of random valid maps (via Markov-chain sampling) and flag an enacted map as a likely gerrymander if its outcome is an outlier.
• Courtroom evidence: these sampled ensembles have been used in real redistricting lawsuits to argue a map is statistically extreme.
• Graph partitioning: splitting a circuit, a social network, or a dataset into balanced clusters with few cross-links is the same NP-hard partition core.
• Logistics and territories: dividing a sales region or delivery zones into balanced, contiguous areas is districting by another name.

Understand why fair maps are hard to find and you've met constrained graph partitioning — the same intractable core behind graph coloring and countless balance-and-connect problems.

Gerrymandering is a vivid reminder that how you slice the data can matter as much as the data itself. The same voters, untouched, can deliver a landslide or a defeat depending only on where the lines fall — and deciding whether a winning map exists is NP-hard.

That hardness cuts both ways. It is why a determined mapmaker can hide an unfair plan among millions of plausible ones, and why reformers fight back not by computing the one fair map — that is intractable — but by sampling the space and spotting the outliers. Behind a salamander-shaped district lies P vs NP, quietly shaping who gets to govern.