Minimum cut

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A graph and two of its cuts. The dotted line in red represents a cut with three crossing edges. The dashed line in green represents one of the minimum cuts of this graph, crossing only two edges.

[1] In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) that is minimal in some sense. Variations of the minimum cut include:

  • The cut with the minimum number of edges among all cuts in an undirected graph, determining the edge connectivity of the graph. Karger's algorithm provides an efficient randomized method for finding this cut.
  • A generalization of the unweighted and undirected minimum cut, the minimum k-cut, in which the goal is to partition the graph into at least k connected components by removing as few edges as possible.
  • Graph partition, a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut.
  • The cut in a flow network that separates the source and sink vertices and minimizes the total weight on the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the max-flow min-cut theorem, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network.
  • A cut in a weighted undirected network that separates a particular pair of vertices from each other and has minimum possible weight. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the Gomory–Hu tree of the graph.

Stoer-Wagner Minimum Cut[edit]

Stoer-Wagner Minimum Cut Algorithm[edit]

The Stoer Wanger algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs. This algorithm was proposed by Mechthild Stoer and Frank Wagner in 1995. The essential idea of this algorithm is to shrink the graph by merging the most intensive vertices, until the graph only contains two combined vertex sets.[2] Let G=(V,E,w) be a weighted undirected graph. Let (S,T) be a global min-cut of G. Suppose that s,t\in V. If |\left\{ s, t\right\} \cap S|=1, then the (S,T) is obviously a s-t min-cut of G.[3]

This algorithm starts by finding a s-t min-cut (S,T) of G, for the two vertices \left\{s,t\right\}\in V. For the pair of (S,T), it has two different situations: (S,T) is a global min-cut of G; or they belong to the same side of the global min-cut of G. Therefore, the global min-cut can be found by checking the graph G/\left\{s,t\right\}, which is the graph after the merging of vertices s and t. During the merging, If s and t are connected by an edge then this edge disappears. If s and t both have edges to some vertex v, then the weight of the edge from the new vertex st to v is w(s,v)+w(t,v).[3] The algorithm is described as:[2]

  • MinimumCutPhase(G,w,a)


while \ A\ne V

add to A the most tightly connected vertex

store the cut-of-the-phase and shrink G by merging the two vertices added last(Contract s and t)

  • MinimumCut(G,w,a)

while |V|>1


If the cut-of-the-phase is lighter than the current minimum cut

store the cut-of-the-phase as the current minimum cut

The algorithm works in phases. In the MinimumCutPhase, the subset A of the graphs vertices grows starting with an arbitrary single vertex until A is equal to V . In each step, the vertex which is outside of A, but most tightly connected with A is added. This procedure can be formally shown as:[2] add vertex Z\notin A such that w(A,z)=max\left\{w(A,y|y\notin A)\right\}. Where the w(A,y) is the sum of the weights of all the edges between A and y. So, in a single phase, a pair of vertices s and t , and a min s\text{-}t cut C is determined.[4] After one phase of the MinimumCutPhase, the two vertices are replaced by a new vertex, and edges from the two vertices to a remaining vertex are replaced by an edge weighted by the sum of the weights of the previous two edges. Edges joining the merged nodes are removed. If there is a minimum cut of G separating s and t, the C is a minimum cut of G. If not, then the minimum cut of G must has s and t on a same side. Therefore, the algorithm would merge them as one node. In addition, the MinimumCut would record and update the global minimum cut after each MinimumCutPhase. After n-1 phases, the minimum cut must be determined.[4]

Stoer-wagner algorithm
The diagram show seven steps (MinimumCutPhase) to shrink the graph and find the minimum cut in the graph. In each step, the s and t are found then merged. Finally, The minimum cut of the graph G is the fifth cut-of-the-phase and the weight is w=4.

Proof of Correctness[edit]

To prove the correctness of this algorithm, We need to prove that MinCutPhase is in fact a minimum s\text{-}t cut of the graph, where s and t are the two vertices last added in the phase. Therefore, a lemma is shown below:

