v. Global Minimum Cut

The cheapest way to split an undirected weighted graph into two non-empty parts, over all pairs. With unit weights it is the edge connectivity $\lambda (G)$. Fixing $s$ and running $n-1$ max flows works but is slow; write Stoer–Wagner.

Algorithm	Time	Notes
$n-1$ max flows from a fixed $s$	$n\cdot$ maxflow	also the only simple option for directed graphs: ${\min }_t(\text{cut}(s,t),\text{cut}(t,s))$, $2(n-1)$ flows
Stoer–Wagner (Nagamochi–Ibaraki)	$O(n^3)$ matrix, $O(nm+n^2\log n)$ heap	deterministic, write this
Karger contraction	$O(n^{2}m\log n)$ for high probability	the counting argument is the point
Karger–Stein	$O(n^2{\log }^{3}n)$	randomized recursion
Karger (tree packing), Kawarabayashi–Thorup	near-linear	not for contests

Stoer–Wagner

A maximum adjacency ordering adds, each step, the vertex with the largest total weight to the already-added set. The last vertex $t$ alone against everything else is a minimum $s$–$t$ cut for the last two vertices $s,t$; record it, merge $s$ and $t$, repeat.

pair<ll, vector<int>> stoerWagner(vector<vector<ll>> w) {   // symmetric matrix; returns {cut, one side}
    int n = sz(w); ll best = LLONG_MAX; vector<int> cut;
    vector<vector<int>> group(n); for (int i = 0; i < n; i++) group[i] = {i};
    for (int ph = 1; ph < n; ph++) {
        vector<ll> key = w[0]; vector<char> added(n); int s = 0, t = 0;
        for (int it = 0; it < n - ph; it++) {                // vertex 0 always survives and starts the ordering
            key[t] = LLONG_MIN; s = t;
            t = max_element(all(key)) - key.begin();
            for (int i = 0; i < n; i++) if (key[i] != LLONG_MIN) key[i] += w[t][i];
        }
        if (key[t] - w[t][t] < best) best = key[t] - w[t][t], cut = group[t];
        group[s].insert(group[s].end(), all(group[t]));
        for (int i = 0; i < n; i++) w[s][i] += w[t][i], w[i][s] = w[s][i];
        w[0][t] = LLONG_MIN;                                  // t is gone: never selected again
    }
    return {best, cut};
}

The merged vertex is removed by setting w[0][t] to $-\infty$, which seeds key[t] with $-\infty$ in later phases; adding finite weights never brings it back above real keys. With a heap and adjacency lists the same is $O(nm+n^2\log n)$.

Proof: the cut-of-the-phase lemma

Let $v_1,\dots ,v_n$ be the MA ordering, $s=v_{n-1}$, $t=v_n$, $A_i=\{v_1,\dots ,v_{i-1}\}$. Take any cut $C$ separating $s$ and $t$. Call $v_i$ active if $v_i$ and $v_{i-1}$ are on different sides of $C$; $t$ is active. For a vertex $v$ let $C_v$ be the weight of edges of $C$ inside $A_v\cup \{v\}$. Claim: $w(A_v,v)\le C_v$ for every active $v$.

For the first active $v$, all of $A_v$ is on one side and $v$ on the other, so $w(A_v,v)=C_v$. If $v$ is active and $u$ is the next active vertex, then
$w(A_u,u)=w(A_v,u)+w(A_u\setminus A_v,u)\le w(A_v,v)+w(A_u\setminus A_v,u)\le C_v+w(A_u\setminus A_v,u)\le C_u$.
The first inequality is the MA rule ($v$ was preferred over $u$ when $A_v$ had been added); the second is induction; the third holds because the vertices of $A_u\setminus A_v$ ($v$ up to the vertex before $u$) all lie on $v$‘s side while $u$ is on the other side, so these edges are cut edges counted in $C_u$ but not in $C_v$. With $u=t$: $w(A_t,t)\le C_t=w(C)$.

Global correctness: a global minimum cut either separates the current $s,t$ (then this phase’s cut is at most it) or keeps them together, and then it is a cut of the merged graph with the same weight. Induction on the number of vertices finishes.

