Global Min Cut

The global minimum cut is the cheapest way to split a graph into two non-empty parts — minimised over all pairs, not a fixed $s$ and $t$.

Naive: fix one endpoint

Fix any vertex $s$; the min cut separates $s$ from some $t$. So $n-1$ max-flow runs suffice: $O(n\cdot \text{maxflow})$. Correct, but wasteful.

Stoer-Wagner — the one to write

$O(nm+n^2\log n)$, deterministic, about 30 lines. See Stoer-Wagner.

The idea. Build a maximum adjacency ordering $v_1,\dots ,v_n$: repeatedly add the vertex most strongly connected to the already-chosen set. Then the cut $\{v_n\}$ vs the rest is a minimum $v_{n-1}$-$v_n$ cut. Record its weight, merge $v_{n-1}$ and $v_n$, and repeat $n-1$ times. The best cut seen is the global minimum.

// O(n^3) adjacency-matrix version; fine for n <= 500
pair<long long, vector<int>> stoerWagner(vector<vector<long long>> w) {
    int n = w.size();
    vector<vector<int>> group(n);
    for (int i = 0; i < n; i++) group[i] = {i};
    vector<int> alive(n); iota(alive.begin(), alive.end(), 0);
 
    long long best = LLONG_MAX; vector<int> bestGroup;
    while (alive.size() > 1) {
        vector<long long> wsum(n, 0);
        vector<bool> added(n, false);
        int prev = -1, last = -1;
        for (size_t i = 0; i < alive.size(); i++) {
            int sel = -1;
            for (int v : alive)
                if (!added[v] && (sel == -1 || wsum[v] > wsum[sel])) sel = v;
            added[sel] = true;
            prev = last; last = sel;
            for (int v : alive) if (!added[v]) wsum[v] += w[sel][v];
        }
        if (wsum[last] < best) { best = wsum[last]; bestGroup = group[last]; }
        // merge last into prev
        for (int v : alive) { w[prev][v] += w[last][v]; w[v][prev] = w[prev][v]; }
        group[prev].insert(group[prev].end(), group[last].begin(), group[last].end());
        alive.erase(find(alive.begin(), alive.end(), last));
    }
    return {best, bestGroup};
}

The algorithms

Algorithm	Time	Type
$n-1$ max flows	$O(n\cdot \text{maxflow})$	deterministic
Stoer-Wagner	$O(nm+n^2\log n)$	deterministic — use this
Nagamochi-Ibaraki	$O(nm+n^2\log n)$	deterministic
Karger	$O(n^4\log n)$	randomized
Karger-Stein	$O(n^2{\log }^{3}n)$	randomized
Karger 2000 (tree packing)	$O(m{\log }^{3}n)$	randomized, near-linear
Reif (planar)	$O(n\log \log n)$	planar graphs only

Directed graphs

Everything above assumes undirected. For a directed global min cut, fix a vertex $s$ and compute ${\min }_t(\text{mincut}(s,t),\text{mincut}(t,s))$ over all $t$ — $2(n-1)$ max-flow runs. Stoer-Wagner does not apply.

Gomory-Hu tree — all pairs at once

The Gomory-Hu tree is a weighted tree on the same vertices such that, for every pair $(u,v)$, the minimum $u$-$v$ cut equals the minimum edge weight on their tree path. It is built with only $n-1$ max-flow computations, and after that all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairwise min cuts are path-min queries — a remarkable compression.

Counting min cuts

Karger’s analysis implies a graph has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ distinct global minimum cuts, and this is tight (a cycle achieves it). More generally, the number of cuts within a factor $\alpha$ of the minimum is $O(n^{2\alpha })$.

Typical problems

• “Minimum cost to split a network into two pieces”
• Clustering / community detection
• Network reliability — the min cut is the bottleneck against failure
• Edge connectivity $\lambda (G)$ — the global min cut with unit capacities

See also: Minimum Cut · Stoer-Wagner · Gomory-Hu