the contraction algorithm uses randomization, so it will guarantee the result only with a certain probability, less than 1, but it can be made arbitrarily close to 1
the algorithm works as follows:
- pick an edge (v, w) uniformly at random among all edges from the current graph G
- contract the selected edge (i.e. merge its endpoints). keep the resulting parallel edges, but remove the self-loops. The contracted graph, denoted by G/(v,w), will be the new value of G
- repeat steps 1 and 2 until there are only 2 nodes left
- the set of edges between the remaining 2 nodes form a cut
the obtained cut will be a minimum cut with probability at least 1/n2 in a graph of n nodes.
If we repeat the algorithm K times independently and choose the smallest of the found cuts, say C, then the following holds:
P(C is not a minimum cut) ≤ (1 - 1/n²)ᴷ
If K is chosen as K = tn2, then the above probability will be approximately e-t, which is very small already for moderate values of t
An interesting by-product of this algorithm is the theorem that the number of minimum cuts in a graph is a t most n2, since each arises with at least 1/n2 probability in a run and these are mutually exclusive events. Note that the total number of different cuts may be exponentially large, but only at most n2 of them can be minimum (actually, n2 is only an upper bound, the precise tight bound is n(n-1)/2)