Stoer–Wagner Algorithm

Stoer–Wagner algorithm is a deterministic combinatorial optimization algorithm within computation and algorithms that computes the global minimum cut of an undirected, non-negatively edge-weighted graph G = (V, E, w) in O(VE + V² log V) time. Published by Mechthild Stoer and Frank Wagner in 1997—and closely related to the maximum adjacency ordering framework introduced by Hiroshi Nagamochi and Toshihide Ibaraki in 1992—the algorithm solves the global minimum cut problem without invoking maximum network flow subroutines or linear programming relaxations.

Prior to the discovery of ordering-based contraction methods, finding a deterministic global minimum cut required solving V − 1 instances of the s–t minimum cut problem via the max-flow min-cut theorem, fixing a reference vertex s and iterating over all remaining targets t ∈ V \ {s}. By contrast, the Stoer–Wagner algorithm performs V − 1 phases of maximum adjacency search (structurally identical to Prim's algorithm but maximizing total connection weight to the visited set rather than minimizing single-edge weight). Each phase identifies a cut of the phase between the last two vertices added to the ordering, records its cut weight, and contracts those two vertices into a single supervertex, returning the minimum cut encountered across all V − 1 contractions.

Global vs. Terminal Minimum Cuts

In an undirected graph G = (V, E) equipped with non-negative edge weights w : E → ℝ_≥0, a cut (S, V \ S) is a partition of the vertex set into two non-empty disjoint subsets S and V \ S. The weight of the cut, denoted w(S, V \ S), is the sum of weights of all edges having one endpoint in S and the other in V \ S. The global minimum cut problem seeks a non-trivial partition (S, V \ S) that minimizes w(S, V \ S) over all 2^|V|−1 − 1 candidate partitions, whereas an s–t minimum cut additionally requires two specified terminals s, t ∈ V to lie on opposite sides of the partition (s ∈ S and t ∈ V \ S).

This distinction induces a dichotomy across all global minimum cuts of G relative to any chosen pair of distinct vertices s and t:

1. Either a global minimum cut separates s and t, in which case its weight equals the minimum s–t cut weight λ(s, t).
2. Or no global minimum cut separates s and t, in which case s and t lie on the same side of every global minimum cut, and contracting s and t into a single merged vertex st preserves the global minimum cut weight of G.

Consequently, if an algorithm can find any pair of vertices (s, t) along with a certifying s–t minimum cut in a single pass, it can record that s–t cut candidate, contract s and t, and recurse on a graph with |V| − 1 vertices.

Maximum Adjacency Search and Proof Principle

During each phase on the current graph G' = (V', E'), the Stoer–Wagner algorithm grows an ordered subset A ⊂ V' starting from an arbitrary initial vertex a₁ (setting A₁ = {a₁}). At each step i = 2, …, |V'|, the algorithm selects the unvisited vertex z ∈ V' \ A_i−1 that is most tightly connected to A_i−1, maximizing the cumulative edge weight:

Let s = a_|V'|−1 and t = a_|V'| denote the second-to-last and last vertices added to the maximum adjacency ordering. The cut of the phase is the partition (V' \ {t}, {t}), whose weight is simply the weighted degree of t in G': w(V' \ {t}, t).

Stoer and Wagner proved by induction on the set of active vertices—subsets A_i where an arbitrary s–t cut C separates a_i from a_i−1—that the cut of the phase (V' \ {t}, {t}) is guaranteed to be a minimum s–t cut in G'. For every active vertex v, the inductive invariant establishes that w(A_v, v) ≤ w(C_v), where C_v is the cut induced by C on the subgraph A_v ∪ {v}. Evaluating this inequality at the final active vertex v = t yields w(V' \ {t}, t) ≤ w(C) for every s–t cut C.

Iterative Contraction Loop

The complete Stoer–Wagner algorithm executes |V| − 1 phases:

1. Initialization: Set w_best ← +∞ and C_best ← ∅. Maintain a vertex contraction list for each supervertex in G.
2. Maximum Adjacency Phase: Using a max-priority queue keyed on key[v] = w(A, v), extract the vertex with the largest key |V'| times. For each extracted vertex u and each incident edge (u, v) with v ∉ A, increase key[v] by w(u, v).
3. Cut Evaluation: Let s and t be the penultimate and final vertices extracted in Step 2. If key[t] = w(V' \ {t}, t) < w_best, update w_best ← key[t] and record the constituent original vertices of supervertex t as C_best.
4. Vertex Contraction: Merge vertex t into vertex s by redirecting all edges (t, v) to (s, v) (summing weights of parallel edges and deleting self-loops (s, s)). Repeat Steps 2–4 until |V'| = 1.

Priority Queue Implementations and Comparative Runtime

In each of the |V| − 1 phases, the maximum adjacency search performs at most |V| extract-max operations and at most |E| increase-key operations. Using a Fibonacci heap (or a pairing heap in practice), each extract-max takes O(log V) amortized time and each increase-key takes O(1) amortized time, bounding a single phase to O(E + V log V) and all |V| − 1 phases to O(VE + V² log V). With a binary max-heap, each phase requires O((V + E) log V) time, giving O(VE log V) overall; on dense graphs represented as an adjacency matrix without a heap, each phase takes O(V²) time for a total of O(V³).

Network Survivability and Traveling Salesperson Subtour Separation

In telecommunications backbone engineering and power-grid contingency planning, the global edge connectivity λ(G) computed by the Stoer–Wagner algorithm measures the minimum cumulative link capacity whose failure disconnects the network into isolated islands. In integer linear programming solvers for the symmetric Traveling Salesperson Problem (TSP), branch-and-cut frameworks run the Stoer–Wagner algorithm on the fractional support graph of the current linear programming relaxation: if the global minimum cut has weight strictly less than 2.0, the corresponding partition (S, V \ S) immediately yields a violated subtour elimination constraint ∑_e∈δ(S) x_e ≥ 2.

Graph-Based Clustering and Bioinformatics Module Discovery

Because the global minimum cut partitions a similarity graph along its weakest inter-cluster boundary without requiring pre-selected seed centroids, iterative Stoer–Wagner partitioning is used in computer vision image segmentation, VLSI netlist partitioning, and bioinformatics protein-protein interaction (PPI) network decomposition to isolate tightly coupled functional protein complexes.

How does the maximum adjacency search in Stoer–Wagner differ from Prim's minimum spanning tree algorithm?

Both algorithms greedily grow a vertex subset A by extracting one unvisited vertex per step from a priority queue. However, Prim's algorithm uses a min-priority queue where each unvisited vertex v stores the minimum single edge weight min_u∈A w(u, v) connecting v to A, whereas the Stoer–Wagner maximum adjacency search uses a max-priority queue where v stores the sum of all edge weights ∑_u∈A w(u, v) connecting v to A.

Does the choice of the starting vertex in each phase affect the correctness of the Stoer–Wagner algorithm?

No. The cut-of-the-phase theorem holds for any arbitrary starting vertex a₁ ∈ V' in each phase. While choosing a different starting vertex a₁ may result in a different pair of final vertices (s, t) at the end of that phase, the partition (V' \ {t}, {t}) is still guaranteed to be a minimum s–t cut for whatever pair (s, t) finishes last, preserving the correctness of the contraction recurrence across all |V| − 1 phases.

Can the Stoer–Wagner algorithm be applied to directed graphs or graphs with negative edge weights?

No. The inductive proof of the cut-of-the-phase theorem relies on edge symmetry w(u, v) = w(v, u) and non-negativity w(u, v) ≥ 0 so that adding vertices to A monotonically increases connection weights. For directed graphs, computing a global minimum directed cut requires flow-based methods such as the Hao–Orlin push-relabel algorithm, while the minimum cut problem with arbitrary negative edge weights is equivalent to the NP-hard maximum cut problem.

1. Stoer, M., & Wagner, F. (1997). "A simple min-cut algorithm." Journal of the ACM, 44(4), 585–591. https://doi.org/10.1145/263867.263872
2. Nagamochi, H., & Ibaraki, T. (1992). "Computing edge-connectivity in multigraphs and capacitated graphs." SIAM Journal on Discrete Mathematics, 5(1), 54–66. https://doi.org/10.1137/0405004
3. Frank, A. (1994). "On the edge-connectivity algorithm of Nagamochi and Ibaraki." Laboratoire Artemis, IMAG, Université Joseph Fourier, Grenoble, Technical Report. https://web.cs.elte.hu/~frank/cikkek/FrankP28.pdf
4. Chekuri, C. S., Goldberg, A. V., Karger, D. R., Levine, M. S., & Stein, C. (1997). "Experimental study of minimum cut algorithms." In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '97), 324–333. https://dl.acm.org/doi/10.5555/314161.314315