随机算法 (Fall 2011)/Randomized Min-Cut

From EtoneWiki
Jump to: navigation, search

Let be a graph. Suppose that we want to partition the vertex set into two parts and such that the number of crossing edges, edges with one endpoint in each part, is as small as possible. This can be described as the following problem: the min-cut problem.

For a connected graph , a cut is a set of edges, removal of which causes becomes disconnected. The min-cut problem is to find the cut with minimum cardinality. A canonical deterministic algorithm for this problem is through the max-flow min-cut theorem. A global minimum cut is the minimum - min-cut, which is equal to the minimum - max-flow.

Do we have to rely on the "advanced" tools like flows? The answer is "no", with a little help of randomness.

Karger's Min-Cut Algorithm

We will introduce an extremely simple algorithm discovered by David Karger. The algorithm works on multigraphs, graphs allowing multiple edges between vertices.

We define an operation on multigraphs called contraction: For a multigraph , for any edge , let be a new multigraph constructed as follows: and in are replaced by a singe new vertex whose neighbors are all the old neighbors of and . In other words, and are merged into one vertex. The old edges between and are deleted.

Karger's min-cut algorithm is described as follows:

MinCut(multigraph )

  • while do
    • choose an edge uniformly at random;
    • ;
  • return the edges between the only two vertices in ;

A better way to understand Karger's min-cut algorithm is to describe it as randomly merging sets of vertices. Initially, each vertex corresponds to a singleton set . At each step, (1) a crossing edge (edge whose endpoints are in different sets) is chosen uniformly at random from all crossing edges; and (2) the two sets connected by the chosen crossing-edge are merged to one set. Repeat this process until there are only two sets. The crossing edges between the two sets are returned.


Analysis

For a multigraph , fixed a minimum cut (there might be more than one minimum cuts), we analyze the probability that is returned by the MinCut algorithm. is returned by MinCut if and only if no edge in is contracted during the execution of MinCut. We will bound this probability .

Lemma 1
Let be a multigraph with vertices, if the size of the minimum cut of is , then .
Proof.
It holds that every vertex has at least neighbors, because if there exists with neighbors, then the edges adjacent to disconnect from the rest of , forming a cut of size smaller than . Therefore .
Lemma 2
Let be a multigraph with vertices, and a minimum cut of . If , then is still a minimum cut of .
Proof.
We first show that no edge in is lost during the contraction. Due to the definition of contraction, the only edges removed from in a contraction are the parallel-edges sharing both endpoints with . Since , none of these edges can be in , or otherwise cannot be a minimum cut of . Thus every edge in remains in .
It is then obvious to see that is a cut of . All paths in a contracted graph can be revived in the original multigraph by inserting the contracted edges into the path, thus a connected would imply a connected , which contradicts that is a cut in .
Notice that a cut in a contracted graph must be a cut in the original graph. This can be easily verified by seeing contraction as taking the union of two sets of vertices. Therefore a contraction can never reduce the size of minimum cuts of a multigraph. A minimum cut must still be a minimum cut in the contracted graph as long as it is still a cut.
Concluding the above arguments, we have that is a minimum cut of for any .

Let be a multigraph, and a minimum cut of .

Initially . After contractions, denote the current multigraph as . Suppose that no edge in has been chosen to be contracted yet. According to Lemma 2, must be a minimum cut of the . Then due to Lemma 1, the current edge number is . Uniformly choosing an edge to contract, the probability that the th contraction contracts an edge in is given by:

Therefore, assuming that is intact after contractions, the probability that survives the th contraction is at least . Note that , because each contraction decrease the vertex number by 1.

The probability that no edge in the minimum cut is ever contracted is:

Therefore, we prove the following theorem,

Theorem
For any multigraph with vertices, the MinCut algorithm returns a minimum cut with probability at least .

Run MinCut independently for times and return the smallest cut returned. The probability that this the minimum cut is found is:

A constant probability!