Maximum Cut

Picture a room full of people, with a line drawn between every pair who can't stand each other. You want to split everyone into two teams so that as many of those rivalries as possible end up across the divide — each enemy pair pulled apart, on opposite sides.

Phrase it with dots and lines and you have a graph: vertices are people, edges are rivalries. Coloring each vertex one of two colors, an edge is "cut" when its endpoints get different colors. Maximum Cut asks for the coloring that cuts the most edges.

It sounds almost too simple to be interesting. Two colors, count the crossings — how hard could it be? The twist is that its mirror image, minimum cut, is genuinely easy, while maximum cut sits among the hardest problems we know.

Here is a small graph. Each vertex is blue or orange; an edge is cut (highlighted) when its two endpoints have different colors. Click any vertex to flip its color and try to maximize the number of cut edges.

<p class="hint">{{hint}}</p>
<svg id="g" viewBox="0 0 320 240" width="100%" height="240"></svg>
<div class="status" id="status">{{cut_zero}}</div>
<div class="btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="brute" type="button">{{btn_brute}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</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 .6rem; line-height: 1.45; }
svg { background: #f4f6f9; border-radius: 10px; display: block; touch-action: manipulation; }
.edge { stroke: #c2cad3; stroke-width: 3; }
.edge.cut { stroke: #0a7d33; stroke-width: 4; }
.node { cursor: pointer; stroke: #14304f; stroke-width: 2; }
.node.A { fill: #2b6cd4; }
.node.B { fill: #e07a1f; }
.nlabel { font: 700 13px system-ui, sans-serif; fill: #fff; pointer-events: none; }
.status { font-size: 1.05rem; font-weight: 700; margin: .6rem 0; min-height: 1.4em; color: #14304f; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Counting the cut for a given coloring is instant — just walk every edge once. Finding the coloring with the largest cut is the hard part. Use Greedy flip to repeatedly move any single vertex that improves the cut: it climbs fast but can get stuck in a local maximum. Only Brute force guarantees the true best, and it checks all $2^{n}$ colorings to do it.

Here is the part that surprises people. The opposite question — minimum cut, splitting the graph to cut as few edges as possible between two chosen points — is easy. It sits in P, solvable in polynomial time through the celebrated max-flow min-cut theorem. So flipping "few" to "many" should be a small change, right?

It is not.

• Checking is trivial: given a coloring, count the cut edges in one pass.
• Maximum Cut is NP-hard. It was one of Richard Karp's original 21 NP-complete problems in 1972. There is no known polynomial algorithm, and finding one would settle P vs NP.
• Brute force tries all $2^{n}$ ways to two-color the vertices — fine for a toy graph, hopeless past a few dozen vertices.
• Greedy local search is fast and often good, but it can freeze in a local maximum where no single flip helps yet the global best is higher.
• The 0.878 guarantee. In 1995 Michel Goemans and David Williamson found a breakthrough: using semidefinite programming plus a clever random rounding, they get a cut at least 0.878 times the optimum — provably. Under the Unique Games Conjecture, that constant is the best any efficient algorithm can promise.

So Maximum Cut draws a crisp line: the same graph, the same two colors, but "minimize" lands in P while "maximize" lands among the hardest problems we have. Like SAT and graph coloring, it is a place where checking is cheap and solving is not.

"Split things into two groups to maximize the tension across the divide" turns out to describe a remarkable number of real systems:

• Chip design (VLSI): routing wires across two layers so that the number of crossings between layers is balanced is a max-cut problem in disguise.
• Statistical physics: finding the lowest-energy state of an Ising spin glass — magnets that each want to disagree with their neighbors — is exactly max cut. Physics and complexity meet on the same graph.
• Data clustering: separating items into two groups to maximize the dissimilarity between groups is a max-cut cut on a similarity graph.
• Quantum computing: max cut is the headline benchmark for the Quantum Approximate Optimization Algorithm (QAOA) — the textbook problem people use to test whether quantum hardware can beat classical optimizers.

Solve max cut well and you have touched circuit layout, condensed-matter physics, and the leading edge of quantum simulation all at once.

Maximum Cut is a lesson in how thin the line between easy and hard can be. Keep everything the same — a graph, two colors, edges crossing the divide — and only swap minimize for maximize, and you fall off the cliff from polynomial-time P into NP-hard.

But it is also a hopeful story. We may never solve max cut exactly at scale, yet Goemans and Williamson showed we can get provably within 87.8% of perfect, fast. When you can't conquer a hard problem, you can often still tame it — and that art of approximation, born here, now reaches from P vs NP to the quantum machines being built today.