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

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions