UC Berkeley—CS 170: Efficient Algorithms and Intractable Problems Handout 11Lecturer: David Wagner March 11, 2003Notes 11 for CS 1701 Min CutGiven an undirected graph G = (V, E), a cut is a partition of the set of vertices into twonon-empty subsets S and V − S. The cost of a cut (S, V − S) is the number of edges of Ethat are incident on one vertex in S and one vertex in V − S. The global min-cut problem(or, in short, the min-cut problem) is the problem of finding a cut (S, V − S) of minimumcost.Another way to look at the problem is that we are looking at the smallest set C ⊆ E ofedges such that removing those edges from the graph disconnects it. If the cost of a min-cutin a graph is k, then removing any k −1 edges from the graph leaves it connected, but thereis a way of removing k edges that disconnects it. A graph whose min-cut has cost k is alsosaid to be k-connected. In a k connected graph, there are always at least k different simplepaths between any two edges. Computing the min-cut of the graph of a network is then,for example, a way to estimate the worst-case reliability of the network.More generally, we may be also given a weight function that associates a positive valueweight(u, v) to each edge (u, v) ∈ E. In this case, the cost of a cut (S, V − S) is the sum ofthe weights of the edges that are incident on a vertex in S and a vertex in V − S.Algorithms to compute the min-cut of a graph can be derived from network flow algo-rithms that we will see later in the course. Such flow-based algorithms are not very efficient,and they are complicated to implement and to analyze. Today, we will see a randomizedalgorithms that seems just too simple to possibly work, and then we will see that it alsohas a fairly simple analysis. A straightforward implementation of the algorithm would bequite slow, but it is possible to optimize the implementation somewhat, and come up witha very efficient, and still simple, randomized algorithm.2 The Contract AlgorithmsWe introduce the following graph operation (that was implicit in one the minimum spanningtree algorithms that we have seen): given an undirected graph G = (V, E), a weight functionweight() and an edge (u, v) ∈ E, contract ((u,v),G) returns a graph G0that is identicalto G except that the vertices u and v have been replaced by a new vertex uv, and that allneighbors of u and v in G are now neighbors of uv in G0; the weight of the edge (uv, z) inG0is the sum of the weights of the edges (u, z) and (v, z) in G (if any).2.1 AlgorithmThe algorithm is as follows.Notes number 11 2algorithm Contract(G=(V,E): graph)while |V | > 2 dopick at random an edge (u, v) ∈ E// with probability proportional to weight(u, v)(G,w) = contract(G,w,(u,v))return names of two remaining vertices in GBasically, the algorithm keeps contracting random edges, so that, after a few rounds,the graph just contains a few vertices that corresponds to sets of vertices in the originalgraph. When only two “macro-vertices” are left, they represent a cut, and such a cut isreturned by the algorithm.2.2 AnalysisOur strategy will be the following. We fix a min-cut (S, V −S) in the input graph G, and weargue that there is a reasonable probability that the algorithm converges to that particularmin-cut.In order for the algorithm to converge to (S, V − S), it must always contract edges thatdo not cross the final cut: in fact, this is a necessary and sufficient condition.Suppose the cost of a min-cut in G is k. Then it follows that, for every vertex vin G, the sum of the weight of the edges incident on v is at least k. (Otherwise, thecut ({v, }, V − {v}) would be better than the optimum.) Consider now the expressionPv∈VP(v,z)∈Eweight(v, z). On the one hand, by the above argument, we haveXv∈VX(v,z)∈Eweight(v, z) ≥Xv∈Vk = n · kwhere n = |V |; on the other hand, the expression is counting twice the weight of every edge,so we haveXv∈VX(v,z)∈Eweight(v, z) = 2X(v,z)∈Eweight(v, z)Now, the probability of picking an edge is proportional to its weight, the total weightof the cut (S, V − S) is k, the total weight of all edges is at least kn/2, it follows that thereis at least a probability 1 − 2/n of doing well in the first step of the algorithm.If we think about it, we quickly realize that, if the algorithm does well in the first pick,at the second stage it has a graph with n −1 nodes where the cut (S, V − S) still is optimumand has cost k. A reasoning similar to the one above will give us that there is a probabilityat least 1 − 2/(n − 1) that we do well at the second step.Overall, we can see that the probability of converging to the cut (S, V − S) is at least1 −2n1 −2n − 11 −2n − 2· · ·1 −241 −23(1)We can write Expression 1 slightly differently as(n − 2)n·(n − 3)n − 1·(n − 4)n − 2·(n − 5)n − 3· · ·35·24·13Notes number 11 3which is clearly equal to 2/n(n − 1) > 2/n2.Now, if we repeat the algorithm n2/2 times, the probability of not finding the cut(S, V − S) at least once is at most1 −2n2n2/2≈ 1/eand if we repeat the algorithm 100n2times, the probability of finding the right cut at leastonce becomes very close to 1. What we will do, then, is to repeat the algorithm 100n2times, and then take the solution of minimum cost. At least one solution will be optimal,and so we are done.Notice that, in one run of the algorithm, we have a probability at least 2/n2to convergeto each fixed optimum cut: this means that there are never more than n2/2 distinct optimumcuts. (This is in contrast to the case of the minimum spanning tree problem, where, if theweights are not all different, there can be an exponential number of minimal trees.)The contract operator can be implemented in O(n) time, the operator is invoked ntimes in each iteration of the basic algorithm, and we have O(n2) iterations of the basicalgorithm. In total, the running time is O(n4). The best known min-cut algorithm basedon the contract operator and on the above ideas runs in O(n2(log n)O(1))