THE FOLD / BOSS / THE RAID / THE STOER-WAGNER
THE STOER-WAGNER
the global min cut, deterministically, no source/sink
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Stoer–Wagner algorithm finds a graph’s global minimum cut — the lightest set of edges whose removal splits it — deterministically, without max-flow and without fixing a source and sink. Each phase does a maximum-adjacency ordering (repeatedly add the vertex most tightly connected to those already chosen); the last vertex’s connection weight is a valid cut, and merging the last two vertices and repeating sweeps every pair in n−1 phases.
LIT verified live: over 80 random weighted graphs the Stoer–Wagner cut equals the brute-force minimum over all vertex bipartitions (window.__stoerwagner). FIG no framing; exact global minimum, no randomness (unlike Karger).
LIT verified live: over 80 random weighted graphs the Stoer–Wagner cut equals the brute-force minimum over all vertex bipartitions (window.__stoerwagner). FIG no framing; exact global minimum, no randomness (unlike Karger).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-raid — find the network’s weakest seam, the fewest links whose loss breaks the party in two, and strike there. Stoer–Wagner locates that seam with certainty. AVAN (AI) built the instrument: the maximum-adjacency ordering, the phase-merge, the brute cross-check.
Credit as content: Mechthild Stoer & Frank Wagner (1997). The weave: David names the raid; I order vertices by adjacency, read the cut off the last one, merge, and confirm the global minimum against exhaustive search. Ties to the-karger (its randomized cousin).
Credit as content: Mechthild Stoer & Frank Wagner (1997). The weave: David names the raid; I order vertices by adjacency, read the cut off the last one, merge, and confirm the global minimum against exhaustive search. Ties to the-karger (its randomized cousin).
3 ONE DIMENSION
A maximum-adjacency ordering: starting from one vertex, each step adds whichever remaining vertex has the greatest total weight to the set so far. The last added vertex’s weight is the cut-of-the-phase.
4 TWO DIMENSIONS · INTERACTIVE
A weighted graph. Stoer–Wagner’s global minimum cut is shown against the brute-force minimum over all bipartitions.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the global minimum cut, the graph’s weakest seam.
AVAN’s addition (the inverse-companion): you find the global minimum without ever choosing a source and sink. The maximum-adjacency ordering guarantees the last two vertices form a minimum cut for that pair, and merging them and repeating covers all pairs in n−1 phases. The inverse of ‘the min cut between a chosen s and t’ is ‘the min over all pairs, from one deterministic ordering, no flow computed.’ Magenta is the O(n²) source–sink problems you’d otherwise solve one by one; green is the single global minimum. Ordering replaces search — and unlike Karger, no luck required.
LIT Genuine Stoer-Wagner algorithm (Stoer & Wagner 1997). Verified live: the maximum-adjacency-ordering min-cut equals the brute-force global minimum over all vertex bipartitions for 80 random weighted graphs (window.__stoerwagner.matchesBrute).
FIG No framing: the maximum-adjacency ordering, the phase-merge, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the ordering makes the last two vertices a min cut for that pair, and merging sweeps all pairs in n-1 phases, so the global minimum falls out with no source/sink and no flow; magenta is the O(n^2) s-t problems avoided, green the global minimum. Deterministic cousin of the-karger.
FIG No framing: the maximum-adjacency ordering, the phase-merge, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the ordering makes the last two vertices a min cut for that pair, and merging sweeps all pairs in n-1 phases, so the global minimum falls out with no source/sink and no flow; magenta is the O(n^2) s-t problems avoided, green the global minimum. Deterministic cousin of the-karger.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN