Stoer-Wagner Algorithm

A Bit of History

Mechthild Stoer and Frank Wagner published "A Simple Min-Cut Algorithm" in 1997, providing a strikingly clean way to compute the global minimum cut of a weighted, undirected graph — the cheapest way to split the graph's vertices into two non-empty groups, without any pre-specified source or sink. Their algorithm made a splash precisely because of its title: unlike the classical approach (running Ford-Fulkerson-style max-flow between a fixed vertex and all \(n-1\) other candidates), their method achieves comparable or better runtime with a conceptually far simpler algorithm.

Working Principle

The algorithm repeats a "minimum cut phase" until only 2 vertices (or "super-vertices") remain:

1. Maximum adjacency search: starting from an arbitrary vertex, repeatedly add the vertex most strongly connected (by total edge weight) to the already-selected set, until every vertex has been added — producing an ordering \(v_1, v_2, \ldots, v_n\).
2. The cut-of-the-phase is the cut separating the last vertex \(v_n\) added from all the others — record its weight as a candidate for the global minimum.
3. Merge the last two vertices added (\(v_{n-1}\) and \(v_n\)) into a single super-vertex, combining their edge weights to all other vertices, and repeat from step 1 on the now-smaller graph.

After \(n-1\) phases, the graph has shrunk to a single super-vertex, and the true global minimum cut is the smallest cut-of-the-phase recorded across all phases.

Worked Example

On a small 4-vertex weighted graph, the first maximum adjacency search might produce the order \(A, B, C, D\) (each chosen because it has the strongest total connection to the already-visited set). The cut-of-the-phase separates \(D\) from \(\{A,B,C\}\), with weight equal to the sum of \(D\)'s edge weights to the rest. Merging \(C\) and \(D\) into a super-vertex \(CD\) (combining their edges), the algorithm repeats on the smaller 3-vertex graph \(\{A, B, CD\}\), continuing until only one super-vertex remains — the overall minimum across all recorded cut-of-the-phase values is the answer.

Correctness

The correctness proof rests entirely on the "cut-of-the-phase is a valid min-cut between the last two vertices" lemma mentioned above. Since a global minimum cut must separate some pair of vertices, and every pair gets merged together at some phase during the algorithm's run, the true global minimum is guaranteed to be recorded as some phase's cut-of-the-phase value at the latest possible moment before that specific pair is merged — meaning the minimum over all phases is provably the true global answer, not just a heuristic approximation.

Complexity Analysis

Each maximum adjacency search phase takes \(O(E + V\log V)\) using a Fibonacci heap (or \(O(V^2)\) with a simple array-based priority structure), and there are \(O(V)\) phases total:

$$\text{Time: } O(VE + V^2 \log V) \qquad \text{(Fibonacci heap implementation)}$$

This comfortably matches or beats classical max-flow-based global min-cut approaches (which would otherwise require \(O(V)\) separate max-flow computations), while requiring no flow-network machinery whatsoever — no source, no sink, no augmenting paths.

Implementation

def stoer_wagner(graph):
    """
    graph: n x n weight matrix (0 if no edge, symmetric, non-negative weights).
    Returns the weight of the global minimum cut.
    """
    n = len(graph)
    w = [row[:] for row in graph]
    vertices = list(range(n))
    best_cut = float('inf')

    while len(vertices) > 1:
        # Maximum adjacency search (a simplified "min-cut phase")
        a = [vertices[0]]
        weights = {v: w[vertices[0]][v] for v in vertices if v != vertices[0]}
        prev, last = None, vertices[0]
        while len(a) < len(vertices):
            # Pick the vertex most strongly connected to the current set `a`
            next_v = max(weights, key=weights.get)
            a.append(next_v)
            prev, last = last, next_v
            del weights[next_v]
            for v in weights:
                weights[v] += w[next_v][v]

        # Cut-of-the-phase: weight separating `last` from the rest
        cut_of_phase = sum(w[last][v] for v in vertices if v != last)
        best_cut = min(best_cut, cut_of_phase)

        # Merge `last` into `prev`
        for v in vertices:
            if v != prev and v != last:
                w[prev][v] += w[last][v]
                w[v][prev] += w[v][last]
        vertices.remove(last)

    return best_cut

