Algorithm Deep Dive: Stoer-Wagner Algorithm

A Bit of History

Mechthild Stoer and Frank Wagner introduced their deterministic algorithm in the 1997 paper A Simple Min-Cut Algorithm. Its target is the global minimum cut of a non-negatively weighted, undirected graph: the cheapest partition into two non-empty sides, with no source and sink chosen in advance.

Before this approach, a standard exact strategy was to fix one vertex and solve a sequence of source–sink minimum-cut problems using max flow. Stoer–Wagner reaches the same global objective through a different idea: a greedy vertex ordering that certifies one pairwise minimum cut, followed by a contraction that reduces the graph without losing the answer.

What Is a Global Minimum Cut?

For a partition $(S, V\setminus S)$ with neither side empty, the cut consists of edges with one endpoint on each side. Its capacity is the sum of their weights:

$$w(\delta(S))=\sum_{u\in S,\;v\notin S} w(u,v).$$

A global minimum cut chooses both sides to minimize this sum. This differs from an $s$–$t$ cut, which must place a specified $s$ and $t$ on opposite sides. Global min-cut asks for the weakest separation anywhere in the network.

Boundary accounting. The crimson boundary crosses two edges, so its capacity is $4+1=5$. A global minimum-cut algorithm searches over all non-trivial partitions, not merely over individual edges.

undirected

Every edge works both ways

The standard theorem and contraction rule assume a symmetric graph. Directed global cut is a different problem.

w(e) ≥ 0

Greedy gains must be safe

Negative weights break the maximum-adjacency argument. Zero weights are allowed and can reveal a disconnected graph.

|V| ≥ 2

Both sides must exist

A global cut is undefined for fewer than two vertices. Isolated vertices make the optimum zero.

Algorithm Overview

Stoer–Wagner repeats a minimum-cut phase while more than one active vertex or super-vertex remains:

Grow a set $A$. Start from any active vertex. Repeatedly add the outside vertex with the largest total edge weight into $A$.
Read the phase cut. Let $s$ and $t$ be the second-last and last vertices added. At that moment, the total weight connecting $t$ to $A$ is the capacity of the cut separating $t$ from all earlier vertices.
Remember the best candidate. If this phase cut is lighter than every earlier one, store its weight and the original vertices represented by $t$.
Contract $s$ and $t$. Merge their represented vertex groups and add their incident weights to every remaining neighbor.
Repeat. After $|V|-1$ phases only one super-vertex remains; the lightest recorded phase cut is the global minimum.

Inside a Maximum-Adjacency Phase

For every unselected vertex $v$, maintain a gain

$$\operatorname{gain}(v)=\sum_{u\in A}w(u,v).$$

Each step selects the vertex with maximum gain, adds it to $A$, and increases every remaining neighbor's gain by the corresponding edge weight. This resembles Prim's algorithm with the preference reversed and with total attachment to the whole selected set rather than the best single connecting edge. Ties may be broken arbitrarily.

Why “Maximum” Search Finds a “Minimum” Cut

The search greedily absorbs vertices that are hardest to separate from the growing set. The final vertex is the one that remains least compelling to absorb until the end. The phase theorem makes this intuition exact: the final boundary is a minimum cut separating the last two vertices $s$ and $t$ in the current contracted graph.

Visual Walkthrough

Use the graph from the first figure and start at $A$. The gain values evolve as follows. A tie between $C$ and $D$ is broken in favor of $C$; choosing $D$ instead would also be valid.

The first phase does not need to find the global answer. It certifies a cut of weight $8$ separating $C$ and $D$, then safely merges them. Later phase cuts are $6$ and $5$, so the global minimum is the final partition ${A}\mid{B,C,D}$.

What Contraction Preserves

Contracting $s$ and $t$ means that later cuts may no longer separate them. Their original vertex groups are united, and for every remaining vertex $v$ the new edge weight is

$$w(st,v)=w(s,v)+w(t,v).$$

This sum preserves the capacity of every cut that keeps $s$ and $t$ on the same side. Self-loops created by the merge can be discarded because no cut crosses them. Parallel edges are represented by their summed weight.

The central bargain: the phase records the best cut that separates $s$ and $t$; contraction preserves every cut that keeps them together. Between those two cases, no possible global optimum disappears unnoticed.

Why the Algorithm Works

The proof has two layers.

Phase lemma: the last boundary is a minimum $s$–$t$ cut

Let $s$ and $t$ be the last two vertices added during maximum-adjacency search. The capacity separating $t$ from all earlier vertices equals gain[t]. The greedy ordering provides a charging argument: for any cut that separates $s$ from $t$, the weights crossing that cut can be compared with the gains of vertices as they enter the selected set. Because each selected vertex had maximum available gain, no such $s$–$t$ cut can be lighter than the final boundary. Therefore the phase cut is an exact minimum $s$–$t$ cut in the current graph.

