# Karger-Stein Random Contraction Algorithm

The Karger-Stein random contraction algorithm significantly improves the runtime of the Karger algorithm by decreasing the number of iterations required to produce a minimum cut with a high probability of correctness. The basic concept is that the probability of collapsing an incorrect edge gets higher as the number of edges decreases. Thus reducing the number of edges to $\frac{n + 1}{\sqrt 2}$ and reusing the pre-reduced result greatly reduces the number of required iterations. This is much easier to grasp by examining the pseudo code.

## Asymptotic Complexity

$O(n^2 \log n)$

## Pseudo Code

karger-stein-recursive:
G = input graph
returns: minimum cut

if n <= 6:
return karger(G)

t = n + 1 / square root 2
while n > t:
collapse random edge

G1 = karger-stein-recursive(G)
G2 = karger-stein-recursive(G)

return the min of G1 and G2

karger-stein:
G = input graph
returns: minimum cut found over n*log n / n - 1 iterations

min_cut = G

repeat n*log n / n-1  times:
temp = karger-stein-recursive(G)

if min_cut < temp:
min_cut = temp

return min_cut


Full Repo

Relevant Files: