Stoer–Wagner Global Minimum Cut
Contract maximum-adjacency phases to find the lightest cut without choosing terminals.
By Riano · Published · Updated · Report a correction
Stoer–Wagner Global Minimum Cut
The Stoer–Wagner algorithm calculates the global minimum cut of an undirected, non-negative weighted graph. Instead of relying on a source-sink max-flow calculation for all pairs of nodes, it computes the min-cut efficiently through a series of phases. In each phase, the graph is contracted to find the minimum cut separating a specific pair of vertices.
Worked Example
Let's consider a simple undirected Path graph with 3 vertices: 0, 1, and 2, connected by edges (0-1) with weight 2, and (1-2) with weight 2.
- Initialize the graph with nodes V = {0, 1, 2} and weights.
- Phase 1: Start at node 0. Node 1 is most tightly connected (weight 2). Then node 2 is connected to node 1. The last two nodes added are 1 and 2. The cut weight separating node 2 from the rest is 2. We contract nodes 1 and 2 into a single supernode (1,2).
- Phase 2: The remaining nodes are 0 and (1,2). The weight connecting them is 2. The minimum cut weight found over all phases is 2.
- The canonical side of the cut containing vertex 0 is simply the set {0}.
Experiment
Explore how different graph topologies affect the minimum cut and the canonical side by selecting different graphs from the controls. See Stoer–Wagner Global Minimum Cut.
- Select the Path graph. Notice that the minimum cut weight is 2, separating node 0 from the rest.
- Change the Graph control to Disconnected. Observe that the minimum cut weight drops to 0, representing the absence of edges between the components, with a canonical side of "0,1".
- Switch to the Complete graph to see the minimum cut weight increase to 3.
Limitations
The Stoer-Wagner algorithm as implemented applies only to undirected graphs with non-negative edge weights. For disconnected graphs, the minimum cut weight is correctly identified as 0. Additionally, this visualization uses predefined vertex layouts, so dynamic layout adjustments for arbitrary graphs are not supported.
References
For a complete technical description of the Stoer-Wagner algorithm:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Stoer–Wagner Global Minimum Cut module.
Try Stoer–Wagner Global Minimum Cut on Riano →