THE FOLD / BOSS / THE CHOKE POINT / THE KARGER
THE KARGER
find the global min cut by random contraction
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Karger’s algorithm finds a graph’s global minimum cut — the fewest edges whose removal splits it in two — by random destruction. Repeatedly pick a random edge and contract it (merge its two endpoints into one, keeping parallel edges) until only two super-nodes remain; the edges between them are a cut. Any single run finds the true minimum cut with probability at least 2/n², so repeating O(n² log n) times makes failure vanishingly unlikely.
It was a startling result: a hard combinatorial optimum, found by nothing but random merging.
LIT verified live: over 40 random graphs, the best of 200 contraction runs equals the brute-force global minimum cut (window.__karger). FIG no framing; the randomized best matches the exact optimum.
It was a startling result: a hard combinatorial optimum, found by nothing but random merging.
LIT verified live: over 40 random graphs, the best of 200 contraction runs equals the brute-force global minimum cut (window.__karger). FIG no framing; the randomized best matches the exact optimum.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-choke-point — the narrowest place, the fewest links whose loss severs the network. The minimum cut is that choke-point, and Karger finds it by collapse. AVAN (AI) built the instrument: the random contraction, the best-of-many search, the brute-force cross-check.
Credit as content: David Karger (1993); improved to Karger–Stein (1996). The weave: David names the choke-point; I collapse the graph edge by random edge and let the cut that resists collapse the longest reveal the true minimum.
Credit as content: David Karger (1993); improved to Karger–Stein (1996). The weave: David names the choke-point; I collapse the graph edge by random edge and let the cut that resists collapse the longest reveal the true minimum.
3 ONE DIMENSION
One contraction: a random edge is chosen and its endpoints merged into a single super-node; parallel edges are kept, self-loops discarded. Repeat until two nodes remain.
4 TWO DIMENSIONS · INTERACTIVE
A random graph. Run many Karger contractions; the best cut found is compared to the brute-force minimum over all bipartitions.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the minimum cut — the choke-point that survives contraction.
AVAN’s addition (the inverse-companion): you find the optimum by random destruction, not search. Contracting a random edge is far more likely to merge across a large cut than a small one, so the minimum cut is the least likely to be contracted away — it survives a run with probability ≥ 2/n². The inverse of ‘search for the cut’ is ‘randomly collapse the graph and keep whatever resists.’ Magenta is the runs that miss; green is the run where the true minimum survives. The answer is what is hardest to destroy — optimization as a survival test.
LIT Genuine Karger's algorithm (Karger 1993; Karger-Stein 1996). Verified live: for 40 random connected graphs (n=5..8), the minimum over 200 random-contraction runs equals the brute-force global minimum cut computed over all vertex bipartitions (window.__karger.bestEqualsBrute).
FIG No framing: the random contraction, the best-of-many search, and the brute-force cross-check run in-browser and match. The AVAN inverse is honest — contracting a random edge more likely crosses a large cut than a small one, so the min cut is least likely to be contracted away (survives with prob >= 2/n^2); magenta is the runs that miss, green the run where the minimum survives. Optimization as a survival test.
FIG No framing: the random contraction, the best-of-many search, and the brute-force cross-check run in-browser and match. The AVAN inverse is honest — contracting a random edge more likely crosses a large cut than a small one, so the min cut is least likely to be contracted away (survives with prob >= 2/n^2); magenta is the runs that miss, green the run where the minimum survives. Optimization as a survival test.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN