Stoer-Wagner Minimum Cut, in depth: maximum adjacency ordering, the cut-of-the-phase proof, a traced example and tested code

The problem and the max-flow baseline

Let G have vertices V, edges E and a non-negative weight on each edge. A cut is a partition of V into a set S and its complement, both non-empty, and its weight is the total weight of edges with one end in each. The minimum cut is the partition minimising that weight.

The obvious approach uses max-flow. The max-flow min-cut theorem says the minimum s-t cut equals the maximum s-t flow. Fix any vertex s; on the global minimum cut, some vertex t lies on the other side, so the answer is the smallest of the n-1 minimum s-t cuts for every t. That is correct, but it costs n-1 max-flow runs, each with its own machinery, such as the augmenting paths in Ford-Fulkerson. Stoer-Wagner replaces all of that with a single simple primitive.

Negative weights break the problem, and with them the algorithm: the proof below relies on adding non-negative quantities. Directed graphs also need different algorithms, because a cut's weight depends on direction.

One phase: maximum adjacency ordering

The primitive is the maximum adjacency ordering. Start a set A with any vertex. Repeatedly add the vertex outside A that is most tightly connected to A, meaning the vertex v maximising w(A, v), the total weight of edges between v and vertices already in A. When every vertex has been added, call the second-to-last vertex s and the last vertex t.

This is the structure of Prim's algorithm with one change. Prim keys each outside vertex by its single cheapest edge into the tree and takes the minimum. Here each vertex is keyed by the sum of all its edges into A, and we take the maximum. When v joins A, every neighbour u outside A has its key increased by w(v, u). Keys only grow, which suits a priority queue.

The cut of the phase is the cut that puts t alone on one side: its weight is w(V minus t, t), which is exactly t's key at the moment it is added. After recording it, the phase merges s and t into a single vertex, adding parallel edge weights together. The next phase runs on a graph with one vertex fewer. After n-1 phases one vertex is left, and the answer is the lightest cut of the phase seen along the way, expanded back to the original vertices that the merged vertex t stood for.

Why it is correct

The whole algorithm rests on one lemma: the cut of the phase is a minimum s-t cut for the s and t of that phase. Given the lemma, correctness follows by a two-case argument. Either the global minimum cut separates s and t, in which case it is an s-t cut, so it is at least the cut of the phase, which is itself a cut and so cannot be lighter than the minimum: the two are equal, and we recorded it. Or the global minimum cut keeps s and t together, in which case merging them destroys nothing, and induction on the smaller graph finds it later.

The lemma's proof is short. Take any cut C that separates s and t. Call a vertex v active if v and the vertex added just before it lie on opposite sides of C. Let A_v be the vertices added before v, and C_v the weight of the edges of C that lie inside A_v plus v. The claim is that w(A_v, v) is at most C_v for every active v. For the first active vertex this holds because every edge from A_v to v crosses C. For the next active vertex u, split w(A_u, u) into the part from A_v and the part from v and the vertices added after it. The first part is at most w(A_v, v), because v was chosen over u when both were candidates, and by induction that is at most C_v. The second part consists of edges that cross C, because those vertices sit on the opposite side from u, so it is counted in C_u but not in C_v. Adding gives w(A_u, u) at most C_u. Since s and t are on opposite sides, t is active, and C_t is the whole of C. So the cut of the phase, w(A_t, t), is at most C.

Non-negativity entered in that last step: C_u contains every edge of C_v plus others, and C_v plus some crossing edges is at most C_u only if those other edges weigh at least zero.

Worked example: tracing six vertices

Take the six-vertex graph below. Vertices 0, 1 and 2 form one dense cluster, 3, 4 and 5 another, and two light edges of weight 1 join them. Each phase starts from the lowest-numbered remaining vertex and breaks key ties towards the lower vertex number, which is what the implementation below does.

Phase 1 starts with A = {0}. Keys become 3 for vertex 1 and 2 for vertex 2, so 1 joins. Vertex 2's key rises to 2 + 4 = 6 and vertex 3's to 1, so 2 joins. Now 3 and 4 both have key 1; the tie goes to 3. Vertex 4's key becomes 1 + 3 = 4 and vertex 5's becomes 2, so 4 joins, and 5's key rises to 6. Vertex 5 is last. The cut of the phase isolates 5 with weight 6, and s = 4, t = 5 are merged.

The remaining phases go the same way. Every number in the table was produced by the implementation in the next section.

The lightest cut of the phase is 2, found in phase 3, and it separates {3, 4, 5} from {0, 1, 2}: exactly the two red edges. Notice that phase 1 found only a cut of 6 even though the answer was already present. A single phase guarantees only a minimum s-t cut for its own s and t, which is why the algorithm must run all n-1 phases and keep the best.

Implementation in Python