graph = [
    [0, 2, 0, 0, 3],
    [2, 0, 3, 2, 2],
    [0, 3, 0, 4, 0],
    [0, 2, 4, 0, 2],
    [3, 2, 0, 2, 0],
]
print(stoer_wagner(graph))

#include <vector>
#include <limits>
#include <algorithm>
#include <iostream>
using namespace std;

int stoerWagner(vector<vector<int>> w) {
    int n = w.size();
    vector<int> vertices(n);
    for (int i = 0; i < n; i++) vertices[i] = i;
    int bestCut = numeric_limits<int>::max();

    while (vertices.size() > 1) {
        vector<bool> added(n, false);
        vector<int> weights(n, 0);
        int prev = -1, last = vertices[0];
        added[last] = true;
        for (int v : vertices) weights[v] = w[last][v];

        for (size_t iter = 1; iter < vertices.size(); iter++) {
            int next = -1, best = -1;
            for (int v : vertices) {
                if (!added[v] && weights[v] > best) { best = weights[v]; next = v; }
            }
            added[next] = true;
            prev = last; last = next;
            for (int v : vertices) if (!added[v]) weights[v] += w[next][v];
        }

        int cutOfPhase = 0;
        for (int v : vertices) if (v != last) cutOfPhase += w[last][v];
        bestCut = min(bestCut, cutOfPhase);

        for (int v : vertices) {
            if (v != prev && v != last) {
                w[prev][v] += w[last][v];
                w[v][prev] += w[v][last];
            }
        }
        vertices.erase(find(vertices.begin(), vertices.end(), last));
    }
    return bestCut;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 0, 0, 3}, {2, 0, 3, 2, 2}, {0, 3, 0, 4, 0},
        {0, 2, 4, 0, 2}, {3, 2, 0, 2, 0}
    };
    cout << stoerWagner(graph) << endl;
    return 0;
}

import java.util.*;

class StoerWagner {
    static int solve(int[][] w) {
        int n = w.length;
        List<Integer> vertices = new ArrayList<>();
        for (int i = 0; i < n; i++) vertices.add(i);
        int bestCut = Integer.MAX_VALUE;

        while (vertices.size() > 1) {
            boolean[] added = new boolean[n];
            int[] weights = new int[n];
            int prev = -1, last = vertices.get(0);
            added[last] = true;
            for (int v : vertices) weights[v] = w[last][v];

            for (int iter = 1; iter < vertices.size(); iter++) {
                int next = -1, best = -1;
                for (int v : vertices) {
                    if (!added[v] && weights[v] > best) { best = weights[v]; next = v; }
                }
                added[next] = true;
                prev = last; last = next;
                for (int v : vertices) if (!added[v]) weights[v] += w[next][v];
            }

            int cutOfPhase = 0;
            for (int v : vertices) if (v != last) cutOfPhase += w[last][v];
            bestCut = Math.min(bestCut, cutOfPhase);

            for (int v : vertices) {
                if (v != prev && v != last) {
                    w[prev][v] += w[last][v];
                    w[v][prev] += w[v][last];
                }
            }
            vertices.remove(Integer.valueOf(last));
        }
        return bestCut;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 0, 3}, {2, 0, 3, 2, 2}, {0, 3, 0, 4, 0},
            {0, 2, 4, 0, 2}, {3, 2, 0, 2, 0}
        };
        System.out.println(solve(graph));
    }
}

Real-World Applications

Exercises

1. Trace through one full minimum-cut phase by hand on a small 4-vertex weighted graph, identifying the maximum adjacency order and the resulting cut-of-the-phase.
2. Explain why the algorithm needs no source or sink vertex, in contrast to Ford-Fulkerson-style max-flow computations from earlier deep dives.
3. Compare running Stoer-Wagner once versus running Ford-Fulkerson \(n-1\) times (fixing one vertex as source and trying every other vertex as sink) to find the same global minimum cut — which approach is conceptually simpler, and why?
4. Challenge: Modify the implementation to also track and return the actual partition of vertices achieving the minimum cut, not just its weight.

Limitations