Karger's Min Cut — Randomized Contraction

Algorithm

int kargerMinCut(Graph g) {
  while (g.vertexCount() > 2) {
    Edge e = g.randomEdge();
    g.contract(e);
  }
  return g.remainingEdges();
}

Success probability

P[min cut survives all contractions] ≥ 2 / (n(n-1)). Repeat O(n² log n) times → high probability.

Complexity

Each run: O(V²). Total: O(V⁴ log V) for high probability answer.

Karger-Stein

Recursive variant: contract to √n/√2 vertices, recurse. O(V² log³ V) time, high probability.