This implementation keeps the graph as adjacency dictionaries, uses Python's heapq as a max-heap by negating keys, and skips stale heap entries lazily rather than supporting a decrease-key operation. It was checked against brute-force enumeration of every cut on thousands of random graphs with up to nine vertices, including parallel edges, self-loops, zero weights, fractional weights and disconnected graphs.

import heapq


def stoer_wagner(n, edges):
    """Global minimum cut of an undirected graph with non-negative weights.

    n: vertices are 0..n-1. edges: iterable of (u, v, weight).
    Returns (cut_weight, sorted list of vertices on one side).
    """
    if n < 2:
        raise ValueError("need at least two vertices")
    w = [dict() for _ in range(n)]               # adjacency: w[u][v] = weight
    for u, v, c in edges:
        if c < 0:
            raise ValueError("negative weight")
        if u != v:                               # self-loops never cross a cut
            w[u][v] = w[u].get(v, 0) + c         # parallel edges add up
            w[v][u] = w[v].get(u, 0) + c
    groups = {v: [v] for v in range(n)}          # original vertices per super-vertex
    active = set(range(n))
    best, best_side = float("inf"), None

    while len(active) > 1:
        # One phase: maximum adjacency ordering with a lazy max-heap.
        key = {v: 0 for v in active}
        heap, added, order = [], set(), []
        while len(added) < len(active):
            if not heap:                         # first vertex, or a new component
                v0 = min(active - added)
                heap.append((0, v0))
            neg, v = heapq.heappop(heap)
            if v in added or -neg != key[v]:
                continue                         # stale heap entry
            added.add(v)
            order.append(v)
            for u, c in w[v].items():
                if u not in added:
                    key[u] += c
                    heapq.heappush(heap, (-key[u], u))
        s, t = order[-2], order[-1]
        cut_of_phase = key[t]                    # weight from t to everything else
        if cut_of_phase < best:
            best, best_side = cut_of_phase, list(groups[t])
        # Merge t into s.
        groups[s].extend(groups.pop(t))
        active.remove(t)
        for u, c in w[t].items():
            if u != s:
                w[s][u] = w[s].get(u, 0) + c
                w[u][s] = w[s][u]
                del w[u][t]
        w[s].pop(t, None)
        w[t] = {}
    return best, sorted(best_side)


edges = [(0, 1, 3), (0, 2, 2), (1, 2, 4), (1, 3, 1),
         (2, 4, 1), (3, 4, 3), (3, 5, 2), (4, 5, 4)]
print(stoer_wagner(6, edges))   # (2, [3, 4, 5])

Two details deserve attention. The if not heap branch matters: in a disconnected graph the heap empties while vertices remain, and an early version of this code crashed there. Restarting from any unvisited vertex is correct, because that vertex's key is genuinely zero, and the phase then reports a cut of weight 0, which is the right answer for a disconnected graph. And groups tracks which original vertices each merged vertex represents; a union-find structure does the same job if you only need membership queries.

Cost and choice of priority queue

There are n-1 phases, and each phase is one priority-queue-driven ordering over the current graph, so the cost per phase depends on the queue:

Fibonacci heaps rarely win in practice; their constants are large, and a binary heap, explained in Priority Queues and Heaps, in depth, is usually faster. For dense graphs of a few thousand vertices, the array version over a weight matrix is simple and cache-friendly. Either way the V times E factor means Stoer-Wagner suits graphs of a few thousand vertices in Python and much more in compiled code, but not for graphs with hundreds of millions of edges.

Alternatives

Stoer-Wagner simplifies an earlier algorithm by Nagamochi and Ibaraki, which used a related ordering. Exact solvers for very large graphs add preprocessing that contracts edges provably not in any minimum cut before running an exact method, and they are the place to look if your graph is far beyond the sizes above.

Failure modes

The single-vertex problem is the one that surprises people using minimum cut for clustering. On real graphs, the cheapest cut very often just separates the vertex with the smallest weighted degree. That is the correct answer to the question asked, but rarely a useful cluster. If you want balanced parts, use an objective that penalises imbalance, such as normalised cut or a graph partitioner, and keep Stoer-Wagner for questions about fragility, such as the fewest links whose failure disconnects a network.

What to do next

1. Run the implementation above on the example graph and check that it prints a cut of 2 with side [3, 4, 5].
2. Add tracing to print each phase's order and cut of the phase, and reproduce the table by hand once.
3. Write a brute-force checker for graphs of up to ten vertices and compare it with your version on random graphs, including disconnected ones.
4. On your own data, compute the minimum weighted degree first; if the minimum cut equals it, you have found a weakly attached vertex, not a cluster boundary.
5. For graphs beyond a few hundred thousand edges, benchmark a compiled library or a max-flow-based method before scaling this one.
6. If your problem has a fixed source and sink, use an s-t max-flow algorithm instead; it is the simpler problem.