Karger Min Cut, in depth: random edge contraction, the 1/C(n,2) bound, a union-find implementation, Karger-Stein and cut counting

The global minimum cut problem

Given a connected undirected graph G with n vertices and m edges, a cut is a partition of the vertices into two non-empty sets S and its complement, and its size is the number of edges with one end on each side. The global minimum cut is the smallest such size over all partitions. There is no source or sink: unlike the s-t version solved by max flow, any split counts.

The classical deterministic route fixes one vertex s, runs a max-flow computation from s to every other vertex t, and takes the smallest: n-1 flow computations, justified by the max-flow min-cut theorem because s must lie on one side of the global minimum cut and some t on the other. That is correct but heavy. Karger's insight is that a minimum cut has few edges by definition, so a random edge is unlikely to be one of them, and merging across a non-cut edge never destroys the cut.

Contraction and the multigraph rules

Contraction of an edge (u, v) replaces u and v by a single vertex uv. Every edge that went from u or v to some third vertex w now goes from uv to w. Two rules make the algorithm correct. First, parallel edges are kept: if both u and v were connected to w, the merged vertex has two edges to w, and the graph becomes a multigraph. Second, edges between u and v themselves become self-loops and are deleted, because they can never cross a cut.

Each super-vertex stands for a set of original vertices, so any cut of the contracted graph corresponds to exactly one cut of the original with the same number of crossing edges. Contraction can lose cuts, namely those that would separate u from v, but it cannot create new ones or change the size of surviving ones. After n-2 contractions two super-vertices remain, and the edges between them are a cut of G. It is a minimum cut whenever no edge of some fixed minimum cut C was contracted along the way.

Why it works: the success bound

Let the minimum cut C have k edges. Every vertex has degree at least k, since the edges at a single vertex form a cut. So a multigraph with i vertices has at least ik/2 edges, and this stays true after contractions because the minimum cut of a contracted graph can only grow. When i vertices remain, the probability that a uniformly random edge lies in C is at most k divided by ik/2, that is 2/i. The probability that C survives the step is therefore at least 1 - 2/i = (i-2)/i.

Multiply over the steps from i = n down to i = 3:

P(C survives) >= (n-2)/n * (n-3)/(n-1) * (n-4)/(n-2) * ... * 2/4 * 1/3
              =  2 / (n (n-1))
              =  1 / C(n, 2)

The product telescopes: every numerator cancels a denominator two places later, leaving 2 over n(n-1). That is small, about 1 in 4,950 for n = 100, so one run is nearly worthless on its own. Independence fixes it. A run that fails returns a cut that is too large, never too small, so the error is one-sided and the best of T independent runs is wrong only if all T runs fail:

P(all T runs miss) <= (1 - 1/C(n,2))^T  <=  exp(-T / C(n,2))

T = C(n,2) * ln n   ->  failure <= 1/n
T = C(n,2) * c ln n ->  failure <= 1/n^c

The same bound has a structural corollary. Each distinct minimum cut survives a run with probability at least 1/C(n,2), and these are disjoint events because a run outputs one cut. Probabilities of disjoint events sum to at most 1, so a graph has at most C(n,2) = n(n-1)/2 distinct minimum cuts. A cycle on n vertices meets the bound exactly: any two of its edges form a minimum cut.

Implementation with union-find

The natural implementation picks a random edge, merges, and rewrites adjacency lists, which is fiddly and slow. There is a cleaner equivalent. Shuffle the original edge list once and process it in that order with a union-find structure, skipping any edge whose endpoints are already in the same set: those are exactly the self-loops of the contracted graph. Conditioned on skipping loops, the next edge in a uniformly random order is a uniformly random non-loop edge, which is precisely Karger's rule. Stop when two sets remain. This is Kruskal's algorithm run on a random order, stopped one merge early.

import math
import random


def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path halving
        x = parent[x]
    return x


def contract_once(n, edges, rng):
    """One Karger run. edges: list of (u, v), parallel edges allowed as repeats.
    Returns (cut_size, side) with side the vertex set containing vertex 0."""
    parent, size, groups = list(range(n)), [1] * n, n
    order = edges[:]
    rng.shuffle(order)
    for u, v in order:
        if groups == 2:
            break
        ru, rv = find(parent, u), find(parent, v)
        if ru == rv:
            continue                    # self-loop in the contracted graph
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        groups -= 1
    if groups > 2:
        raise ValueError("graph is disconnected: the minimum cut is 0")
    root = find(parent, 0)
    side = {x for x in range(n) if find(parent, x) == root}
    cut = sum(1 for u, v in edges if (u in side) != (v in side))
    return cut, side


def karger_min_cut(n, edges, runs=None, seed=None):
    rng = random.Random(seed)
    if runs is None:
        runs = math.ceil(n * (n - 1) / 2 * math.log(n))   # failure <= 1/n
    best, best_side = math.inf, None
    for _ in range(runs):
        cut, side = contract_once(n, edges, rng)
        if cut < best:
            best, best_side = cut, side
    return best, best_side

One run costs O(m) for the shuffle and the final count plus near-constant amortised time per union-find operation, so about O(m α(n)). With the full C(n,2) ln n runs the total is O(n² m log n). The textbook adjacency-matrix version costs O(n²) per run and O(n⁴ log n) in total; the union-find form is faster on sparse graphs. The union-find article explains why the per-operation cost is effectively constant.

