Minimum Cut: Stoer-Wagner Algorithm
A minimum cut in a graph partitions vertices into two non-empty sets such that the total weight of edges crossing the partition is minimized. This fundamental problem appears everywhere in practice:...
Key Insights
- The Stoer-Wagner algorithm finds the global minimum cut in an undirected weighted graph without requiring source/sink designation, making it ideal for problems like network reliability analysis and image segmentation.
- The algorithm’s elegance lies in a simple observation: for any two vertices s and t, the minimum cut either separates them or it doesn’t—by systematically checking all possible s-t pairs through vertex contraction, we guarantee finding the global minimum.
- With O(VE + V² log V) time complexity using Fibonacci heaps, Stoer-Wagner often outperforms flow-based approaches for dense graphs and provides cleaner implementations for undirected graph problems.
Introduction to Minimum Cut Problems
A minimum cut in a graph partitions vertices into two non-empty sets such that the total weight of edges crossing the partition is minimized. This fundamental problem appears everywhere in practice: determining network reliability (what’s the weakest link?), image segmentation (separating foreground from background), clustering data points, and analyzing social network communities.
Most developers first encounter minimum cuts through the max-flow/min-cut theorem, which states that the maximum flow between two vertices equals the minimum cut separating them. While powerful, flow-based approaches require designating source and sink vertices. When you need the global minimum cut—the weakest point in an entire network—you’d need to run max-flow for every vertex pair.
The Stoer-Wagner algorithm solves this elegantly. Published in 1997, it directly computes the global minimum cut without the source/sink ceremony, making it the right tool when you’re asking “where is this network most vulnerable?” rather than “how much can flow from A to B?”
Why Stoer-Wagner?
Flow-based algorithms like Ford-Fulkerson or Push-Relabel are workhorses for directed graphs and s-t cut problems. But they carry baggage for undirected global minimum cut:
- No natural source/sink: You’d need O(V²) max-flow computations to check all pairs
- Direction handling: Undirected edges require careful bidirectional flow modeling
- Conceptual overhead: Flow networks add complexity when you just want a partition
Stoer-Wagner sidesteps all of this. It works directly on undirected weighted graphs, processes vertices in a natural ordering, and produces the global minimum cut in V-1 phases. Each phase runs a maximum adjacency search and contracts two vertices, progressively shrinking the graph until only two super-vertices remain.
The time complexity breaks down as O(VE + V² log V) with Fibonacci heaps, or O(V³) with simpler priority queues. For dense graphs where E approaches V², this matches or beats running V-1 max-flow computations.
Algorithm Intuition
Here’s the key insight that makes Stoer-Wagner work: pick any two vertices s and t. The global minimum cut either separates s from t, or it keeps them together. If it separates them, we can find it by computing the s-t minimum cut. If it doesn’t, then s and t are on the same side of the minimum cut, and we can merge them into a single super-vertex without losing information.
The algorithm exploits this by cleverly choosing which s and t to examine. Rather than picking arbitrarily, it uses maximum adjacency ordering: starting from an arbitrary vertex, repeatedly add the vertex most tightly connected to the already-selected set. The last two vertices added (call them s and t) have a special property—the cut separating just t from everything else equals the s-t minimum cut.
This “cut-of-the-phase” gives us one candidate for the global minimum. We then merge s and t (since if they’re not separated by the global minimum cut, we lose nothing) and repeat. After V-1 phases, we’ve checked all necessary configurations and tracked the best cut found.
The Algorithm Step-by-Step
The algorithm alternates between two operations:
Maximum Adjacency Search: Build an ordering of vertices by greedily selecting the vertex with maximum total edge weight to already-selected vertices. This runs like Prim’s MST algorithm but tracks connectivity strength rather than minimum edges.
Vertex Contraction: Merge the last two vertices in the ordering. Combine their edge weights to all neighbors. This reduces the graph by one vertex per phase.
Here’s the maximum adjacency search in Python:
import heapq
from collections import defaultdict
def maximum_adjacency_search(graph, num_vertices, active):
"""
Perform maximum adjacency search on the graph.
Returns the ordering of vertices and the cut-of-phase value.
graph: dict mapping (u, v) -> weight for edges
active: set of vertices still in the contracted graph
"""
if len(active) < 2:
return list(active), 0
# Start from arbitrary active vertex
start = next(iter(active))
in_set = {start}
ordering = [start]
# Priority queue: (-weight, vertex) - negative for max-heap behavior
# weight[v] = total edge weight from v to vertices in_set
weight = defaultdict(int)
pq = []
# Initialize weights from start vertex
for v in active:
if v != start:
edge_weight = graph.get((start, v), 0) + graph.get((v, start), 0)
weight[v] = edge_weight
heapq.heappush(pq, (-edge_weight, v))
cut_of_phase = 0
while len(in_set) < len(active):
# Find vertex with maximum weight to current set
while pq:
neg_w, v = heapq.heappop(pq)
if v not in in_set and v in active:
break
else:
# Remaining vertices are disconnected
for v in active:
if v not in in_set:
ordering.append(v)
in_set.add(v)
break
in_set.add(v)
ordering.append(v)
cut_of_phase = -neg_w # Weight of last added vertex
# Update weights for remaining vertices
for u in active:
if u not in in_set:
edge_weight = graph.get((v, u), 0) + graph.get((u, v), 0)
if edge_weight > 0:
weight[u] += edge_weight
heapq.heappush(pq, (-weight[u], u))
return ordering, cut_of_phase
Complete Implementation
Here’s the full Stoer-Wagner implementation with graph representation and cut tracking:
def stoer_wagner_min_cut(vertices, edges):
"""
Find the global minimum cut using Stoer-Wagner algorithm.
vertices: list of vertex identifiers
edges: list of (u, v, weight) tuples for undirected edges
Returns: (min_cut_weight, partition) where partition is a set of vertices
on one side of the minimum cut
"""
n = len(vertices)
if n < 2:
return float('inf'), set()
# Build adjacency representation
# graph[(u,v)] stores weight of edge u-v
graph = defaultdict(int)
for u, v, w in edges:
graph[(u, v)] += w
graph[(v, u)] += w
# Track which original vertices each super-vertex contains
# After contractions, merged[v] contains all original vertices in super-vertex v
merged = {v: {v} for v in vertices}
# Active vertices (shrinks as we contract)
active = set(vertices)
min_cut_weight = float('inf')
min_cut_partition = None
# Run V-1 phases
for phase in range(n - 1):
if len(active) < 2:
break
ordering, cut_of_phase = maximum_adjacency_search(graph, n, active)
if len(ordering) < 2:
break
# Last two vertices in ordering
s, t = ordering[-2], ordering[-1]
# Check if this phase found a better cut
if cut_of_phase < min_cut_weight:
min_cut_weight = cut_of_phase
min_cut_partition = merged[t].copy()
# Contract: merge t into s
# Update merged sets
merged[s] = merged[s] | merged[t]
# Update edges: combine t's edges into s
for v in active:
if v != s and v != t:
# New weight from s to v includes old s-v and t-v edges
w_tv = graph.get((t, v), 0)
if w_tv > 0:
graph[(s, v)] += w_tv
graph[(v, s)] += w_tv
# Remove t's edges
graph.pop((t, v), None)
graph.pop((v, t), None)
# Remove edge between s and t
graph.pop((s, t), None)
graph.pop((t, s), None)
# Remove t from active set
active.remove(t)
del merged[t]
return min_cut_weight, min_cut_partition
Worked Example
Let’s trace through a small graph with 5 vertices:
def trace_stoer_wagner():
"""Demonstrate algorithm on a small graph with tracing."""
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
('A', 'B', 2), ('A', 'C', 3),
('B', 'C', 4), ('B', 'D', 3),
('C', 'D', 1), ('C', 'E', 2),
('D', 'E', 4)
]
print("Initial graph:")
print(" A--2--B--3--D")
print(" |\\ | /|")
print(" 3 4 | / 4")
print(" | \\| / |")
print(" +--C--1-+ E")
print(" \\--2--/")
print()
# Simplified trace version
graph = defaultdict(int)
for u, v, w in edges:
graph[(u, v)] += w
graph[(v, u)] += w
active = set(vertices)
merged = {v: {v} for v in vertices}
for phase in range(len(vertices) - 1):
ordering, cut_weight = maximum_adjacency_search(graph, len(vertices), active)
if len(ordering) < 2:
break
s, t = ordering[-2], ordering[-1]
print(f"Phase {phase + 1}:")
print(f" Ordering: {' -> '.join(ordering)}")
print(f" s={s}, t={t}")
print(f" Cut-of-phase: {cut_weight}")
print(f" Merging {t} into {s}")
# Contract t into s
merged[s] = merged[s] | merged[t]
for v in list(active):
if v != s and v != t:
w_tv = graph.get((t, v), 0)
if w_tv > 0:
graph[(s, v)] += w_tv
graph[(v, s)] += w_tv
graph.pop((t, v), None)
graph.pop((v, t), None)
graph.pop((s, t), None)
graph.pop((t, s), None)
active.remove(t)
del merged[t]
print(f" Active vertices: {active}")
print()
# Run actual algorithm
min_cut, partition = stoer_wagner_min_cut(vertices, edges)
print(f"Minimum cut weight: {min_cut}")
print(f"Partition: {partition} | {set(vertices) - partition}")
trace_stoer_wagner()
Running this produces output showing each phase’s vertex ordering, the cut-of-phase values, and the final minimum cut. The algorithm systematically explores the graph structure, with each contraction preserving the minimum cut information.
Optimizations and Practical Considerations
The basic implementation above uses Python’s heapq with lazy deletion (we push duplicates and skip stale entries). For production use, consider these optimizations:
from dataclasses import dataclass, field
from typing import Any
@dataclass(order=True)
class PrioritizedItem:
priority: int
vertex: Any = field(compare=False)
valid: bool = field(default=True, compare=False)
def optimized_max_adjacency_search(adj_matrix, active_mask, n):
"""
Optimized version using adjacency matrix and lazy deletion.
adj_matrix: n x n weight matrix
active_mask: boolean array indicating active vertices
"""
active_count = sum(active_mask)
if active_count < 2:
return [], 0
# Find first active vertex
start = next(i for i in range(n) if active_mask[i])
in_set = [False] * n
in_set[start] = True
ordering = [start]
# Track current weights and heap entries
weight = [0] * n
entries = [None] * n
pq = []
for v in range(n):
if active_mask[v] and v != start:
weight[v] = adj_matrix[start][v]
entry = PrioritizedItem(-weight[v], v)
entries[v] = entry
heapq.heappush(pq, entry)
cut_of_phase = 0
while len(ordering) < active_count:
while pq:
entry = heapq.heappop(pq)
if entry.valid and not in_set[entry.vertex]:
break
else:
break
v = entry.vertex
in_set[v] = True
ordering.append(v)
cut_of_phase = weight[v]
# Update neighbors
for u in range(n):
if active_mask[u] and not in_set[u]:
delta = adj_matrix[v][u]
if delta > 0:
weight[u] += delta
if entries[u]:
entries[u].valid = False
new_entry = PrioritizedItem(-weight[u], u)
entries[u] = new_entry
heapq.heappush(pq, new_entry)
return ordering, cut_of_phase
For sparse graphs, maintain adjacency lists instead of matrices. For disconnected graphs, run Stoer-Wagner on each connected component separately—the global minimum cut is the minimum across components (or zero if multiple components exist).
In practice, Stoer-Wagner performs well on graphs up to tens of thousands of vertices. For larger graphs, consider randomized contraction algorithms or parallel implementations. The algorithm’s simplicity makes it easy to adapt, debug, and verify—often more valuable than marginal performance gains from complex alternatives.