Stoer–Wagner algorithm

A min-cut of a weighted graph having min-cut weight 4^[1]

In graph theory, the Stoer–Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs. It 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] After each shrinking, the weight of the merged cut would be stored in a list. Finally, the minimum weight cut in the list will be the minimum of the graph.

A cut is a partition of the vertices of a graph into two disjoint subsets. A minimum cut is a cut for which the size or weight of the cut is not larger than the size of any other cut. For an unweighted graph, the minimum cut would simply be the cut with the least edges. For a weighted graph, the sum of all edges' weight on the cut determines whether it is a minimum cut. In practical, the minimum cut problem is always discussed with the maximum flow problem, to explore the maximum capacity of a network, since the minimum cut is a bottleneck in a graph or network.

Stoer–Wagner minimum cut algorithm

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 $|\{ s, t\} \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)$

    $A\gets\left\{a\right\}$ 
   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

MinimumCut $(G,w,a)$

   while  $|V|>1$ 
       MinimumCutPhase $(G,w,a)$ 
       if the cut-of-the-phase is lighter than the current minimum cut
           then 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 to the set $A$ . This procedure can be formally shown as:^[2] add vertex $Z\notin A$ such that $w(A,z)=\max\{w(A,y\mid y\notin A)\}$ , where $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 merged as 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 can be determined.^[4]

Example

The graph in step 1 shows the original graph $G$ and randomly selects node 2 as the starting node for this algorithm. In the MinimumCutPhase, set $A$ only has node 2, the heaviest edge is edge (2,3), so node 3 is added into set $A$ . Next, set $A$ contains node 2 and node 3, the heaviest edge is (3,4), thus node 4 is added to set $A$ . By following this procedure, the last two nodes are node 5 and node 1, which are $s$ and $t$ in this phase. By merging them, the new graph is as shown in step 2. In this phase, the weight of cut is 5, which is the summation of edges (1,2) and (1,5). Right now, the first loop of MinimumCut is completed.

In step 2, starting from node 2, the heaviest edge is (2,15), thus node 15 is put in set $A$ . The next heaviest edges is (2,3) or (15,6), we choose (15,6) thus node 6 is added to the set. Then we compare edge (2,3) and (6,7) and choose node 3 to put in set $A$ . The last two nodes are node 7 and node 8. Therefore, merge edge (7,8). The minimum cut is 5, so remain the minimum as 5.

The following steps repeat the same operations on the merged graph, until there is only one edge in the graph, as shown in step 7. The global minimum cut has edge (2,3) and edge (6,7), which is detected in step 5.

Proof of correctness

To prove the correctness of this algorithm, we need to prove that MinimumCutPhase 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: MinimumCutPhase returns a minimum $s\text{-}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 a 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 $\overline{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)=w(A_v,u)+w(A_u-A_v,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

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 running time should be the product of two phase complexity, which is $O(|V||E|+|V|^2\log|V|)$ [2].^[2]

For the further improvement, the key is to make it easy to select the next vertex to be added to the set $A$ , the most tightly connected vertex. During execution of a phase, all vertices that are not in $A$ reside in a priority queue based on a key field. The key of a vertex $V$ is the sum of the weights of the edges connecting it to the current $A$ , that is, $w(A,v)$ . Whenever a vertex $v$ is added to $A$ we have to perform an update of the queue. $v$ has to be deleted from the queue, and the key of every vertex $w$ not in $A$ , connected to $v$ has to be increased by the weight of the edge $vw$ , if it exists. As this is done exactly once for every edge, overall we have to perform $|V|$ ExtractMax and $|E|$ IncreaseKey operations. By using the Fibonacci heap we can perform an ExtractMax operation in $O(\log|V|)$ amortized time and an IncreaseKey operation in $O(1)$ amortized time. Thus, the time we need for this key step that dominates the rest of the phase, is $O(|E|+|V|\log|V|)$ .^[2]

Example code^[5]

// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.
//
// Running time:
//     O(|V|^3)
//
// INPUT: 
//     - graph, constructed using AddEdge()
//
// OUTPUT:
//     - (min cut value, nodes in half of min cut)

#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;

pair<int, VI> GetMinCut(VVI &weights) {
  int N = weights.size();
  VI used(N), cut, best_cut;
  int best_weight = -1;
  
  for (int phase = N-1; phase >= 0; phase--) {
    VI w = weights[0];
    VI added = used;
    int prev, last = 0;
    for (int i = 0; i < phase; i++) {
      prev = last;
      last = -1;
      for (int j = 1; j < N; j++)
	if (!added[j] && (last == -1 || w[j] > w[last])) last = j;
      if (i == phase-1) {
	for (int j = 0; j < N; j++) weights[prev][j] += weights[last][j];
	for (int j = 0; j < N; j++) weights[j][prev] = weights[prev][j];
	used[last] = true;
	cut.push_back(last);
	if (best_weight == -1 || w[last] < best_weight) {
	  best_cut = cut;
	  best_weight = w[last];
	}
      } else {
	for (int j = 0; j < N; j++)
	  w[j] += weights[last][j];
	added[last] = true;
      }
    }
  }
  return make_pair(best_weight, best_cut);
}

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;  
}

References

↑ "Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1". www.boost.org. Retrieved 2015-12-07.
1 2 3 4 5 "A Simple Min-Cut Algorithm" (PDF).
1 2 "Lecture notes for Analysis of Algorithms": Global minimum cuts" (PDF).
1 2 "The minimum cut algorithm of Stoer and Wagner" (PDF).
↑ "Stanford University ACM Team Notebook (2014–15)". web.stanford.edu. Retrieved 2015-12-07.

This article is issued from Wikipedia - version of the Tuesday, April 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.