Karger's Min-Cut Algorithm

A Bit of History

David Karger introduced this randomized contraction algorithm in his 1993 Stanford PhD thesis and a related paper, showing — remarkably — that a purely random process could find the global minimum cut with high probability, in an algorithm dramatically simpler to state (though not necessarily faster in the worst case) than Stoer-Wagner's deterministic approach. Three years later, Karger and David Stein published the Karger-Stein algorithm (1996), a recursive refinement achieving near-optimal \(O(V^2 \log^3 V)\) expected running time — for years the fastest known algorithm for the global minimum cut problem.

Working Principle

The algorithm is disarmingly simple:

1. While more than 2 vertices remain: pick an edge uniformly at random from the current (multi-)graph.
2. Contract that edge — merge its two endpoints into a single vertex, keeping all other edges (including any resulting parallel edges/multi-edges, and removing only self-loops created by the contraction).
3. When exactly 2 vertices (super-vertices) remain, the multi-edges between them form a cut — its size is the number of parallel edges connecting them.

A single run of this process might land on a poor cut by bad luck — but running it many times independently and keeping the smallest cut found dramatically increases the chance of finding the true global minimum.

Worked Example

On a small graph with a "weak link" — two dense clusters of vertices connected by just 2 edges — a lucky random run will happen to only contract edges within each cluster, never touching the 2 bridging edges, until each cluster has collapsed to a single super-vertex; the final cut between them is then exactly those 2 original bridging edges — the true minimum cut. An unlucky run might instead contract one of the bridging edges early, merging the two clusters together and hiding the true minimum cut forever in that particular run — which is precisely why the algorithm must be repeated many times.

Why It Works (Probabilistically)

Karger's key insight is a clean probability bound: if the graph has \(n\) vertices and its global minimum cut has \(k\) edges, then a single run of the algorithm finds that specific minimum cut with probability at least \(\binom{n}{2}^{-1} = \frac{2}{n(n-1)}\). The argument: since every vertex must have degree \(\geq k\) (else a smaller cut would isolate it), the graph has at least \(nk/2\) edges — so the chance of randomly picking one of the \(k\) minimum-cut edges at any single contraction step is at most \(k / (nk/2) = 2/n\), and multiplying these small "avoid the cut" probabilities across all \(n-2\) contraction steps yields the stated bound.

Complexity Analysis

A single contraction run takes \(O(V)\) contraction steps, each doable in \(O(V)\) time with a simple implementation, giving \(O(V^2)\) per run. Repeating \(O(V^2 \log V)\) times for high-probability correctness:

$$\text{Time (basic Karger): } O(V^4 \log V) \qquad \text{Time (Karger-Stein, 1996): } O(V^2 \log^3 V)$$

The Karger-Stein refinement achieves its dramatically better bound by recursively contracting down to \(n/\sqrt{2}\) vertices (where the failure probability is still manageable) before branching into two independent recursive sub-runs, rather than repeating the entire process from scratch every single time.

Implementation

import random

def karger_min_cut(n, edges, trials=1000):
    """
    n: number of vertices (0-indexed). edges: list of (u, v) pairs (a simple graph;
    parallel edges represented as duplicate entries).
    Returns the smallest cut size found across `trials` independent random runs.
    """
    best = float('inf')

    for _ in range(trials):
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        remaining_edges = list(edges)
        random.shuffle(remaining_edges)
        components = n
        i = 0
        while components > 2:
            u, v = remaining_edges[i]
            i += 1
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv
                components -= 1

        cut_size = sum(1 for u, v in edges if find(u) != find(v))
        best = min(best, cut_size)

    return best

edges = [(0,1), (0,2), (1,2), (2,3), (3,4), (3,5), (4,5)]
print(karger_min_cut(6, edges))  # 1 (the bridge edge 2-3)

#include <vector>
#include <algorithm>
#include <random>
#include <numeric>
#include <iostream>
using namespace std;

int findSet(vector<int>& parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}

int kargerMinCut(int n, vector<pair<int,int>> edges, int trials = 1000) {
    int best = INT_MAX;
    random_device rd;
    mt19937 rng(rd());

    for (int t = 0; t < trials; t++) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        vector<pair<int,int>> shuffled = edges;
        shuffle(shuffled.begin(), shuffled.end(), rng);

        int components = n, i = 0;
        while (components > 2) {
            int u = shuffled[i].first, v = shuffled[i].second;
            i++;
            int ru = findSet(parent, u), rv = findSet(parent, v);
            if (ru != rv) { parent[ru] = rv; components--; }
        }

        int cutSize = 0;
        for (auto& e : edges) {
            if (findSet(parent, e.first) != findSet(parent, e.second)) cutSize++;
        }
        best = min(best, cutSize);
    }
    return best;
}

int main() {
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,2},{2,3},{3,4},{3,5},{4,5}};
    cout << kargerMinCut(6, edges) << endl;  // 1
    return 0;
}

import java.util.*;

class Karger {
    static int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    static int minCut(int n, List<int[]> edges, int trials) {
        int best = Integer.MAX_VALUE;
        Random rng = new Random();

        for (int t = 0; t < trials; t++) {
            int[] parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
            List<int[]> shuffled = new ArrayList<>(edges);
            Collections.shuffle(shuffled, rng);

            int components = n, idx = 0;
            while (components > 2) {
                int u = shuffled.get(idx)[0], v = shuffled.get(idx)[1];
                idx++;
                int ru = find(parent, u), rv = find(parent, v);
                if (ru != rv) { parent[ru] = rv; components--; }
            }

            int cutSize = 0;
            for (int[] e : edges) {
                if (find(parent, e[0]) != find(parent, e[1])) cutSize++;
            }
            best = Math.min(best, cutSize);
        }
        return best;
    }

    public static void main(String[] args) {
        List<int[]> edges = Arrays.asList(
            new int[]{0,1}, new int[]{0,2}, new int[]{1,2},
            new int[]{2,3}, new int[]{3,4}, new int[]{3,5}, new int[]{4,5}
        );
        System.out.println(minCut(6, edges, 1000));  // 1
    }
}

Real-World Applications

Exercises

1. Run the provided implementation on a small graph with an obvious "weak bridge" edge, and verify across multiple executions that it reliably finds the correct minimum cut.
2. Explain in your own words why the per-run success probability bound \(\frac{2}{n(n-1)}\) gets worse (smaller) as \(n\) grows, and why repeated trials are therefore essential rather than optional.
3. Compare Karger's algorithm to Stoer-Wagner's: which is deterministic, and which trades a probabilistic guarantee for dramatically simpler logic?
4. Challenge: Research the Karger-Stein recursive refinement and explain, at a high level, why contracting only down to \(n/\sqrt{2}\) vertices before recursing (rather than all the way to 2) improves the overall running time so significantly.

Limitations