Karger's Minimum Cut

Karger's Minimum Cut is a beautiful randomized algorithm: instead of cleverly searching for the smallest cut in a graph, it just keeps merging random edges and trusts probability. Run it enough times and the smallest cut you saw is almost certainly the true minimum.

The slow way first

You could try every possible way to split the vertices into two groups and count the crossing edges for each. With n vertices that is 2^n partitions to check — exponential, and hopeless for anything but tiny graphs. Max-flow / min-cut algorithms do better, but they are heavier to implement. Karger asks a different question: can randomness do the work for us?

The idea: contract random edges

Pick an edge at random and contract it — glue its two endpoints into a single super-vertex. Any edge that now connects the super-vertex to itself (a self-loop) is thrown away; parallel edges between the same pair are kept. Repeat until only two vertices remain. Whatever edges still run between those two final groups are a cut, and its size is just the number of those edges.

A single run can be unlucky and contract an edge that belonged to the true minimum cut, giving too large an answer. The fix is simple: run the whole thing many times and keep the smallest cut seen. The probability any one run finds the real minimum is at least 1 / (n choose 2), so O(n^2 log n) runs make failure vanishingly unlikely.

Walk through it

Step through the animation. We pick edge A-C and merge them into {A,C}; the A-C edge becomes a self-loop and is dropped. Next we contract an edge between {A,C} and B, merging into {A,C,B}. Now only {A,C,B} and D remain, and the two edges still crossing — B-D and C-D — are the cut. Cut size = 2.

Pseudocode

while more than 2 vertices remain:
    pick an edge (u, v) uniformly at random
    contract it: relabel every v as u (merge the two vertices)
    delete any self-loops (edges from u to u)
the cut size = number of edges left between the final two vertices
repeat the whole run many times, keep the smallest cut found

The Python solution

import random
 
def karger_min_cut(graph):       # graph: list of [u, v] edges
    nodes = unique_vertices(graph)
    while len(nodes) > 2:
        u, v = random.choice(graph)   # pick a random edge
        merge(v, into=u)              # contract: relabel v as u
        graph = [e for e in graph if e[0] != e[1]]  # drop self-loops
        nodes.discard(v)
    return len(graph)                # surviving edges = cut size

• nodes tracks how many distinct vertices are still left.
• random.choice(graph) picks an edge uniformly at random — this is where the randomness lives.
• merge(v, into=u) rewrites every endpoint v as u, gluing the two vertices into one.
• The list comprehension drops self-loops (e[0] == e[1]) created by the merge, but keeps parallel edges.
• When only two vertices remain, every edge left is a crossing edge, so len(graph) is the cut size for this run.

Complexity

The single run is cheap; the cost comes from repeating it enough times to make the answer reliable. Each run succeeds with probability at least 1 / (V choose 2), so O(V^2 log V) runs drive the failure probability to near zero.

When this pattern shows up

Practice