MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms October 22, 1996 Lecture 11 Lecturer: Michel X. Goemans Scribe: Roberto De Prisco Minimum Cuts In this lecture we will describe an algorithm that computes the minimum cut (or simply mincut) in an undirected graph. A cut is defined as follows. Definition 1 Given a graph G = (V,E) and a subset S of V, the cut S(S) induced by S is the subset of edges (i, j) E E such that 1 {i,j) ilSI = 1. That is, 6(S) consists of all those edges with exactly one endpoint in S. Given an undirected graph G = (V,E) and for each edge e E E a nonnegative cost (or capacity) ce, the cost of a cut 6(S), is the sum of the costs of the edges in the cut, that is The minimum cut problem (or mincut problem) is to find a cut of minimum cost. If all costs are 1then the problem becomes the problem of finding a cut with as few edges as possible. Cuts are often defined in a different, not completely equivalent, way. Define a cutset to be a set of edges whose removal disconnects the graph into at least two connected components. Minimal cutsets (a minimal cutset C is a cutset such that any proper subset of C is not anymore a cutset) can be seen to correspond to cuts 6(S) for which the subgraphs induced by S and V -S are connected. Observe that only minimal cutsets can be of minimum cost (among all cutsets) and that only cuts S(S) for which both S and V -S induce connected components can be of minimum cost (among all cuts) since the costs are assumed to be nonnegative. For this reason, the problem of finding a cutset of minimum cost is equivalent to the problem of finding a cut 6(S) of minimum cost, namely the mincut problem. From now on, we will only look at cuts 6(S) (and not cutsets). An important variant of the mincut problem is often considered. This is the problem of finding the minimum cost cut separating two given two vertices s and t. A cut 6(S) is said to separate s and t if only one of them belongs to S. We refer to this problem as the minimum (s,t)-cut problem. The minimum (s, t)-cut problem has been traditionally solved by means of network flow algorithms. Indeed it can be reduced to a max flow problem. Given a source sand a sink t of the graph G, it is known that1 MAX FLOW(s, t) = min c(6(S)).S:s~s,t@S Notice that this result relates the value of the maximum flow from s to t and the value of the minimum (s,t)-cut It does not specify any relationship between the minimum (s,t)-cut itself (meaning the edges composing the cut) and the way the maximum flow can be pushed into the graph. However, given a maximum flow, it is easy to obtain the corresponding (s,t)-mincut. If you look at the residual graph corresponding to the maximum flow, the set S of vertices reachable from S will induce a minimum cut. By definition of the residual graph (and properties of maximum flows), the cost of this cut is equal to the value of the maximum flow and thus it is a min (s,t)-cut. On the other hand, the knowledge of a min (s, t)-cut does not help in finding the actual maximum flow (not just its value but the flow on every edge). Indeed, consider the following example. Let C*be the min (s, t)-cut value in G = (V,E) and let us consider the graph G' = (V', El) where V' = {s'} u V and E' = {(s', s)) U E with c(s', s) = C*. Then a possible minimum (s',t)-cut is &(is')). However this does not give any more information on how the flow can be pushed from s' to t (than just its value C*). So far no algorithm that finds a minimum (s, t)-cut without using a reduction to the max flow problem has been discovered. We will see that for general mincuts (ot separating two given vertices), the situation is different. How can we find a minimum cut in an undirected graph? One possibility is to choose a vertex s and compute the min (s, t)-cuts for every t E V -{s), and choose the cut of minimum cost among all the cuts obtained. The fastest maximum flow algorithms currently take slightly more than O(mn) time (for example, Goldberg and Tarjan's algorithm [I]take O(mn log(n2/m)) time). Since we need to use it n times, we can find a mincut in O(mn2 log(n2/m)) time. However, these n -1 maxflow problem are related, and Hao and Orlin [2] have shown that it is possible to solve all of them in O(mn log(n2/m)) by modifying Goldberg and Tarjan's algorithm. Thus the minimum cut problem can be solved within this time bound. In this lecture, we will derive an algorithm for the mincut problem which is not based on network flows, and which has a running time slightly better than Hao and Orlin's. The algorithm is due to Stoer and Wagner [6], and is a simplification of an earlier result of Nagamochi and Ibaraki [5]. We should also point out that there is a randomized algorithm due to Karger and Stein [4] whose running time is O(n2 log3 n), and a subsequent one due to Karger [3] that runs in O(mlog3 n). We first need a definition. Define, for any two sets A, B of nodes of the graph, It is clear that the maximum flow cannot be larger than the cost of any cut. This result says that it is as large as it can be, i.e. as large as the cost of the minimum (s, t)-cut.The algorithm is described below. In words, the algorithm starts with any vertex, and build an ordering of the vertices by always adding to the selected vertices the vertex whose total cost to the previous vertices is maximized. The cut induced by the last vertex in the ordering is considered, as well as the cuts obtained by recursively applying the procedure to the graph obtained by shrinking the last two vertices. (If there are edges from a vertex v to these last two vertices then we substitute those two edges with only one edge having capacity equal to the sum of the capacities of the two edges.) The claim is that the best cut among the cuts considered is the overall mincut. The formal description is given below. Let vl be any vertex of G for i = 2 to n let vi the node of V \ S s.t. c(S : {v}) is maximized (over all v E V \ S) S :=SU {vi} end for if n = 2 then return the cut S({v,}) else Let G' be obtained from G by shrinking v,-1 and v, Let C be the cut returned by MINCUT(G') Among C and 6({vn)) return the smaller cut (in terms of cost) endif