Karger contraction and counting minimum cuts

Contract uniformly random edges (probability proportional to weight) until two super-vertices remain; the edges between them form a cut. A fixed minimum cut survives with probability at least ${\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^{-1}$, so $O(n^2\log n)$ runs succeed w.h.p.; a run is Kruskal on a random edge order.

Corollary: a graph has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ global minimum cuts (tight for a cycle), and at most $O(n^{2\alpha })$ cuts of weight $\le \alpha \lambda$.

Proof: survival probability and the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ bound

Let the minimum cut have weight $c$. When $i$ super-vertices remain, every super-vertex has weighted degree $\ge c$ (its star is a cut), so the total weight is $\ge ic/2$ and a random edge lies in the fixed cut with probability $\le c/(ic/2)=2/i$. Contraction never destroys a cut unless it contracts one of its edges, so survival has probability $\ge {\prod }_{i=3}^n(1-2/i)={\prod }_{i=3}^n\frac{i-2}{i}=\frac{2}{n(n-1)}$. The events “the run outputs cut $C$” are disjoint for distinct minimum cuts and each has probability $\ge {\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^{-1}$, so there are at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of them. Repeating $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ln n$ times fails with probability $\le (1-{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^{-1}{)}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ln n}\le 1/n$.

Karger–Stein

Contracting from $n$ to $t=\lceil 1+n/\sqrt{2}\rceil$ keeps a fixed minimum cut with probability $\ge t(t-1)/(n(n-1))\ge 1/2$: the danger is only at the end, so contract to $t$ twice independently and recurse on both. $T(n)=2T(n/\sqrt{2})+O(n^2)=O(n^2\log n)$, success probability $\Omega (1/\log n)$; repeat $O({\log }^{2}n)$ times.

mt19937_64 krng(1234567);
ll kargerStein(vector<vector<ll>> w) {                      // one run; repeat and take the minimum
    int n = sz(w);
    if (n <= 6) {
        ll best = LLONG_MAX;
        for (int mask = 1; mask < (1 << n) - 1; mask++) {
            ll c = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if ((mask >> i & 1) && !(mask >> j & 1)) c += w[i][j];
            best = min(best, c);
        }
        return best;
    }
    auto contract = [&](vector<vector<ll>> a, int t) -> vector<vector<ll>> {
        int m = sz(a); vector<ll> deg(m); vector<int> alive(m); iota(all(alive), 0);
        for (int i = 0; i < m; i++) deg[i] = accumulate(all(a[i]), 0LL);
        while (sz(alive) > t) {
            ll tot = 0; for (int v : alive) tot += deg[v];
            if (!tot) return {};                              // disconnected: the answer is 0
            ll r = uniform_int_distribution<ll>(0, tot - 1)(krng); int u = 0, v = 0;
            for (int x : alive) { if (r < deg[x]) { u = x; break; } r -= deg[x]; }
            r = uniform_int_distribution<ll>(0, deg[u] - 1)(krng);
            for (int x : alive) { if (r < a[u][x]) { v = x; break; } r -= a[u][x]; }
            deg[u] += deg[v] - 2 * a[u][v];
            for (int x : alive) a[u][x] += a[v][x], a[x][u] = a[u][x];
            a[u][u] = 0; alive.erase(find(all(alive), v));
        }
        vector<vector<ll>> b(t, vector<ll>(t));
        for (int i = 0; i < t; i++) for (int j = 0; j < t; j++) b[i][j] = a[alive[i]][alive[j]];
        return b;
    };
    int t = (int)ceil(1 + n / sqrt(2.0)); ll best = LLONG_MAX;
    for (int rep = 0; rep < 2; rep++) {
        auto b = contract(w, t);
        if (b.empty()) return 0;
        best = min(best, kargerStein(b));
    }
    return best;
}

Proof: Karger–Stein succeeds with probability $\Omega (1/\log n)$

Contracting from $n$ to $t$ keeps a fixed minimum cut with probability ${\prod }_{i=t+1}^n(1-2/i)=\frac{t(t-1)}{n(n-1)}\ge \frac{1}{2}$ for $t\ge 1+n/\sqrt{2}$. Let $p_k$ be a lower bound on the success probability at recursion height $k$ (leaves are exact, $p_0=1$). A branch succeeds with probability $\ge p_k/2$, and the two branches are independent, so $p_{k+1}\ge 1-(1-p_k/2{)}^2=p_k-p_k^2/4$. By induction $p_k\ge \frac{1}{k+1}$: $x-x^2/4$ is increasing on $[0,2]$, and $\frac{1}{k+1}-\frac{1}{4(k+1{)}^2}\ge \frac{1}{k+2}$ because $\frac{1}{(k+1)(k+2)}\ge \frac{1}{4(k+1{)}^2}$. The height is ${\log }_{\sqrt{2}}n=2{\log }_{2}n$, so one run succeeds with probability $\Omega (1/\log n)$, and the time recurrence solves to $O(n^2\log n)$ by the master theorem (two subproblems of size $n/\sqrt{2}$, $O(n^2)$ work, $a=b^2$).

Sparse certificates (Nagamochi–Ibaraki)

To decide cuts smaller than $k$, replace $G$ by the union of $k$ forests $F_1,\dots ,F_k$ where $F_j$ is a maximal spanning forest of $G-F_1-\cdots -F_{j-1}$. It has at most $k(n-1)$ edges and preserves every cut of size $<k$ exactly. Greedy one pass: put each edge into the first forest whose DSU does not yet connect its endpoints; connectivity is monotone in $j$, so binary search the forest. Use before $k$-edge-connectivity checks, small max flows, or Stoer–Wagner on dense multigraphs. (Nagamochi–Ibaraki obtain the same forests in $O(m)$ from one MA ordering.)

vector<int> sparseCertificate(int n, const vector<pair<int, int>>& E, int k) {   // ids of the kept edges
    vector<DSU> F(k, DSU(n)); vector<int> keep;
    for (int i = 0; i < sz(E); i++) {
        auto [u, v] = E[i]; int lo = 0, hi = k;              // first forest not connecting u and v
        while (lo < hi) { int mid = (lo + hi) / 2; if (F[mid].find(u) == F[mid].find(v)) lo = mid + 1; else hi = mid; }
        if (lo < k) F[lo].unite(u, v), keep.push_back(i);
    }
    return keep;
}

Proof: the certificate preserves all cuts below $k$

Monotonicity: the components of $F_{j+1}$ always refine those of $F_j$. An edge enters $F_j$ only when its endpoints are already connected in $F_{j-1}$, so it merges two $F_j$-components inside one $F_{j-1}$-component; merges in $F_{j-1}$ only coarsen the coarser partition. So “connected in $F_j$” is monotone in $j$ and the binary search finds the first forest where $u,v$ are separate. Maximality: an edge skipped by $F_j$ had its endpoints connected in $F_j$ at that moment, so each $F_j$ is a maximal forest of the edges that reached it. Cuts: let $(A,B)$ be a cut with $|{\delta }_H(A)|<k$ in $H=\bigcup F_j$. The forests are edge-disjoint, so some $F_j$ has no edge across the cut. Every discarded edge $(x,y)$ has $x,y$ connected in that $F_j$, hence on the same side. So ${\delta }_G(A)={\delta }_H(A)$. Since ${\delta }_H\le {\delta }_G$ always, $\min ({\delta }_H(A),k)=\min ({\delta }_G(A),k)$ for every cut.

Applications

Beyond raw edge connectivity: network reliability (the min cut is the bottleneck against random failure), clustering and community detection, image segmentation (min-cut partitioning of a pixel similarity graph), and circuit partitioning in VLSI design (minimising cross-partition wiring). Certificates (above) are maintained incrementally inside dynamic connectivity structures, and the same “sparsify before you compute” philosophy produced cut sparsifiers (Benczúr-Karger) and spectral sparsifiers (Spielman-Teng), preserving all cuts approximately within $1\pm \epsilon$ using $\tilde{O}(n/{\epsilon }^2)$ edges.