Introduction

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(n2)O(n^2) max-flow computations on a graph with nn 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.

Try It: Contract the Tightest Vertex

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">A weighted graph with 6 vertices. One <b>Stoer-Wagner phase</b> builds a maximum-adjacency ordering: always pick the vertex most tightly connected to the chosen set. The last two vertices define a <b>cut candidate</b>. Click <b>Next vertex</b> to advance the phase, then <b>Contract &amp; restart</b> to merge and repeat.</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">Phase ordering</div>
      <div id="ordering"></div>
    </div>
    <div class="cut-box">
      <div class="box-label">Cut candidate</div>
      <div id="cut-val">—</div>
    </div>
    <div class="best-box">
      <div class="box-label">Best cut so far</div>
      <div id="best-val">—</div>
    </div>
  </div>
</div>
<div class="status" id="status">Press <b>Next vertex</b> to start a phase.</div>
<div class="btns">
  <button id="btn-next" type="button">Next vertex</button>
  <button id="btn-contract" type="button" disabled>Contract &amp; restart</button>
  <button id="btn-reset" type="button" class="ghost">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; }
/* 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Stoer-Wagner phase demo.
// Graph: 6 vertices (0-5), weighted undirected edges from the classic example.
// One "phase" = maximum adjacency ordering from a start vertex.
// The last vertex added is the cut candidate; its incident edge weights sum = cut value.
// After a phase we contract (merge) the last two vertices.

// Initial graph as adjacency matrix (symmetric). Vertices labeled A-F.
const LABELS = ['A','B','C','D','E','F'];
// Positions in the 320x240 SVG
const POS = [
  [60, 60],   // A
  [170, 40],  // B
  [280, 60],  // C
  [60, 180],  // D
  [170, 200], // E
  [280, 180], // F
];
// Initial edge weights (upper triangle stored as [u,v,w])
const INIT_EDGES = [
  [0,1,2],[0,3,3],
  [1,2,3],[1,3,2],[1,4,2],
  [2,4,2],[2,5,3],
  [3,4,3],
  [4,5,2]
];

// --- State ---
let adj = [];   // adj[u][v] = weight (merged super-vertices tracked by representative)
let alive = []; // which original vertices are still active representatives
let merged = [];// merged[v] = list of original vertex indices collapsed into representative v
let order = []; // current phase ordering (representatives)
let key = [];   // key[v] = sum of weights to chosen set
let chosen = new Set();
let phaseStart = null; // start vertex representative
let bestCut = Infinity;
let bestCutEdges = null; // set of edge descriptors forming the best cut
let phaseCutVal = null;
let phaseCutVertex = null; // the 't' vertex of this phase
let phasePrev = null;      // 's' vertex
let phaseComplete = false;
let done = false;

function initGraph() {
  const n = LABELS.length;
  adj = Array.from({length:n}, () => new Array(n).fill(0));
  for (const [u,v,w] of INIT_EDGES) { adj[u][v] = w; adj[v][u] = w; }
  alive = Array.from({length:n}, (_,i)=>i);
  merged = alive.map(i=>[i]);
  order = []; key = new Array(n).fill(0); chosen = new Set();
  phaseStart = alive[0];
  phaseComplete = false; phaseCutVal = null; phaseCutVertex = null; phasePrev = null;
  bestCut = Infinity; bestCutEdges = null;
  done = false;
}

function startPhase(startV) {
  order = []; chosen = new Set();
  key = new Array(LABELS.length).fill(0);
  phaseComplete = false; phaseCutVal = null; phaseCutVertex = null; phasePrev = null;
  // Add start vertex first
  chosen.add(startV); order.push(startV);
  // Update keys
  for (const v of alive) if (!chosen.has(v)) key[v] += adj[startV][v];
}

// Pick vertex not yet chosen with maximum key
function pickNext() {
  let best = -1, bestKey = -1;
  for (const v of alive) {
    if (!chosen.has(v) && key[v] > bestKey) { bestKey = key[v]; best = v; }
  }
  return best;
}

function addVertex(v) {
  phasePrev = order.length >= 1 ? order[order.length - 1] : null;
  chosen.add(v); order.push(v);
  // Update keys
  for (const u of alive) if (!chosen.has(u)) key[u] += adj[v][u];
  if (chosen.size === alive.length) {
    // Phase complete
    phaseComplete = true;
    phaseCutVertex = v; // t
    phasePrev = order[order.length - 2]; // s
    phaseCutVal = 0;
    for (const u of alive) phaseCutVal += adj[v][u]; // sum of all edges to t
    if (phaseCutVal < bestCut) { bestCut = phaseCutVal; }
  }
}

// Contract: merge last two vertices of the ordering
function contractPhase() {
  const t = phaseCutVertex, s = phasePrev;
  // Merge t into s
  merged[s] = merged[s].concat(merged[t]);
  // Update adjacency: for each other alive vertex u, adj[s][u] += adj[t][u]
  for (const u of alive) {
    if (u===s || u===t) continue;
    adj[s][u] += adj[t][u]; adj[u][s] = adj[s][u];
    adj[t][u] = 0; adj[u][t] = 0;
  }
  adj[s][t] = 0; adj[t][s] = 0;
  alive = alive.filter(v => v !== t);
  if (alive.length <= 1) { done = true; return; }
  // Start a new phase from the first alive vertex
  startPhase(alive[0]);
}

// --- Rendering ---
const svg = document.getElementById('graph-svg');

function mergedLabel(v) {
  return merged[v].map(i=>LABELS[i]).join('+');
}

function render() {
  svg.innerHTML = '';
  const defs = document.createElementNS('http://www.w3.org/2000/svg','defs');
  svg.appendChild(defs);

  // Draw edges
  for (let u = 0; u < LABELS.length; u++) {
    for (let v = u+1; v < LABELS.length; v++) {
      if (!alive.includes(u) || !alive.includes(v)) continue;
      if (adj[u][v] <= 0) continue;
      const [x1,y1] = POS[u], [x2,y2] = POS[v];
      const line = document.createElementNS('http://www.w3.org/2000/svg','line');
      line.setAttribute('x1',x1); line.setAttribute('y1',y1);
      line.setAttribute('x2',x2); line.setAttribute('y2',y2);
      const isCutEdge = phaseComplete && (u===phaseCutVertex||v===phaseCutVertex) && adj[u][v]>0 && phaseCutVal===bestCut;
      line.setAttribute('class','edge'+(isCutEdge?' cut':''));
      svg.appendChild(line);
      // Weight label
      const mx=(x1+x2)/2, my=(y1+y2)/2;
      const lbl = document.createElementNS('http://www.w3.org/2000/svg','text');
      lbl.setAttribute('x', mx+4); lbl.setAttribute('y', my-4);
      lbl.setAttribute('class','edge-label');
      lbl.textContent = adj[u][v];
      svg.appendChild(lbl);
    }
  }

  // Draw nodes
  for (const v of alive) {
    const [cx,cy] = POS[v];
    const isChosen = chosen.has(v);
    const isLast = phaseComplete && v===phaseCutVertex;
    const isPrev = phaseComplete && v===phasePrev;
    const cls = 'node-circle'+(isLast?' last':isPrev?' prev':isChosen?' chosen':'');
    const circle = document.createElementNS('http://www.w3.org/2000/svg','circle');
    circle.setAttribute('cx',cx); circle.setAttribute('cy',cy); circle.setAttribute('r',22);
    circle.setAttribute('class',cls);
    svg.appendChild(circle);
    const lbl = document.createElementNS('http://www.w3.org/2000/svg','text');
    lbl.setAttribute('x',cx); lbl.setAttribute('y',cy);
    lbl.setAttribute('class','node-label'+(isLast?' last':isPrev?' prev':isChosen?' chosen':''));
    lbl.textContent = mergedLabel(v);
    svg.appendChild(lbl);
    // Show key value while phase in progress and vertex not yet chosen
    if (!phaseComplete && !isChosen && order.length>0) {
      const klbl = document.createElementNS('http://www.w3.org/2000/svg','text');
      klbl.setAttribute('x',cx); klbl.setAttribute('y',cy+14);
      klbl.setAttribute('class','edge-label');
      klbl.style.fontSize='9px'; klbl.style.fill='#e76f51';
      klbl.textContent = 'k='+key[v];
      svg.appendChild(klbl);
    }
  }
}

function updateUI() {
  document.getElementById('ordering').textContent = order.map(v=>mergedLabel(v)).join(' → ');
  document.getElementById('cut-val').textContent = phaseCutVal !== null ? phaseCutVal : '—';
  document.getElementById('best-val').textContent = bestCut < Infinity ? bestCut : '—';
  document.getElementById('btn-next').disabled = phaseComplete || done;
  document.getElementById('btn-contract').disabled = !phaseComplete || done;
}

function setStatus(html) { document.getElementById('status').innerHTML = html; }

document.getElementById('btn-next').addEventListener('click', () => {
  if (phaseComplete || done) return;
  if (order.length === 0) {
    startPhase(alive[0]);
    render(); updateUI();
    setStatus(fmt('Started phase. Chosen: <b>%mergedLabel%</b>. Pick next tightest vertex.', { mergedLabel: mergedLabel(alive[0]) }));
    return;
  }
  const v = pickNext();
  if (v === -1) return;
  addVertex(v);
  render(); updateUI();
  if (phaseComplete) {
    setStatus(fmt('Phase complete. Cut candidate = <b><b>%phaseCutVal%</b></b> (edges into <b><b>%mergedLabel%</b></b>). Press <b>Contract &amp; restart</b>.', { phaseCutVal: phaseCutVal, mergedLabel: mergedLabel(phaseCutVertex) }));
  } else {
    const rem = alive.length - chosen.size;
    setStatus(fmt('Added <b><b>%mergedLabel%</b></b> (key=%v%). %rem% %v2%', { mergedLabel: mergedLabel(v), v: key[v], rem: rem, v2: rem===1?'vertex remaining.':'vertices remaining.' }));
  }
});

document.getElementById('btn-contract').addEventListener('click', () => {
  if (!phaseComplete || done) return;
  contractPhase();
  render(); updateUI();
  if (done) {
    setStatus(fmt('Done! Global minimum cut = <b><b>%bestCut%</b>.', { bestCut: bestCut }));
  } else {
    setStatus(fmt('Contracted. New phase with <b><b>%length%</b></b> vertices.', { length: alive.length }));
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  initGraph(); startPhase(alive[0]);
  // Reset to blank start (no vertex chosen yet)
  order=[]; chosen=new Set(); key=new Array(LABELS.length).fill(0);
  render(); updateUI();
  setStatus('Reset. Press <b>Next vertex</b> to start a phase.');
});

initGraph();
render(); updateUI();
setStatus('Press <b>Next vertex</b> to start a phase.');
Result
Console

The last two vertices added in a phase — call them ss and tt — define a cut candidate: all edges incident to tt form the cut that separates tt from the rest. If that cut weight equals the global min cut, we're done; otherwise we merge ss and tt into one super-vertex and repeat. After n−1n-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 nn priority-queue operations per phase.

The Real Complexity

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+nlog⁡n)O(m + n \log n) with a Fibonacci heap. Across n−1n-1 phases the total is O(mn+n2log⁡n)O(mn + n^2 \log n) — polynomial in the size of the graph.
  • Correctness key lemma: in any phase, the last vertex tt added satisfies a remarkable property — the weight of all edges touching tt (the ss-tt 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−1n-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, O~(mlog⁡3n)\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.

Where It Matters

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.

Conclusion

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−1n-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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/stoer-wagner/Content licensed under CC BY-NC 4.0.