Karger's Min-Cut Algorithm

A randomized contraction algorithm that finds a global minimum cut of an undirected graph with high probability.

Global min cut by contraction

Karger's algorithm finds the global minimum cut of an undirected graph, the smallest set of edges whose removal disconnects the graph, using random edge contraction. Unlike s-t min cut, there is no fixed source and sink; the goal is the cheapest split of the whole graph into two non-empty parts.

The contraction step

Kronos motion — classical

Repeatedly pick a random edge and contract it, merging its two endpoints into one vertex and removing self-loops (parallel edges are kept). After n-2 contractions, two vertices remain, and the edges between them form a cut. That cut is the minimum with probability at least 2/(n*(n-1)), because a specific minimum cut survives every contraction only if no crossing edge is ever picked.

One trial

python

import random

def contract(edges, n):
    parent = list(range(n))
    def find(x):
        while parent[x] != x: x = parent[x]
        return x
    count = n
    while count > 2:
        u, v = random.choice(edges)
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            count -= 1
    return sum(1 for u, v in edges if find(u) != find(v))

Boosting the probability

A single run succeeds with probability about 2/n^2, so running it O(n^2 log n) times and keeping the smallest cut found makes failure exponentially unlikely, giving O(n^4 log n) overall. Karger-Stein improves this dramatically to O(n^2 log^3 n) by recursing: contract only partway, then branch, since early contractions are safe and late ones are risky.

Contrast

Deterministic global min cut: the Stoer-Wagner algorithm in O(V*E + V^2 log V).
Karger uses union-find for contraction bookkeeping.
A clean example of a Monte Carlo algorithm: fast, occasionally wrong, boosted by repetition.