Random Contraction Algorithm

This algorithm was designed by Karger in 1990, as phd student at stanford. This algorithm is used to solve the min cut problem, which is :

Input - An undirected graph G = (V,E) ,  (note that parallel edges are allowed)
Goal - Tom compute a cut with fewest number of crossing edges (a min cut)

Karger's Algorithm
We will have just one mail loop, and algorithm terminates when only 2 vertices are remaining. This algorithm showed that random sampling can be extremely effective for graph problems.

We have only 1 while loop. Here we first randomly select edge, and when we see if it is edge, we will fuse the 2 vertices, and this may create parallel edge or self loop. Now, if it is self loop, we delete them.

while there are more than 2 vertices
{
  pick a remaining edge (u,v) uniformly at random
  merge or contract u and v into a single vertex
  remove self loops
}
return cut represented by final 2 vertices

Examples
Example 1 - Where Karger's algorithm works
Now let's see the example. Consider the following graph:

Now, lets take the edge (s,v) randomly to start with, and fuse it:

Now, we have 2 edges between s and t, and 4 edges overall. Suppose, we take upper parallel edge between and s and t nodes, which will s to t, and remove upper parallel edge, but create a self-loop of lower parallel edge between s and t. Also, we will have parallel edge between s and w:

Finally, we can remove 2 parallel edges between s and w, as we remove the self loop on s :

But, this being random algorithm, we will have different run, each time we run it, as it can randomly select any edge. Lets see example 2.

Example 2 - Where Karger's algorithm don't work
Lets again run the Karger's algorithm on the same graph:

Suppose we fuse s and v, like we did in example 1 :

Now, we have 2 parallel edges between s and t. But this time rather than choosing any parallel edge lets choose non parallel edge, say t-w:

Now, we are left with 2 nodes, which was condition for getting out of loop, but 3 edges as min cut, which is incorrect.

So, here we found out that Karger's algorithm may not work sometimes.

Probability of Success for Karger's algorithm
It is just 1/|V| for this algorithm, but some recent works have improved it by lot.
Proof of 1/|V| to come soon.

Running time
Running time - polynomial in |V| and |E|, though the brute force algorithm takes exponential algorithm, and there are better implementation of this.

Thanks.