Recursive algorithm in graph theory
In graph theory, the Stoer–Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights. 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. At each phase, the algorithm finds the minimum formula_1-formula_2 cut for two vertices formula_1 and formula_2 chosen at its will. Then the algorithm shrinks the edge between formula_1 and formula_2 to search for non formula_1-formula_2 cuts. The minimum cut found in all phases will be the minimum weighted cut of the graph.
A cut is a partition of the vertices of a graph into two non-empty, 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 practice, 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 formula_9 be a weighted undirected graph. Suppose that formula_10. The cut is called an formula_1-formula_2 cut if exactly one of formula_1 or formula_2 is in formula_15. The minimal cut of formula_16 that is also an formula_1-formula_2 cut is called the formula_1-formula_2 min-cut of formula_16.
This algorithm starts by finding an formula_1 and a formula_2 in formula_24, and an s-t min-cut formula_25 of formula_16. For any pair formula_27, there are two possible situations: either formula_25 is a global min-cut of formula_16, or formula_1 and formula_2 belong to the same side of the global min-cut of formula_16. Therefore, the global min-cut can be found by checking the graph formula_33, which is the graph after merging vertices formula_1 and formula_2 into a new vertex formula_36. During the merging, if formula_1 and formula_2 are connected by an edge then this edge disappears. If formula_1 and formula_2 both have edges to some vertex formula_41, then the weight of the edge from the new vertex formula_36 to formula_41 is formula_44. The algorithm is described as:
 MinimumCutPhaseformula_45
 formula_46
 while formula_47
 add to formula_48 the most tightly connected vertex
 end
 store the cut in which the last remaining vertex is by itself (the "cut-of-the-phase") 
 shrink formula_16 by merging the two vertices (s, t) added last (the value of "cut-of-the-phase" is the value of minimum s, t cut.)
 MinimumCutformula_45
 while formula_51
 MinimumCutPhaseformula_45
 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 formula_48 of the graphs vertices grows starting with an arbitrary single vertex until formula_48 is equal to formula_24. In each step, the vertex which is outside of formula_48, but most tightly connected with formula_48 is added to the set formula_48. This procedure can be formally shown as: add vertex formula_59 such that formula_60, where formula_61 is the sum of the weights of all the edges between formula_48 and formula_63. So, in a single phase, a pair of vertices formula_1 and formula_2 , and a min formula_66 cut formula_67 is determined. 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 formula_16 separating formula_1 and formula_2, the formula_67 is a minimum cut of formula_16. If not, then the minimum cut of formula_16 must have formula_1 and formula_2 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 formula_76 phases, the minimum cut can be determined.
Example.
This section refers to Figs. 1–6 in the original paper.
The graph in step 1 shows the original graph formula_16 and randomly selects node 2 as the starting node for this algorithm. In the MinimumCutPhase, set formula_48 only has node 2, the heaviest edge is edge (2,3), so node 3 is added into set formula_48. Next, set formula_48 contains node 2 and node 3, the heaviest edge is (3,4), thus node 4 is added to set formula_48. By following this procedure, the last two nodes are node 5 and node 1, which are formula_1 and formula_2 in this phase. By merging them into node 1+5, 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,1+5), thus node 1+5 is put in set formula_48. The next heaviest edges is (2,3) or (1+5,6), we choose (1+5,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 formula_48. 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 the cut given by MinimumCutPhase is in fact a minimum formula_66 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 formula_66-cut of formula_16.Let formula_89 be an arbitrary formula_66 cut, and formula_91 be the cut given by the phase. We must show that formula_92. Observe that a single run of MinimumCutPhase gives us an ordering of all the vertices in the graph (where formula_93 is the first and formula_1 and formula_2 are the two vertices added last in the phase). We say the vertex formula_41 is active if formula_41 and the vertex added just before formula_41 are
in opposite sides of the cut. We prove the lemma by induction on the set of active vertices. We define formula_99 as the set of vertices added to formula_48 before formula_41, and formula_102 to be the set of edges in formula_67 with both of their ends in formula_104, i.e. formula_105 is the cut induced by formula_104. We prove, for each active vertex formula_41,formula_108Let formula_109 be the first active vertex. By the definition of these two quantities, formula_110 and formula_111 are equivalent. formula_112 is simply all vertices added to formula_48 before formula_109, and the edges between these vertices and formula_109 are the edges that cross the cut formula_67. Therefore, as shown above, for active vertices formula_41 and formula_118, with formula_41 added to formula_48 before formula_118:formula_122formula_123 by induction, formula_124formula_125 since formula_126 contributes to formula_127 but not to formula_128 (and other edges are of non-negative weights)Thus, since formula_2 is always an active vertex since the last cut of the phase separates formula_1 from formula_2 by definition, for any active vertex formula_2:formula_133Therefore, the cut of the phase is at most as heavy as formula_67.
Time complexity.
The running time of the algorithm MinimumCut is equal to the added running time of the formula_135 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 formula_136 time.
Therefore, the overall running time should be the product of two phase complexity, which is formula_137.
For the further improvement, the key is to make it easy to select the next vertex to be added to the set formula_48, the most tightly connected vertex. During execution of a phase, all vertices that are not in formula_48 reside in a priority queue based on a key field. The key of a vertex formula_24 is the sum of the weights of the edges connecting it to the current formula_48, that is, formula_142. Whenever a vertex formula_41 is added to formula_48 we have to perform an update of the queue. formula_41 has to be deleted from the queue, and the key of every vertex formula_146 not in formula_48, connected to formula_41 has to be increased by the weight of the edge formula_149, if it exists. As this is done exactly once for every edge, overall we have to perform formula_150 ExtractMax and formula_151 IncreaseKey operations. By using the Fibonacci heap we can perform an ExtractMax operation in formula_152 amortized time and an IncreaseKey operation in formula_153 amortized time. Thus, the time we need for this key step that dominates the rest of the phase, is formula_136.
Example code.
Below is a concise C++ implementation of the Stoer–Wagner algorithm.
// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.
// Running time:
// O(|V|^3)
using namespace std;
pair ;int, vector ;int» globalMinCut(vector ;vector ;int» mat) {
 pair ;int, vector ;int» best = {INT_MAX, {}};
 int n = mat.size();
 vector ;vector ;int» co(n);
 for (int i = 0; i ; n; i++)
 co[i] = {i};
 for (int ph = 1; ph ; n; ph++) {
 vector ;int ; w = mat[0];
 size_t s = 0, t = 0;
 for (int it = 0; it ; n - ph; it++) { // O(V^2) - ; O(E log V) with prio. queue
 w[t] = INT_MIN;
 s = t, t = max_element(w.begin(), w.end()) - w.begin();
 for (int i = 0; i ; n; i++) w[i] += mat[t][i];
 best = min(best, {w[t] - mat[t][t], co[t]});
 co[s].insert(co[s].end(), co[t].begin(), co[t].end());
 for (int i = 0; i ; n; i++) mat[s][i] += mat[t][i];
 for (int i = 0; i ; n; i++) mat[i][s] = mat[s][i];
 mat[0][t] = INT_MIN;
 return best;
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 &amp;s, int &amp;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] &amp;&amp; !vis[j] &amp;&amp; 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] &amp;&amp; !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;