Introduction

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.

Try It

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">Each vertex is <b style="color:#2b6cd4">blue</b> or <b style="color:#e07a1f">orange</b>. An edge is <b>cut</b> (bright) when its ends have different colors. Click a vertex to flip it and try to maximize the cut. Counting a cut is instant; finding the largest is the hard part.</p>
<svg id="g" viewBox="0 0 320 240" width="100%" height="240"></svg>
<div class="status" id="status">Cut: 0 edges</div>
<div class="btns">
  <button id="greedy" type="button">Greedy flip</button>
  <button id="brute" type="button">Brute force (best)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// MAX-CUT: color each vertex 0 or 1; an edge is "cut" when its endpoints differ.
// Counting the cut of a coloring is O(edges) — trivial. Finding the coloring that
// MAXIMIZES the cut is NP-hard (Karp, 1972). Here, greedy single-vertex flips can
// stall at a LOCAL maximum, while brute force checks all 2^n colorings for the true best.
const POS = [ [160,40],[60,110],[260,110],[110,200],[210,200] ];
const EDGES = [ [0,1],[0,2],[0,4],[1,2],[1,3],[2,3],[2,4] ];
const N = POS.length;
let color = new Array(N).fill(0); // start: all blue

function cutOf(col){ let c=0; for(const [a,b] of EDGES) if(col[a]!==col[b]) c++; return c; }

const svg = document.getElementById('g');
const SVGNS = 'http://www.w3.org/2000/svg';
function el(tag, attrs){ const e=document.createElementNS(SVGNS,tag);
  for(const k in attrs) e.setAttribute(k, attrs[k]); return e; }

function render(){
  svg.innerHTML='';
  for(const [a,b] of EDGES){
    const e=el('line',{ x1:POS[a][0], y1:POS[a][1], x2:POS[b][0], y2:POS[b][1] });
    e.setAttribute('class','edge'+(color[a]!==color[b]?' cut':''));
    svg.appendChild(e);
  }
  for(let i=0;i<N;i++){
    const c=el('circle',{ cx:POS[i][0], cy:POS[i][1], r:18 });
    c.setAttribute('class','node '+(color[i]?'B':'A'));
    c.addEventListener('click',()=>{ color[i]^=1; render(); });
    svg.appendChild(c);
    const t=el('text',{ x:POS[i][0], y:POS[i][1]+5, 'text-anchor':'middle' });
    t.setAttribute('class','nlabel'); t.textContent=i+1; svg.appendChild(t);
  }
  const cut=cutOf(color), max=EDGES.length;
  const s=document.getElementById('status');
  s.textContent=fmt('Cut: %cut% of %max% edges', { cut: cut, max: max });
  s.className='status'+(cut===bestCut?' ok':'');
}

// Precompute the true optimum once (so we can tell when the user/greedy reaches it).
let bestCut=0;
(function(){ for(let m=0;m<(1<<N);m++){ const col=[]; for(let i=0;i<N;i++) col.push((m>>i)&1);
  const c=cutOf(col); if(c>bestCut) bestCut=c; } })();

// Greedy: repeatedly flip any single vertex that strictly increases the cut. Stops
// at a local maximum — which may be below the global best.
function greedy(){
  let improved=true;
  while(improved){ improved=false;
    for(let i=0;i<N;i++){ const before=cutOf(color); color[i]^=1;
      if(cutOf(color)>before){ improved=true; } else { color[i]^=1; } }
  }
  render();
  const cur=cutOf(color);
  const s=document.getElementById('status');
  if(cur<bestCut) s.textContent=fmt('Greedy stuck at %cur% (a local max). Best possible is %bestCut%.', { cur: cur, bestCut: bestCut });
}

// Brute force: check all 2^n colorings, keep the best. Always finds the true optimum.
function brute(){
  let best=null, bc=-1, steps=0;
  for(let m=0;m<(1<<N);m++){ steps++; const col=[]; for(let i=0;i<N;i++) col.push((m>>i)&1);
    const c=cutOf(col); if(c>bc){ bc=c; best=col; } }
  color=best.slice(); render();
  const s=document.getElementById('status');
  s.textContent=fmt('Best cut %bc% of %length% found after %steps% colorings.', { bc: bc, length: EDGES.length, steps: steps });
  s.className='status ok';
}

document.getElementById('greedy').addEventListener('click',greedy);
document.getElementById('brute').addEventListener('click',brute);
document.getElementById('reset').addEventListener('click',()=>{ color=new Array(N).fill(0); render(); });
render();
Result
Console

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 2n2^{n} colorings to do it.

The Real Complexity

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 2n2^{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.

Where It Matters

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

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/max-cut/Content licensed under CC BY-NC 4.0.