Lemma 1: MinCutPhase returns a min s-t-cut of G.

We prove this by induction on the set of active vertices. Let C=(X,\overline{X}) be an arbitrary s\text{-}t cut, and CP be the cut of the phase. We must show that W(C)\ge W(CP). Observe that single run of MinimumCutPhase gives us a permutation of all the vertices in the graph (where a is the first and s and t are the two vertices added last in the phase). So, we say that the vertex v is active if v\in X, the vertex before v in the ordering of vertices produced by MinimumCutPhase is in X or vice versa, which is to say, they’re on opposite sides of the cut. We define A_{v} as the set of vertices added to A before v and C_{v} to be the cut of the set A_{v}\cup \{v\}induced by C. For all the active vertex v:

w(A_{v},v)\le w(C_{v})

Let v_{0} be the first active vertex. By the definition of these two quantities, the w(A_{v_{0}},v_{0}) and w(C_{v_{0}}) are equivalent. A_{v_{0}} is simply all vertices added to A before v_{0}, and the edges between these vertices and v_{0} are the edges that cross the cut C. Therefore, as shown above, For the active vertex u and v (v is added to A before u).


w(A_{u},u)\le w(C_{v})+w(A_{u}-A_{v},u) by introduction, w(A_{v},u)\le w(A_{v},v)\le w(C_{v})

w(A_{u},u)\le w(C_{v}) w(A_{u}-A_{v},u) contributes to w(C_{u}) but not w(C_{v})

Thus, since t is always an active vertex since the last cut of the phase separates s from t by definition, for any active vertex t:

w(A_{t},t)\le w(C_{t})=w(C)

Therefore, the cut of the phase is at most as heavy as C.

Time Complexity[edit]

The running time of the algorithm MinimumCut is equal to the added running time of the |V|-1 runs of MinimumCutPhase , which is called on graphs with decreasing number of vertices and edges.

For the MinimumCutPhase, a single run of it needs at most O(|E|+|V|log|V|) time.

Therefore, the overall runtime is O(|V||E|+|V|^{2}log|V|).[2]

Example Code[5][edit]

const int maxn = 550;  
const int inf = 1000000000;  
int n, r;  
int edge[maxn][maxn], dist[maxn];  
bool vis[maxn], bin[maxn];  
void init()  
    memset(edge, 0, sizeof(edge));  
    memset(bin, false, sizeof(bin));  
int contract( int &s, int &t )          // Find s,t  
    memset(dist, 0, sizeof(dist));  
    memset(vis, false, sizeof(vis));  
    int i, j, k, mincut, maxc;  
    for(i = 1; i <= n; i++)  
        k = -1; maxc = -1;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j] && dist[j] > maxc)  
            k = j;  maxc = dist[j];  
        if(k == -1)return mincut;  
        s = t;  t = k;  
        mincut = maxc;  
        vis[k] = true;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j])  
            dist[j] += edge[k][j];  
    return mincut;  
int Stoer_Wagner()  
    int mincut, i, j, s, t, ans;  
    for(mincut = inf, i = 1; i < n; i++)  
        ans = contract( s, t );  
        bin[t] = true;  
        if(mincut > ans)mincut = ans;  
        if(mincut == 0)return 0;  
        for(j = 1; j <= n; j++)if(!bin[j])  
            edge[s][j] = (edge[j][s] += edge[j][t]);  
    return mincut;  
  1. ^ "4 Min-Cut Algorithms". 
  2. ^ a b c d "A Simple Min-Cut Algorithm" (PDF). 
  3. ^ a b "Lecture notes for Analysis of Algorithms": Global minimum cuts" (PDF). 
  4. ^ a b "The minimum cut algorithm of Stoer and Wagner" (PDF). 
  5. ^ "Store-Wagner Algorithm Analysis". 

Number of minimum cuts[edit]

A graph with n vertices ca at the most have n (n-1) /2 distinct minimum cuts.

See also[edit]

  • Maximum cut, a cut that is as large as possible instead of being as small as possible
  • Vertex separator, an analogous concept to minimum cuts for vertices instead of edges