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


Full Repo

Relevant Files: