The Stoer-Wagner Algorithm

Imagine a network of cities connected by roads of varying capacities. Which roads, if cut, would isolate some group of cities from the rest while removing as little total capacity as possible? That is the minimum cut problem, and it sits at the heart of network design, reliability analysis, and clustering.

The obvious approach borrows from the max-flow min-cut theorem: run a max-flow algorithm between every pair of vertices, take the smallest result. That works, but it is expensive — you run $O(n^2)$ max-flow computations on a graph with $n$ vertices.

In 1997, Mechthild Stoer and Frank Wagner published a remarkably simple algorithm that finds the global minimum cut in a single sweep, with no max-flow computation at all. Their insight: a minimum-phase ordering of vertices — built greedily by always picking the vertex most tightly connected to the growing set — hands you the minimum cut almost for free.

Each phase of Stoer-Wagner builds a maximum adjacency ordering of the graph's vertices, starting from an arbitrary vertex. At every step the next vertex added is the one with the highest total edge weight into the already-chosen set.

<p class="hint">{{hint}}</p>
<div class="layout">
  <svg id="graph-svg" viewBox="0 0 320 240" xmlns="http://www.w3.org/2000/svg"></svg>
  <div class="side-panel">
    <div class="ordering-box">
      <div class="box-label">{{label_ordering}}</div>
      <div id="ordering"></div>
    </div>
    <div class="cut-box">
      <div class="box-label">{{label_cut}}</div>
      <div id="cut-val">—</div>
    </div>
    <div class="best-box">
      <div class="box-label">{{label_best}}</div>
      <div id="best-val">—</div>
    </div>
  </div>
</div>
<div class="status" id="status">{{press_next_start}}</div>
<div class="btns">
  <button id="btn-next" type="button">{{btn_next}}</button>
  <button id="btn-contract" type="button" disabled>{{btn_contract}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 12px; align-items: flex-start; }
#graph-svg { flex: 1 1 auto; min-width: 0; border: 1px solid #dde3ea; border-radius: 8px; background: #f8fafc; }
.side-panel { flex: 0 0 130px; display: flex; flex-direction: column; gap: 8px; }
.ordering-box, .cut-box, .best-box { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 8px; padding: 8px 10px; }
.box-label { font-size: .72rem; font-weight: 700; text-transform: uppercase; letter-spacing: .04em; color: #6b7a8d; margin-bottom: 4px; }
#ordering { font: 700 13px ui-monospace, monospace; color: #1d3557; min-height: 22px; line-height: 1.6; }
#cut-val, #best-val { font: 700 18px ui-monospace, monospace; color: #1d3557; }
#best-val { color: #0a7d33; }
.status { font-size: .9rem; font-weight: 600; margin: .5rem 0 .3rem; min-height: 1.5em; }
.status b { font-weight: 800; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
/* {{c_svg_helpers}} */
.edge { stroke: #9ab; stroke-width: 2; }
.edge.active { stroke: #e76f51; stroke-width: 2.8; }
.edge.cut { stroke: #e63946; stroke-width: 3; stroke-dasharray: 5 3; }
.node-circle { fill: #e8eef3; stroke: #7a9bb5; stroke-width: 2; }
.node-circle.chosen { fill: #1d3557; stroke: #1d3557; }
.node-circle.last { fill: #e63946; stroke: #c92f3c; }
.node-circle.prev { fill: #e76f51; stroke: #c95a2c; }
.node-label { font: 700 12px ui-monospace, monospace; text-anchor: middle; dominant-baseline: central; fill: #1d3557; }
.node-label.chosen { fill: #fff; }
.node-label.last { fill: #fff; }
.node-label.prev { fill: #fff; }
.edge-label { font: 600 10px ui-monospace, monospace; fill: #555; text-anchor: middle; }

// Code not found

The last two vertices added in a phase — call them $s$ and $t$ — define a cut candidate: all edges incident to $t$ form the cut that separates $t$ from the rest. If that cut weight equals the global min cut, we're done; otherwise we merge $s$ and $t$ into one super-vertex and repeat. After $n-1$ phases the algorithm has seen every possible cut and returns the smallest one.

Notice how the greedy ordering does all the heavy lifting. No flow computation, no matrix inversion — just $n$ priority-queue operations per phase.

How fast is the Stoer-Wagner algorithm, and why does it work at all?

• Running time: each phase runs a maximum adjacency ordering costing $O(m + n \log n)$ with a Fibonacci heap. Across $n-1$ phases the total is $O(mn + n^2 \log n)$ — polynomial in the size of the graph.
• Correctness key lemma: in any phase, the last vertex $t$ added satisfies a remarkable property — the weight of all edges touching $t$ (the $s$-$t$ min cut of that phase) is at most the weight of the true global minimum cut. So the algorithm never misses it.
• No max flow needed: the original approach (Gomory-Hu tree) required $n-1$ max-flow computations. Stoer-Wagner achieves the same result in a single deterministic pass with much simpler bookkeeping.
• Status: the algorithm is proven correct and optimal (Stoer & Wagner, 1997). It is a solved problem in the sense that the deterministic polynomial bound is tight for comparison-based methods on dense graphs. Faster randomized approaches exist (Karger 1993, $\tilde{O}(m \log^3 n)$), but for practical dense graphs Stoer-Wagner's simplicity wins.

This contrasts sharply with the P vs NP question: global min cut is firmly in P, while its cousin max cut is NP-hard. The difference — whether you are cutting as little as possible or as much as possible — separates a polynomial-time treasure from an intractable nightmare.

The global minimum cut answers a fundamental question about any network: where is it most fragile? That question appears across engineering and science:

• Network reliability: internet routers, power grids, and supply chains all have bottlenecks. The min cut identifies the set of links whose failure isolates part of the network.
• VLSI layout: chip designers partition a circuit into sections that fit on separate dies. Minimizing the wires that cross the partition boundary is a min-cut problem — fewer crossing wires means cheaper manufacturing.
• Graph clustering and community detection: if two groups of nodes in a social or biological network interact weakly across the boundary, the min cut can tease them apart. (The normalized variants used in image segmentation are relatives of the same idea.)
• Survivability analysis: telecommunications operators compute the edge connectivity of their backbone — the minimum cut value — to certify that no single failure can split the network.
• Algorithm design education: Stoer-Wagner is a textbook example of how a clever greedy invariant can replace an expensive black-box subroutine, a design pattern that recurs throughout algorithms.

Whenever you need to know where a weighted graph is thinnest, Stoer-Wagner gives you the answer in polynomial time — no guessing, no exponential search.

The Stoer-Wagner algorithm is a lesson in algorithmic elegance. The global minimum cut — a problem that seems to demand expensive flow computations — yields to a simple greedy rule: always grab the vertex most tightly connected to the set you have already chosen.

That single rule produces a phase ordering whose last two vertices hand you a cut candidate. Run $n-1$ phases, keep the smallest candidate, and you are done. No randomness, no max flow, no complicated data structures beyond a priority queue.

It is also a reminder of how much the sign of the problem matters. Minimizing a cut is easy; maximizing it is NP-hard. The Stoer-Wagner algorithm lives on the lucky side of that divide, and it does so with disarming simplicity.