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.