Karger's Min-Cut

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.

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">{{hint}}</p>
<svg id="canvas" viewBox="0 0 320 200" class="canvas"></svg>
<div class="status" id="status">{{ready_status}}</div>
<div class="readout">
  <span>{{best_cut_label}}: <b id="best">—</b></span>
  <span>{{true_min_label}}: <b>2</b></span>
</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="trials" type="button">{{btn_trials}}</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 .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; }

// Code not found

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.

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(n^{2})$ time on an n-node graph.
• A single run succeeds with probability ≥ 2/$n^{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/$n^{2}$ — small, but not zero.
• Repetition turns luck into certainty. Run the whole thing $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(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.

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.

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-$n^{2}$ long shot into a guarantee, one cheap roll of the dice at a time.