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

Relevant Files:

Click here for build and run instructions