Introduction

Picture a network — friends in a social graph, routers on the internet, cities joined by roads. A natural question: what is the fewest number of links you could cut to split it into two disconnected pieces? That smallest seam is the global minimum cut, and it tells you exactly where the network is most fragile.

The obvious ways to find it are heavy machinery: run max-flow between every pair of nodes, or grind through clever combinatorics. They work, but they feel like overkill for such a simple question.

In 1993, David Karger proposed something almost absurd instead. Don't search at all. Just pick a random edge, glue its two endpoints together, and repeat until only two blobs remain. The links left between those two blobs are your guess at the cut. It sounds like it can't possibly work — and yet, repeated a modest number of times, it finds the true minimum cut with overwhelming probability.

Try It: Contract the Edges

Below is a small graph. Press Contract one edge to pick a random edge and merge its endpoints into a single supernode — any parallel edges that appear stay, but self-loops are thrown away. Keep going until only two supernodes are left: the edges between them are this trial's cut.

<p class="hint">This graph has two clusters joined by just a few links. Press <b>Contract one edge</b> to merge a random edge’s endpoints into one supernode. Keep going until only <b>two</b> supernodes remain — the edges between them are this trial’s cut. Then run many trials and watch the best cut find the true minimum.</p>
<svg id="canvas" viewBox="0 0 320 200" class="canvas"></svg>
<div class="status" id="status">Ready. 6 supernodes, 8 edges.</div>
<div class="readout">
  <span>Best cut found: <b id="best">—</b></span>
  <span>True min cut: <b>2</b></span>
</div>
<div class="btns">
  <button id="step" type="button">Contract one edge</button>
  <button id="trials" type="button">Run 200 trials</button>
  <button id="reset" type="button" class="ghost">Reset graph</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 .7rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 360px; height: 200px; background: #f3f6f9;
          border: 1px solid #cdd9e3; border-radius: 8px; display: block; }
