Karger Random Contraction Algorithm

Because a minimum cut has fewer edges than a non-minimum cut, the Karger Random Contraction algorithm has a higher probability of producing a minimum cut than a non-minimum cut. The key concept here is that it has a higher probability of producing a minimum cut: it is not guaranteed to produce one.

The probability that random contraction produces a minimum cut is $\frac{2}{n(n-1)}$. In order to ensure that a minimum cut is produced, the algorithm should be run $n^2 \log n$ times. The smallest minimum cut found over all executions has a high probability of being an actual minimum cut. Description goes here

Asymptotic Complexity

$O(n^4 \log n)$

Pseudo Code

karger:
    G = input graph
    returns: minimum cut found over n^2 log n iterations

    min_cut = G

    repeat n^2 log (n) times:
        temp = copy of G

        while temp->n > 2:
            collapse random edge

        if min_cut < temp:
            min_cut = temp

   return min_cut

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions