Minimum Cut

Minimum cut problem usually refer to s-t minimum cut, which can be solved by using maximum flow algorithm (eg. Ford-Fulkerson, Edmonds-Karp, relabel-to-front, ... etc.). The problem discuss in this article is general minimum cut problem. Given an undirected graph G = (V, E), a cut is to split the nodes of the graph into two set S and T. Any edge (u, v) in E with either u in S and v in T or u in T and v in S is a cut edge, which is belongs to the cut set. In weighted undirected graph, a cut is minimum if the sum of weight of its set is the smallest among all possible cut set.

Gomory-Hu tree. This algorithm is used to construct a general graph into a tree, weight of edges of the tree correspond to the weight of the cut set to disconnect adjacent vertices. The idea of this algorithm is very simple. At the beginning, pick two vertices arbitrarily, and compute the minimum cut between them. Then separate the graph into two groups, contract the edges in the cut set into a new edge e', and the weight of e' is the weight of the cut set. After that, in each iteration, pick two vertices from the same group, and find the minimum cut between them, then separate the group into two and contract the edges as before. It is obvious that this algorithm only need O(n) iterations of computing minimum cut. There are many variations of this algorithm to get a better time complexity, you can google it if you are interested in.

Stoer-Wagner's min-cut algorithm. This is the algorithm I implemented these days. The algorithm is based on a theorem. Let s and t be two vertices of graph G = (V, E). Let G/{s, t} be the graph obtained by contracting s and t. Then, a minimum cut of G can be obtained by taking the smaller of minimum s-t cut and minimum cut of G/{s, t}. By this theorem, Stoer and Wagner comes up an algorithm. In each iteration of the algorithm, get two vertices which have a minimum cut to separate them, then contract these two vertices. This algorithm follows the theorem stated above. If the minimum cut is not current s-t cut, then it should be in the graph G/{s, t}. The following is the pseudo code of this algorithm.

MinCutPhase(G, w, a):
 A <- {a}
 while (A != V)
  x <- Most Tightly Connected Vertex
  if (|A| == |V| - 2)
   s <- x
  if (|A| == |V| - 1)
   t <- x
   CurrentCut <- (A, complement of A)
  add x to A
 Contract(s, t)
 return CurrentCut

MinCut (G, w, a):
 while (|V| > 1)
  CurrentCut <- MinCutPhase(G, w, a)
  if (w(CurrentCut) < w(MinimumCut))
   MinimumCut <- CurrentCut

In the pseudo code above, the definition of most tightly connected vertex x is:

• x not in A s.t.
  
• w(A, x) = max { w(A, y) | y not in A }

The only thing that we need to care is the correctness of the MinCutPhase function, and it can be proved by induction. This algorithm also need O(n) iterations to compute MinCutPhase(). If priority queue is used for getting the most tightly connected vertex in each iteration in MinCutPhase, in total it needs O(nlogn) time. For updating the weights of all the edges from the selected vertex to any vertices not in A, in overall it takes O(m) time. As a result, this algorithm run in O(nm + n²logn) time.

Related Problems:

• Minimum Cut (from acm.pku.edu.cn)
• Bomb, Divide and Conquer (from acm.uva.es)
  

Reference:

• Stoer, M. and Wagner, F. 1997. A simple min-cut algorithm. J. ACM 44, 4 (Jul. 1997), 585-591. DOI= http://doi.acm.org/10.1145/263867.263872
• Anne Loomis, Min cut, CS 105 (Winter 2005), Computer Science, Dartmouth College