.edge { stroke: #adb1b8; stroke-width: 2; }
.edge.cut { stroke: #e63946; stroke-width: 3; }
.node { fill: #1d3557; }
.node.super { fill: #457b9d; }
.label { fill: #fff; font: 700 11px ui-monospace, monospace; text-anchor: middle; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.readout { display: flex; gap: 1.4rem; font-size: .95rem; margin: .3rem 0 .6rem; }
.readout b { color: #1d3557; }
.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; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Karger’s algorithm: pick a random edge, contract (merge) its endpoints, discard self-loops, keep parallel edges. Repeat until 2 supernodes remain — the surviving edges between them are a cut. Any one run may overshoot; the BEST over many runs is the true global minimum cut with high probability (Karger, 1993).
const POS = [[60,45],[40,110],[80,165],[240,45],[280,110],[260,165]];
// Two triangles (clusters) bridged by exactly 2 edges -> true min cut = 2.
const BASE_EDGES = [[0,1],[1,2],[0,2],[3,4],[4,5],[3,5],[2,3],[0,5]];

let groups, edges, best = Infinity;

function fresh(){
  groups = POS.map((_,i)=>[i]);          // each supernode = list of original node ids
  edges = BASE_EDGES.map(e=>e.slice());  // multiset of edges between supernodes
}
function find(id){ return groups.findIndex(g=>g.includes(id)); }

// Contract a random surviving edge; returns false if fewer than 2 groups remain.
function contract(){
  const live = edges.filter(([a,b])=>find(a)!==find(b));
  if(groups.filter(g=>g.length).length<=2 || live.length===0) return false;
  const [a,b] = live[Math.floor(Math.random()*live.length)];
  const ga = find(a), gb = find(b);
  groups[ga] = groups[ga].concat(groups[gb]); // merge gb into ga
  groups[gb] = [];                              // gb now empty
  return true;
}
function liveGroups(){ return groups.map((g,i)=>i).filter(i=>groups[i].length); }
// Cut value = edges whose endpoints fall in different surviving supernodes.
function cutValue(){
  let c=0; for(const [a,b] of edges) if(find(a)!==find(b)) c++; return c;
}

function draw(){
  const svg=document.getElementById('canvas'); svg.innerHTML='';
  const lg=liveGroups();
  // representative original-node position per supernode = first member’s POS
  const rep=lg.map(i=>{ const m=groups[i][0]; return {gi:i, x:POS[m][0], y:POS[m][1]}; });
  const cut = lg.length===2;
  for(const [a,b] of edges){
    const ga=find(a), gb=find(b); if(ga===gb) continue;
    const pa=rep.find(r=>r.gi===ga), pb=rep.find(r=>r.gi===gb);
    const ln=document.createElementNS('http://www.w3.org/2000/svg','line');
    ln.setAttribute('x1',pa.x);ln.setAttribute('y1',pa.y);
    ln.setAttribute('x2',pb.x);ln.setAttribute('y2',pb.y);
    ln.setAttribute('class','edge'+(cut?' cut':''));
    svg.appendChild(ln);
  }
  for(const r of rep){
    const big=groups[r.gi].length>1;
    const c=document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',r.x);c.setAttribute('cy',r.y);c.setAttribute('r',big?15:11);
    c.setAttribute('class','node'+(big?' super':''));
    svg.appendChild(c);
    const t=document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',r.x);t.setAttribute('y',r.y+4);t.setAttribute('class','label');
    t.textContent=groups[r.gi].length;
    svg.appendChild(t);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function refreshBest(v){ if(v<best) best=v; document.getElementById('best').textContent=best===Infinity?'—':best; }

function onStep(){
  if(!contract()){ setStatus(fmt('Two supernodes left — this trial’s cut = %cutValue%.', { cutValue: cutValue() }),'ok');
    refreshBest(cutValue()); document.getElementById('step').disabled=true; draw(); return; }
  draw();
  const n=liveGroups().length;
  if(n===2){ const c=cutValue(); setStatus(fmt('Two supernodes left — this trial’s cut = %c%.', { c: c }),'ok');
    refreshBest(c); document.getElementById('step').disabled=true; }
  else setStatus(fmt('%n% supernodes remain. Keep contracting.', { n: n }),'');
}
// One full silent trial -> its cut value.
function oneTrial(){ fresh(); while(contract()){} return cutValue(); }
function onTrials(){
  let local=Infinity;
  for(let i=0;i<200;i++){ const c=oneTrial(); if(c<local) local=c; }
  refreshBest(local);
  fresh(); draw(); document.getElementById('step').disabled=false;
  setStatus(fmt('Ran 200 trials. Smallest cut seen = %local%.', { local: local }), local<=2?'ok':'');
  console.log('200 trials, best cut =', local);
}
function onReset(){ best=Infinity; document.getElementById('best').textContent='—';
  fresh(); draw(); document.getElementById('step').disabled=false; setStatus('Ready. 6 supernodes, 8 edges.',''); }

document.getElementById('step').addEventListener('click',onStep);
document.getElementById('trials').addEventListener('click',onTrials);
document.getElementById('reset').addEventListener('click',onReset);
fresh(); draw();
Result
Console

One run is just a roll of the dice — sometimes it nails the true minimum cut, sometimes it overshoots. Press Run 200 trials and watch the best cut found settle onto the real answer. That is the whole idea: a single attempt is unreliable, but the smallest result over many cheap attempts is almost surely correct. Compare this with the certainty-on-the-first-try world of P vs NP.

The Real Complexity

How can collapsing random edges possibly be reliable? The magic is in the probabilities.

  • One contraction phase is cheap. Repeatedly merging endpoints down to two supernodes takes O(n2)O(n^{2}) time on an n-node graph.
  • A single run succeeds with probability ≥ 2/n2n^{2}. The minimum cut survives only if you never once pick one of its few edges to contract. Because a min cut has so few edges relative to the whole graph, the chance of avoiding all of them the entire way is at least 2/n2n^{2} — small, but not zero.
  • Repetition turns luck into certainty. Run the whole thing O(n2log⁡n)O(n^{2} \log n) times and keep the best answer; the probability that every run misses the true min cut drops below any threshold you like. This makes it a Monte Carlo algorithm — always fast, occasionally wrong, but tunably so.
  • It can be made fast. In 1996 Karger and Stein sped this up to roughly O(n2log⁡3n)O(n^{2} \log ^{3} n) by recursing more carefully, since early contractions are far safer than late ones.

This is a different flavour of "hard" from the SAT-style problems. Min-cut is solvable in polynomial time — the surprise is not whether it can be solved, but that randomness gives the simplest, most elegant route to the answer.

Where It Matters

Finding where a graph is weakest is a question that hides inside many real systems:

  • Network reliability: the min cut counts the fewest links whose failure disconnects a network — a direct measure of how robust an internet backbone or power grid is.
  • Clustering and community detection: a small cut separates loosely connected groups, so min-cut ideas help split data into natural communities.
  • Image segmentation and vision: pixels become a graph, and cutting it along weak boundaries separates an object from its background.
  • Circuit and chip layout: partitioning components to minimize the wires crossing between blocks is a min-cut at heart, close cousin to graph coloring layout problems.

Beyond the cut itself, Karger's algorithm became a textbook landmark for randomized computation — proof that throwing dice, repeated cleverly, can beat painstaking deterministic search.

Conclusion

Karger's algorithm is a small miracle of computer science: to find the spot where a network would break, you don't analyze it — you gamble. Collapse random edges, end with two blobs, count the survivors, and repeat. Any one trial is a coin toss, but the best of many is almost certainly the true minimum cut.

The lesson outlives the problem. Long before quantum tricks or deep learning, Karger showed that controlled randomness can be not a last resort but the cleanest tool in the box — turning a one-in-n2n^{2} long shot into a guarantee, one cheap roll of the dice at a time.

Share this article

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

Comments

Loading comments...

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