Stoer_Wagner.H File Reference

Stoer-Wagner deterministic min-cut algorithm. More...

#include <limits>
#include <vector>
#include <queue>
#include <functional>
#include <htlist.H>
#include <tpl_sgraph.H>
#include <tpl_dynArray.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for Stoer_Wagner.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >
	Stoer-Wagner deterministic minimum cut algorithm. More...
struct	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::SWNode
struct	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::PQEntry
struct	Aleph::Unit_Weight< GT >
	Unit weight functor for unweighted graphs. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Stoer-Wagner deterministic min-cut algorithm.

Implements the Stoer-Wagner algorithm for finding minimum cuts in undirected weighted graphs. Unlike Karger's randomized approach, Stoer-Wagner is deterministic and always finds the exact minimum cut.

Algorithm Description

The Stoer-Wagner algorithm is based on a key observation: for any two vertices s and t, the minimum cut of the graph is either:

1. The minimum s-t cut (separating s from t), OR
2. The minimum cut of the graph with s and t merged

The algorithm exploits this by repeatedly finding a "minimum s-t cut" using a procedure called Maximum Adjacency Search (also known as Maximum Cardinality Search), then merging s and t.

Maximum Adjacency Search (MAS)

MAS grows a set A of vertices starting from an arbitrary vertex:

1. Start with A = {arbitrary vertex}
2. Repeatedly add the vertex v ∉ A that has maximum total edge weight to vertices in A
3. Continue until all vertices are in A
4. The last two vertices added (s and t) define a "minimum s-t cut"

Key theorem: The cut separating t from all other vertices has weight equal to the sum of edges incident to t. This is a minimum s-t cut!

Main Algorithm

1. Run MAS to find s, t, and the cut-of-the-phase (weight of edges to t)
2. If this cut is smaller than best known, update best cut
3. Merge s and t into a single vertex
4. Repeat until only 2 vertices remain
5. Return the minimum cut found

Time Complexity

• With binary heap: O(nm + n² log n)
• With Fibonacci heap: O(nm + n² log n)
• Simple implementation: O(n²m) or O(n³) for dense graphs

This implementation uses a binary heap, achieving O(nm + n² log n).

Comparison with Other Algorithms

Algorithm	Time Complexity	Type	Guarantee
Stoer-Wagner	O(nm + n² log n)	Deterministic	Exact
Karger	O(n⁴ m)	Randomized	High prob.
Karger-Stein	O(n² log³ n)	Randomized	High prob.
Max-Flow	O(n³) or better	Deterministic	Exact (s-t)

When to Use Stoer-Wagner

• Exact answer required: Deterministic, always finds true min-cut
• Weighted graphs: Handles edge weights naturally
• Sparse graphs: O(nm) term dominates, very efficient
• Small to medium graphs: Practical for n < 10,000

Limitations

• Designed for undirected graphs only
• For directed graphs, use max-flow based algorithms
• Memory: O(n²) for the adjacency representation during merges

Author

Leandro Rabindranath León

Definition in file Stoer_Wagner.H.