Contraction invariant: an optimum is recorded or survives

Consider a global minimum cut in the current graph. If it separates $s$ and $t$, the phase lemma says the recorded phase cut is no heavier; since no cut is lighter than the global optimum, the two weights are equal. If it keeps $s$ and $t$ together, contraction preserves that cut exactly. Thus every phase either records a global optimum or carries one forward into the smaller graph. Induction over the contractions proves that the smallest recorded phase cut is the original graph's global minimum cut.

Complexity Analysis

The implementations below use an adjacency matrix and scan all active vertices to choose the next maximum-gain vertex. A phase on $k$ active vertices costs $O(k^2)$, and summing across all phases gives:

$$\text{Time: } O(V^3) \qquad \text{Space: } O(V^2).$$

With adjacency lists and a suitable priority queue, one phase can be implemented in $O(E+V\log V)$ amortized time using a Fibonacci heap, leading to $O(VE+V^2\log V)$ overall. The dense $O(V^3)$ form is often preferable for teaching and moderate dense graphs because it is compact, deterministic, and difficult to misuse.

Implementation

These versions return both the optimum weight and one side of an optimum partition. They copy the input before contracting, validate the matrix assumptions, track which original vertices each super-vertex represents, and use wide integer types where available.

def stoer_wagner(matrix):
    """Return (minimum_cut_weight, (side, complement))."""
    n = len(matrix)
    if n < 2:
        raise ValueError("a cut needs at least two vertices")
    if any(len(row) != n for row in matrix):
        raise ValueError("weight matrix must be square")

    for u in range(n):
        if matrix[u][u] != 0:
            raise ValueError("diagonal weights must be zero")
        for v in range(n):
            if matrix[u][v] < 0:
                raise ValueError("weights must be non-negative")
            if matrix[u][v] != matrix[v][u]:
                raise ValueError("graph must be undirected (symmetric)")

    weights = [list(row) for row in matrix]  # preserve caller's matrix
    active = list(range(n))
    groups = [{v} for v in range(n)]
    best_weight = float("inf")
    best_side = None

    while len(active) > 1:
        added = [False] * n
        gain = [0] * n
        previous = None

        for step in range(len(active)):
            # The -v tie-break makes examples deterministic; any tie is valid.
            selected = max(
                (v for v in active if not added[v]),
                key=lambda v: (gain[v], -v),
            )

            if step == len(active) - 1:
                t, s = selected, previous
                phase_weight = gain[t]
                if phase_weight < best_weight:
                    best_weight = phase_weight
                    best_side = set(groups[t])

                # Contract t into s.
                groups[s].update(groups[t])
                for v in active:
                    if v != s and v != t:
                        weights[s][v] += weights[t][v]
                        weights[v][s] = weights[s][v]
                active.remove(t)
                break

            added[selected] = True
            for v in active:
                if not added[v]:
                    gain[v] += weights[selected][v]
            previous = selected

    other_side = set(range(n)) - best_side
    return best_weight, (best_side, other_side)


graph = [
    [0, 4, 1, 0],
    [4, 0, 2, 3],
    [1, 2, 0, 5],
    [0, 3, 5, 0],
]

weight, partition = stoer_wagner(graph)
print(weight)       # 5
print(partition)    # ({1, 2, 3}, {0})

#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <stdexcept>
#include <vector>

struct CutResult {
    long long weight;
    std::vector<int> side;
};

CutResult stoerWagner(std::vector<std::vector<long long>> weights) {
    const int n = static_cast<int>(weights.size());
    if (n < 2) throw std::invalid_argument("need at least two vertices");
    for (const auto& row : weights)
        if (static_cast<int>(row.size()) != n)
            throw std::invalid_argument("matrix must be square");
    for (int u = 0; u < n; ++u) {
        if (weights[u][u] != 0)
            throw std::invalid_argument("diagonal weights must be zero");
        for (int v = 0; v < n; ++v) {
            if (weights[u][v] < 0 || weights[u][v] != weights[v][u])
                throw std::invalid_argument("weights must be non-negative and symmetric");
        }
    }

    std::vector<int> active(n);
    std::iota(active.begin(), active.end(), 0);
    std::vector<std::vector<int>> groups(n);
    for (int v = 0; v < n; ++v) groups[v] = {v};

    CutResult answer{std::numeric_limits<long long>::max(), {}};
    while (active.size() > 1) {
        std::vector<bool> added(n, false);
        std::vector<long long> gain(n, 0);
        int previous = -1;

        for (std::size_t step = 0; step < active.size(); ++step) {
            int selected = -1;
            for (int v : active) {
                if (!added[v] && (selected == -1 || gain[v] > gain[selected] ||
                                  (gain[v] == gain[selected] && v < selected))) {
                    selected = v;
                }
            }

            if (step + 1 == active.size()) {
                const int t = selected, s = previous;
                if (gain[t] < answer.weight) answer = {gain[t], groups[t]};

                groups[s].insert(groups[s].end(), groups[t].begin(), groups[t].end());
                for (int v : active) {
                    if (v != s && v != t) {
                        weights[s][v] += weights[t][v];
                        weights[v][s] = weights[s][v];
                    }
                }
                active.erase(std::find(active.begin(), active.end(), t));
                break;
            }

            added[selected] = true;
            for (int v : active)
                if (!added[v]) gain[v] += weights[selected][v];
            previous = selected;
        }
    }
    return answer;
}

