Stoer–Wagner algorithm

Stoer-Wagner Minimum Cut Algorithm

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. 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$.

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)$. The algorithm is described as:

• MinimumCutPhase$(G,w,a)$

$A\gets \left\{a\right\}$

while $\ A\neq 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$

MinimumCutPhase$(G,w,a)$

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: 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. 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.

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 

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)\geq 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)\leq 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)\leq w(C_{v})+w(A_{u}-A_{v},u)$ by introduction, $w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})$

$w(A_{u},u)\leq 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)\leq 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 runtime is $O(|V||E|+|V|^{2}log|V|)$.

Example Code

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