Stoer-Wagner: Global Minimum Cut Without Max-Flow

The problem: a global cut, not an s-t cut

A cut of a connected undirected graph is a partition of its vertices into two non-empty sets; its weight is the sum of the weights of all edges crossing the partition. The global minimum cut asks for the cheapest such partition over all ways to split the graph. It answers concrete questions: what is the fewest edges (or lowest total capacity) whose failure disconnects a network? Where does a graph most naturally fall into two clusters?

Contrast this with the more familiar s-t min cut, which fixes two terminals s and t and finds the cheapest cut separating them. By the max-flow min-cut theorem, one s-t cut equals one max-flow computation. The naive route to a global cut is to fix s and run an s-t min cut for every possible sink t — that is V-1 max-flow computations. Stoer and Wagner's insight, building on Nagamochi and Ibaraki, is that you can get a min s-t cut for a cleverly chosen s and t almost for free, then merge those two vertices and repeat.

How it works: maximum-adjacency ordering and merging

The algorithm runs V-1 phases. Each phase performs a maximum-adjacency (MA) ordering, also called a legal ordering, and then merges two vertices.

A phase grows a set A, starting from any arbitrary vertex. Repeatedly it adds the vertex most tightly connected to A:

MinimumCutPhase(G, w, a):
  A = {a}
  while A != V(G):
    add z not in A maximizing w(A, z) = sum of w(y,z) for y in A
  let s, t = last two vertices added (t is last)
  cut-of-the-phase = weight of edges from t to A\{t}
  merge s and t   # contract into one vertex
  return cut-of-the-phase

Key lemma (Stoer-Wagner): the cut-of-the-phase — the cut that isolates the very last vertex t from everything else — is always a minimum s-t cut in the current graph, where s and t are the last two vertices added. This is the whole trick: MA ordering hands you an optimal s-t cut without any flow.

Merging s and t replaces them with one super-vertex; parallel edges to any other vertex v combine by adding weights, w(new, v) = w(s, v) + w(t, v). The global min cut is the minimum cut-of-the-phase seen across all V-1 phases.

Complexity and a worked step-trace

Each phase is one MA ordering: a priority-queue traversal much like Prim's MST or Dijkstra. With a Fibonacci heap a phase costs O(E + V·log V); across V-1 phases the total is O(V·E + V²·log V). On a dense graph stored as an adjacency matrix, each phase is a simple O(V²) selection loop, giving the famously compact O(V³) implementation that fits in about 30 lines. Space is O(V²) for the matrix form, O(V+E) otherwise.

Trace a tiny graph, vertices {1,2,3,4}, edges 1-2:3, 1-3:1, 2-3:2, 2-4:1, 3-4:4:

Phase 1, start A={1}:
  add 2 (w=3); add 3 (w=1+2=3); add 4 (w=1+4=5)
  order: 1,2,3,4 -> s=3, t=4
  cut-of-phase = edges at 4 = 1+4 = 5
  merge 3,4 -> super {3,4}; edges: 1-2:3, 1-{34}:1, 2-{34}:3
Phase 2, start A={1}:
  add 2 (w=3); add {34} (w=1+3=4)
  order: 1,2,{34} -> s=2, t={34}
  cut-of-phase = edges at {34} = 1+3 = 4
  merge -> two vertices left, next phase gives cut = 4

The minimum over all phases is 4: isolating vertex 1... in fact the min cut here separates {1,2} from {3,4} at cost 1+2+1=4. The algorithm reports 4.

Where it is used in real systems

Global min cut is a workhorse whenever you need a graph's weakest link or its most natural binary split:

• VLSI and hypergraph partitioning: chip-design tools split netlists to minimize wires crossing between placement regions; min-cut is the objective, and SW-style scans feed multilevel partitioners like METIS/hMETIS.
• Image segmentation and computer vision: pixels become graph nodes with similarity-weighted edges; a min cut separates foreground from background. (Normalized-cut spectral methods extend this to avoid trivial cuts.)
• Network reliability and design: the min cut of a capacitated network is its bottleneck — the cheapest set of links whose removal disconnects it — used in telecom planning and vulnerability analysis.
• Clustering and community detection: repeatedly taking min cuts yields a hierarchical decomposition of graphs.

The algorithm ships in production libraries: the Boost Graph Library (stoer_wagner_min_cut), LEMON, and NetworkX's stoer_wagner function. Its appeal in these libraries is that it needs no flow machinery and is short enough to audit.

Comparison: why skip max-flow?

Before Stoer-Wagner, the standard was flow-based: Gomory-Hu trees or repeated s-t cuts require O(V) max-flow computations, and even fast max-flow pushes total cost well above O(V³) on dense graphs. Hao-Orlin cleverly reuses a single push-relabel flow to hit O(V·E·log(V²/E)) but is intricate to implement.

• vs. flow methods: SW is deterministic and needs no residual graphs, augmenting paths, or preflows — just an MST-like scan. The tradeoff: it requires non-negative edge weights and does not directly handle directed graphs.
• vs. Karger-Stein randomized contraction: O(V²·log³ V) expected — asymptotically faster on some inputs but Monte Carlo, with a small probability of missing the true min cut, so it is repeated for confidence. SW is exact every time.
• vs. Nagamochi-Ibaraki: its direct predecessor, same O(V·E + V²·log V) bound; SW simplified the presentation and proof. Modern near-linear results — Karger's 2000 randomized (Monte Carlo) algorithm, and the later deterministic near-linear min cut of Kawarabayashi-Thorup (2015) and follow-ups — beat SW asymptotically but are far more complex.

For an exact, easy-to-code, dependency-free global min cut, Stoer-Wagner remains the default choice.

Pitfalls, failure modes, and significance

Non-negative weights are mandatory. The correctness lemma relies on w(A,z) being monotone; negative edges break it and can produce wrong cuts. If you have negative weights, min cut is a different, harder problem.

It is undirected only. For directed graphs the notion of a symmetric cut does not apply; use flow-based directed min-cut instead.

Common implementation bugs:

• Forgetting to merge in every phase, or merging the wrong pair — you must contract the last two added vertices s and t, not the first ones.
• Mis-summing parallel edges during contraction: w(new,v) = w(s,v) + w(t,v), and the s-t edge itself must be dropped.
• Off-by-one on phases: exactly V-1 phases; stopping early misses candidate cuts.
• Recording the cut-of-the-phase but losing the partition — track which original vertices got merged into t if you need the actual vertex sets, not just the weight.

Significance: Stoer-Wagner demonstrated that a problem long assumed to require max-flow could be solved by a strikingly simple greedy scan, with a one-page inductive proof. It reshaped how the min-cut problem is taught and remains one of the most elegant results in combinatorial optimization.

Global minimum cut algorithms compared

Algorithm	Time complexity	Uses max-flow?	Notes
Stoer-Wagner (1997)	O(V·E + V²·log V), or O(V³)	No	Deterministic; non-negative weights only
Gomory-Hu / max-flow all-pairs	O(V) max-flow calls = O(V²·E) or worse	Yes	Fix s, iterate t over all sinks
Hao-Orlin (1994)	O(V·E·log(V²/E))	Yes	Single push-relabel run, reuses flow
Karger-Stein (1996)	O(V²·log³ V) expected	No	Randomized contraction; small error prob.
Nagamochi-Ibaraki (1992)	O(V·E + V²·log V)	No	Sparse-certificate scan; SW's predecessor