Karger-Stein Algorithm

Purpose: Find the global minimum cut of an undirected weighted graph in $O(n^2{\log }^{3}n)$ with high probability — a large improvement over running plain Karger’s contraction $O(n^2\log n)$ times.

The Insight

Karger’s basic algorithm contracts random edges until two vertices remain. A specific minimum cut survives all contractions with probability $\ge {\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^{-1}=\Omega (1/n^2)$, so you must repeat $O(n^2\log n)$ times — that is where the cost lies.

But look at where the failure happens. The probability that a given min cut survives contraction from $n$ down to $t$ vertices is

${\prod }_{i=t+1}^n\left(1-\frac{2}{i}\right)=\frac{t(t-1)}{n(n-1)}\approx \frac{t^2}{n^2}.$

Contracting to $t=n/\sqrt{2}$ succeeds with probability about $\frac{1}{2}$ — the early contractions are almost free of risk; only the last few are dangerous. So: contract cheaply down to $n/\sqrt{2}$, then recurse twice to give the risky part two independent chances.

Algorithm

MinCut(G):
    if |V(G)| <= 6:
        return brute-force minimum cut
    t = ceil(1 + |V(G)| / sqrt(2))
    G1 = contract G randomly down to t vertices
    G2 = contract G randomly down to t vertices     (independent)
    return min(MinCut(G1), MinCut(G2))

Complexity

$T(n)=2T\left(\frac{n}{\sqrt{2}}\right)+O(n^2)=O(n^2\log n)$

per run, with success probability $\Omega (1/\log n)$. Repeating $O({\log }^{2}n)$ times gives a high-probability result in

$O(n^2{\log }^{3}n).$

Compare: $n^2\log n$ repetitions of basic Karger cost $O(n^4\log n)$.

Solving the recurrence for success probability

Let $P(n)$ be the success probability. Each branch succeeds if the contraction preserves the cut (probability $\approx 1/2$) and the recursive call succeeds:

$P(n)=1-{\left(1-\frac{1}{2}P\left(\frac{n}{\sqrt{2}}\right)\right)}^2.$

Substituting $P(n)=1/(1+c\log n)$ shows this solves to $P(n)=\Omega (1/\log n)$ — the doubling exactly compensates for the halving.

Comparison of min-cut algorithms

Algorithm	Time	Type
$n-1$ max-flow runs	$O(n\cdot \mathrm{maxflow})$	deterministic
Stoer-Wagner	$O(nm+n^2\log n)$	deterministic, simple
Karger	$O(n^4\log n)$	randomized
Karger-Stein	$O(n^2{\log }^{3}n)$	randomized
Nagamochi-Ibaraki	$O(nm+n^2\log n)$	deterministic
Karger 2000 (tree packing)	$O(m{\log }^{3}n)$	randomized, near-linear

For a contest

Write Stoer-Wagner. It is deterministic, about 30 lines, and $O(n^3)$ is fine for the $n\le 500$ that global-min-cut problems use. Karger-Stein is here for the beautiful recursion, not the leaderboard.

Variants / Use Cases

• Counting minimum cuts — a corollary of Karger’s analysis is that a graph has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ minimum cuts, and Karger-Stein can enumerate them
• Approximate min cuts — the same analysis bounds the number of cuts within a factor $\alpha$ by $O(n^{2\alpha })$
• Karger’s algorithm — the base contraction procedure
• Global Min Cut — the topic page
• Network reliability, clustering, image segmentation — where global min cuts appear