int main() {
    std::vector<std::vector<long long>> graph = {
        {0, 4, 1, 0}, {4, 0, 2, 3},
        {1, 2, 0, 5}, {0, 3, 5, 0}
    };
    CutResult cut = stoerWagner(graph);
    std::cout << "minimum cut weight = " << cut.weight << '\n'; // 5
}

import java.util.*;

public class StoerWagner {
    static final class CutResult {
        final long weight;
        final List<Integer> side;
        CutResult(long weight, List<Integer> side) {
            this.weight = weight;
            this.side = side;
        }
    }

    static CutResult solve(long[][] matrix) {
        int n = matrix.length;
        if (n < 2) throw new IllegalArgumentException("need at least two vertices");
        for (long[] row : matrix)
            if (row.length != n) throw new IllegalArgumentException("matrix must be square");

        long[][] weights = new long[n][n];
        for (int u = 0; u < n; u++) {
            if (matrix[u][u] != 0) throw new IllegalArgumentException("diagonal must be zero");
            for (int v = 0; v < n; v++) {
                if (matrix[u][v] < 0 || matrix[u][v] != matrix[v][u])
                    throw new IllegalArgumentException("weights must be non-negative and symmetric");
                weights[u][v] = matrix[u][v];
            }
        }

        List<Integer> active = new ArrayList<>();
        List<List<Integer>> groups = new ArrayList<>();
        for (int v = 0; v < n; v++) {
            active.add(v);
            groups.add(new ArrayList<>(List.of(v)));
        }

        CutResult answer = new CutResult(Long.MAX_VALUE, List.of());
        while (active.size() > 1) {
            boolean[] added = new boolean[n];
            long[] gain = new long[n];
            int previous = -1;

            for (int step = 0; step < active.size(); step++) {
                int selected = -1;
                for (int v : active) {
                    if (!added[v] && (selected == -1 || gain[v] > gain[selected] ||
                                      (gain[v] == gain[selected] && v < selected))) {
                        selected = v;
                    }
                }

                if (step + 1 == active.size()) {
                    int t = selected, s = previous;
                    if (gain[t] < answer.weight)
                        answer = new CutResult(gain[t], new ArrayList<>(groups.get(t)));

                    groups.get(s).addAll(groups.get(t));
                    for (int v : active) {
                        if (v != s && v != t) {
                            weights[s][v] += weights[t][v];
                            weights[v][s] = weights[s][v];
                        }
                    }
                    active.remove(Integer.valueOf(t));
                    break;
                }

                added[selected] = true;
                for (int v : active)
                    if (!added[v]) gain[v] += weights[selected][v];
                previous = selected;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        long[][] graph = {
            {0, 4, 1, 0}, {4, 0, 2, 3},
            {1, 2, 0, 5}, {0, 3, 5, 0}
        };
        CutResult cut = solve(graph);
        System.out.println(cut.weight); // 5
        System.out.println(cut.side);   // [1, 2, 3]
    }
}

Choosing a Minimum-Cut Strategy

Method	What it finds	Guarantee	Best fit
Stoer–Wagner	Global cut in a non-negative weighted undirected graph	Deterministic and exact	Moderate graphs when no terminals are prescribed
One max-flow run	Minimum cut separating chosen $s$ and $t$	Deterministic and exact	A specific source–sink separation
Repeated max flow	Global undirected cut by fixing one source and trying every other sink	Exact	When a strong flow implementation already exists
Karger-style contraction	Global cut, classically in an undirected multigraph	Randomized; success amplified by repetition	Randomized algorithms, large sparse graphs, parallel trials

A Gomory–Hu tree is another option when the goal is richer: it compactly represents all-pairs minimum-cut values in an undirected weighted graph. Stoer–Wagner is focused—it returns one global optimum, not the entire cut structure.

Where Global Min-Cut Helps

Network vulnerability

Find the least total link capacity whose loss disconnects an undirected infrastructure model.

Circuit partitioning

Measure a cheapest unconstrained separation in weighted connectivity graphs used during layout exploration.

Cluster diagnostics

Detect a weak boundary in a similarity graph—while checking whether the result is merely one low-degree outlier.

Resilience auditing

Use the minimum-cut value as an edge-connectivity or capacity bottleneck indicator.

Graph preprocessing

Expose a fragile split before decomposition, routing, or reliability analysis.

Algorithm baselines

Provide a deterministic exact baseline for evaluating heuristics or randomized min-cut routines.

Limitations and Common Pitfalls

Pitfall	What goes wrong	Better practice
Passing a directed or asymmetric matrix	The phase and contraction theorems no longer apply.	Validate symmetry; use a directed-cut method when direction matters.
Allowing negative weights	Greedy maximum-adjacency reasoning can fail.	Require all weights to be non-negative.
Overwriting instead of adding on contraction	Cut capacities change after a merge.	Set $w(st,v)=w(s,v)+w(t,v)$.
Tracking only super-vertex IDs	The weight is correct, but the original partition is lost.	Maintain a set or list of original vertices for each super-vertex.
Using narrow integer types	Summed parallel weights can overflow even if individual edges fit.	Use Python integers or 64-bit integers and check application bounds.
Expecting a balanced split	Global min-cut often isolates one low-degree vertex.	Use normalized cut, conductance, or an explicit balance constraint when balance matters.
Treating image segmentation as automatic	The unconstrained global cut can produce a trivial tiny region.	Practical segmentation often uses seeded $s$–$t$ cuts or normalized objectives.
Ignoring disconnected input	A returned zero may be mistaken for a bug.	Recognize that a disconnected graph legitimately has global cut weight zero.

Minimum Does Not Mean Meaningful

Stoer–Wagner optimizes only total boundary weight. It has no preference for similarly sized sides, coherent geometry, or domain-specific semantics. A mathematically correct global cut may simply peel off a weakly connected vertex. Model the objective you actually care about.

Exercises

Reason About Phases and Contractions

Trace. Re-run the illustrated first phase but break the gain-$3$ tie in favor of $D$. What are the new final vertices $s,t$ and phase-cut weight?
Continue. Starting from the contracted graph ${A,B,CD}$, compute the next two phase cuts and recover the global partition.
Prove. Explain why adding parallel weights during contraction preserves every cut that keeps $s$ and $t$ together.
Break it. Find a small example showing why the minimum-weight single edge need not define the global minimum cut.
Test. Enumerate every non-trivial partition of random graphs with at most eight vertices and compare the brute-force optimum with the implementation.
Extend. Return both sides of the partition in C++ or Java and verify their crossing weight equals the reported optimum.

Hint for 1: after selecting $D$, the remaining gain of $C$ becomes $1+2+5=8$; the phase still records a valid minimum cut between the new final pair.

Cookie Consent

Stoer-Wagner Algorithm

Contents

A Bit of History

What Is a Global Minimum Cut?

Every edge works both ways

Greedy gains must be safe

Both sides must exist

Algorithm Overview

Inside a Maximum-Adjacency Phase

Why “Maximum” Search Finds a “Minimum” Cut

Visual Walkthrough

What Contraction Preserves

Why the Algorithm Works

Phase lemma: the last boundary is a minimum $s$–$t$ cut

Contraction invariant: an optimum is recorded or survives

Complexity Analysis

Implementation

Choosing a Minimum-Cut Strategy

Where Global Min-Cut Helps

Network vulnerability

Circuit partitioning

Cluster diagnostics

Resilience auditing

Graph preprocessing

Algorithm baselines

Limitations and Common Pitfalls

Minimum Does Not Mean Meaningful

Exercises

Reason About Phases and Contractions

Cookie Consent

Stoer-Wagner Algorithm

Contents

A Bit of History

What Is a Global Minimum Cut?

Every edge works both ways

Greedy gains must be safe

Both sides must exist

Algorithm Overview

Inside a Maximum-Adjacency Phase

Why “Maximum” Search Finds a “Minimum” Cut

Visual Walkthrough

What Contraction Preserves

Why the Algorithm Works

Phase lemma: the last boundary is a minimum $s$–$t$ cut

Contraction invariant: an optimum is recorded or survives

Complexity Analysis

Implementation

Choosing a Minimum-Cut Strategy

Where Global Min-Cut Helps

Network vulnerability

Circuit partitioning

Cluster diagnostics

Resilience auditing

Graph preprocessing

Algorithm baselines

Limitations and Common Pitfalls

Minimum Does Not Mean Meaningful

Exercises

Reason About Phases and Contractions

Related Deep Dives

Graph Theory Series

Part 15: Network Flow & Cuts

Karger's Min-Cut Algorithm