Weighted graphs, where an edge of weight w stands for w parallel edges, need sampling proportional to weight. Do not shuffle uniformly. Give each edge the key -math.log(1.0 - rng.random()) / w and sort by key ascending: this exponential-race trick produces an order in which each next non-loop edge is chosen with probability proportional to its weight, which is what the proof requires. The cut size becomes the sum of crossing weights.

Worked example: two cliques and two bridges

Take two four-vertex cliques, {0, 1, 2, 3} and {4, 5, 6, 7}, joined by two bridge edges 0-4 and 3-7. There are 14 edges. Each vertex has degree 3 or 4, so the cheapest single-vertex cut has size 3, while removing the two bridges splits the graph at cost 2. The minimum cut is 2 and is unique.

Trace one lucky run. Suppose the shuffled order begins 1-2, 5-6, 0-1, 4-5, 2-3, 6-7. Each of those merges two different sets, so after six merges the sets are {0, 1, 2, 3} and {4, 5, 6, 7}: two groups, so the loop stops. Counting crossing edges gives the two bridges, a cut of 2. An unlucky run would draw 0-4 early, merging across the bridge, after which the best this run can return is a larger cut, such as 3 when a degree-3 vertex ends up alone.

The bound says a single run succeeds with probability at least 2/(8 x 7), about 3.6 percent. Measured over 200,000 runs of the code above, the single-run success rate on this graph is about 21.6 percent; the other runs returned cuts from 3 up to 8. The bound is a worst case over all graphs, and graphs with one clear bottleneck are far kinder than that. The default of ceil(28 x ln 8) = 59 runs therefore drives failure here to about 0.784 to the 59th power, below one in a million, rather than the guaranteed 1/8.

Karger-Stein: sharing the safe early work

Look at where the failure probability comes from. The early contractions, with many vertices, are very safe: the chance of hitting the cut at step i is at most 2/i. Almost all of the risk is in the last few steps. Repeating the whole run wastes the safe early work. Karger and Stein (1996) share it instead: contract once down to about 1 + n/√2 vertices, where the minimum cut survives with probability at least one half, then branch into two independent recursive calls and keep the better answer.

def karger_stein(G):
    n = vertex_count(G)
    if n <= 6:
        return min_cut_by_repeated_contraction(G)    # small: brute force or many runs
    t = ceil(1 + n / sqrt(2))
    G1 = contract_randomly(G, down_to=t)            # independent random choices
    G2 = contract_randomly(G, down_to=t)
    return min(karger_stein(G1), karger_stein(G2))

The running time satisfies T(n) = 2 T(n/√2) + O(n²), which solves to O(n² log n) per call using an adjacency-matrix contraction. The success probability satisfies P(n) at least 1 - (1 - P(n/√2)/2)², which is Ω(1/log n): far better than 1/C(n,2). Repeating O(log² n) times gives high probability in O(n² log³ n) total, against O(n⁴ log n) for plain repetition with the matrix version.

Failure modes

• Deduplicating parallel edges. Collapsing the two ab-d edges into one after a contraction changes the distribution of the next random edge and the size of cuts. The probability argument fails silently, and the returned cut size can be wrong. Keep multiplicities, or use weights.
• Random vertex, then random neighbour. This is not a uniform random edge: edges at low-degree vertices are over-sampled, and those are often exactly the edges of small cuts. Sample edges, not vertices.
• Uniform sampling on a weighted graph. A heavy edge must be proportionally more likely to be contracted. Use the exponential keys above.
• Disconnected input. The minimum cut is 0 and union-find never gets down to two groups. Check connectivity first or handle the case, as the code does.
• Too few runs. Running a fixed 10 or 100 times regardless of n gives no guarantee on large graphs. Derive T from n and the failure probability you need.
• Correlated randomness. Reseeding every run with the same value, or parallel workers sharing a seed, turns T runs into one. Seed once per process and give workers independent streams.
• No cross-check. A minimum cut is hard to verify directly. In tests, compare against a deterministic algorithm on many random small graphs.

Trade-offs

Karger is a Monte Carlo algorithm: fast, simple, and correct with high but not certain probability. Stoer-Wagner is deterministic and runs in O(nm + n² log n) with a heap, which beats plain repeated Karger at any size and is the safer default when you need one exact answer with a certificate you can trust. Karger wins in other places: it is trivially parallel because runs are independent; the union-find form is a few dozen lines; it naturally samples many near-minimum cuts, which is useful when you want the set of fragile partitions rather than one; and its analysis underlies results in network reliability, where the near-minimum cuts dominate the probability that a graph disconnects. Karger-Stein closes much of the time gap for dense graphs at the price of a recursive implementation.

What to do next

1. Implement contract_once with union-find and test it against brute force on every graph with up to seven vertices.
2. Measure single-run success on your own graphs; it is usually far above the bound.
3. Choose T from n and the failure probability you can tolerate, not by habit.
4. Add weighted sampling with exponential keys if your edges carry capacities.
5. Cross-check against Stoer-Wagner in CI on random graphs.
6. If you need all minimum cuts, collect the distinct sides found across runs.