随机算法 (Fall 2015)/Min-cut

From EtoneWiki
Jump to: navigation, search

Min-Cut in a Graph

Let be a multi-graph, which allows parallel edges between two distinct vertices and but does not allow any self-loop, i.e. an edge connect a vertex to itself. Such a multi-graph can be represented as data structures like adjacency matrix , where is symmetric (undirected graph) with zero diagonal, and each entry is a nonnegative integer giving the number of edges between vertices and .

A cut in a multi-graph is an edge set , which can be equivalently defined as

  • there exists a nonempty , such that ; or
  • removing of disconnects , that is, disconnects.

The min-cut or minimum cut problem is defined as follows:

  • Input: a multi-graph ;
  • Output: a cut in with the minimum size .

The problem itself is well-defined on simple graph (without parallel edges), and our main goal is indeed solving the min-cut in simple graphs, however, as we shall see the algorithm creates parallel edges during its running, even though we start with a simple graph without parallel edges.

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.

Karger's Min-Cut Algorithm

We will introduce a very simple and elegant algorithm discovered by David Karger.

We define an operation on multi-graphs called contraction: For a multigraph , for any edge , let be a new multigraph obtained by:

  • replacing the vertices and by a new vertex ;
  • for each replacing any edge or by the edge ;
  • removing all parallel edges between and in ;
  • the rest of the graph remains unchanged.

To conclude, the operation merges the two vertices and into a new vertex which maintains the old neighborhoods of both and except for that all the parallel edges between and are removed.

Perhaps a better way to look at contraction is to interpret it as union of equivalent classes of vertices. Initially every vertex is in a dinstinct equivalent class. Upon call a , the two equivalent classes corresponding to and are unioned together, and only those edges crossing between different equivalent classes are counted as valid edges in the graph.

RandomContract (Karger 1993)
while do
  • choose an edge uniformly at random;
  • ;
return (the parallel edges between the only remaining vertices in );

A multi-graph can be maintained by appropriate data strucrtures such that each contraction takes time, where is the number of vertices, so the algorithm terminates in time . We leave this as an exercise.

Analysis of accuracy

For convenience, we assume that each edge has a unique "identity" . And when an edge is contracted to new vertex , and each adjacent edge of (or adjacent edge of ) is replaced by , the identity of the edge (or ) is transfered to the new edge replacing it. When referring a cut , we consider as a set of edge identities , so that a cut is changed by the algorithm only if some of its edges are removed during contraction.

We first prove some lemma.

Lemma 1
If is a cut in a multi-graph and , then is still a cut in .
Proof.

It is easy to verify that is a cut in if none of its edges is lost during the contraction. Since is a cut in , there exists a nonempty vertex set and its complement such that . And if , it must hold that either or where and are the subgraphs induced by and respectively. In both cases none of edges in is removed in .

Lemma 2
The size of min-cut in is at least as large as the size of min-cut in , i.e. contraction never reduces the size of min-cut.
Proof.
Note that every cut in the contracted graph is also a cut in the original graph .
Lemma 3
If is a min-cut in a multi-graph , then .
Proof.
It must hold that the degree of each vertex is at least , or otherwise the set of adjacent edges of forms a cut which separates from the rest of and has size less than , contradicting the assumption that is a min-cut. And the bound follows directly from the fact that every vertex in has degree at least .

For a multigraph , fixed a minimum cut (there might be more than one minimum cuts), we analyze the probability that is returned by the above algorithm.

Initially . We say that the min-cut "survives" a random contraction if none of the edges in is chosen to be contracted. After contractions, denote the current multigraph as . Supposed that survives the first contractions, according to Lemma 1 and 2, must be a minimum cut in the current multi-graph . Then due to Lemma 3, 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, conditioning on that survives the first 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:

This gives the following theorem.

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

Run RandomContract independently for times and return the smallest cut returned. The probability that a minimum cut is found is at least:

A constant probability!

A Corollary by the Probabilistic Method

Karger's algorithm and its analysis implies the following combinatorial theorem regarding the number of distinct minimum cuts in a graph.

Corollary
For any graph of vertices, the number of distinct minimum cuts in is at most .
Proof.

For each minimum cut in , we define to be the event that RandomContract returns . Due to the analysis of RandomContract, . The events are mutually disjoint for distinct and the event that RandomContract returns a min-cut is the disjoint union of over all min-cut . Therefore,

which must be no greater than 1 for a well-defined probability space. This means the total number of min-cut in must be no greater than .

Note that the statement of this theorem has no randomness at all, however the proof involves a randomized algorithm. This is an example of the probabilistic method.

Fast Min-Cut

In the analysis of RandomContract, we have the following observation:

  • The probability of success is only getting worse when the graph becomes small.

This motivates us to consider the following alternation to the algorithm: first using random contractions to reduce the number of vertices to a moderately small number, and then recursively finding a min-cut in this smaller instance. This seems just a restatement of exactly what we have been doing. Inspired by the idea of boosting the accuracy via independent repetition, here we apply the recursion on two smaller instances generated independently.

The algorithm obtained in this way is called FastCut. We first define a procedure to randomly contract edges until there are number of vertices left.

RandomContract
while do
  • choose an edge uniformly at random;
  • ;
return ;

The FastCut algorithm is recursively defined as follows.

FastCut
if then return a mincut by brute force;
else let ;
;
;
return the smaller one of and ;

As before, all are multigraphs.

Let be a min-cut in the original multigraph . By the same analysis as in the case of RandomContract, we have

When , this probability is at least .

We use to denote the probability that is returned by , where is a multigraph of vertices. We then have the following recursion for .

where the last inequality is due to the fact that and our previous discussions in the analysis of RandomContract that if the min-cut survives all first contractions then must be a min-cut in the remaining multigraph.

The base case is that for . Solving this recursion of (or proving by induction) gives us that

Recall that we can implement an edge contraction in time, thus it is easy to verify the following recursion of time complexity:

where denotes the running time of on a multigraph of vertices.

Solving the recursion of with the base case for , we have .

Therefore, for a multigraph of vertices, the algorithm returns a min-cut in with probability in time . Repeat this independently for times, we have an algorithm which runs in time and returns a min-cut with probability , a high probability.