May 28, 2009 Leave a comment
In this post, we consider the min-cut problem. A min-cut is a cut of minimum size, i.e. the minimum number of edges whose removal disconnects the graph (also called edge connectivity). It is represented as (X, V-X) where X is a subset of V in the multi-graph G=(V, E). (Multigraph is a graph where parallel edges are allowed.)
Now, how do we find a min-cut? We’ll approach this through a randomized algorithm. It is very straightforward.
What we want ultimately is to have a partition of V into two disjoint vertex sets, X and V-X, where each of X and V-X is connected. With this in mind, we’ll proceed by successively decreasing the number of vertices in the graph, until only two vertex sets are left.
Select an edge of G uniformly at random. Contract the end points of this edge. That is, merge the 2 end points into one single vertex. If x and y are the 2 vertices merged into a new vertex, say z, then all edges of the form (v,x) and (v,y) are replaced by edges of the form (v,z). As we keep on contracting one edge after the other (edges chosen independently and uniformly at random), we will ultimately end up with just 2 vertex sets, i.e. a cut. (This takes n-2 iterations (|V| = n.), since each contraction reduces the number of vertices by one.)
Now, what is the guarantee that the cut produced is indeed a min-cut?
Assume that the original graph has a min-cut of size, k. Let K be the set of edges corresponding to one such min-cut.
We’ll find the probability that the cut obtained in the algorithm is K. For that to happen, no edge of K must be contracted in any of the iterations. Consider the first iteration.
The min-cut size is k. Hence, the degree of each of the vertices is at least k, implying that the total number of edges is at least n*k/2. The probability that an edge of K is contracted in the first iteration is at most k/ (n*k/2) = 2/n. Hence, the probability that no edge of K is contracted is at least 1- 2/n = (n-2)/n.
Now, consider the 2nd iteration. The number of vertices is n-1. Assume that the first iteration did not contract any edge of K. Therefore, K is a cut of this contracted graph, and is also a min-cut. Again all vertices have a degree of at least k, meaning that the number of edges is at least (n-1)k/2. Similarly, the probability that no edge of K is contracted in this iteration is at least (n-3)/(n-1).
Proceeding in the same manner, we get that the probability that no edge of K is contracted in any of the iterations is at least (n-2)* (n-3) *(n-4) …. 2*1 / n*(n-1) *(n-2) …4*3 = 2 / n*(n-1) = 1/C(n,2).
Now, this is a small probability. To improve the chances of obtaining K as our min-cut, we can run the algorithm multiple times.
Running time: The algorithm can be implemented in O(n^2) steps. Now, how is that possible for a multigraph which can possibly have any unlimited number of edges. The solution is to assign a weight to one of a set of parallel edges, equal to the number of parallel edges. This way the graph has effectively at most C(n,2) edges.
For more on the min-cut problem, see Ch. 10 of Randomized Algorithms by Motwani and Raghavan.