StoerWagner

Stoer-Wagner is a deterministic algorithm for computing the global minimum cut of an undirected, weighted graph. It was introduced by R. Stoer and F. Wagner in 1997. The global minimum cut is the smallest total weight of edges whose removal separates the graph into two nonempty components.

The algorithm finds the minimum cut through a sequence of phases. In each phase, it repeatedly selects vertices with maximum adjacency to the already chosen set, building an ordering of the vertices. The last vertex in this ordering identifies a candidate cut, whose weight is recorded. The graph is then contracted by merging certain vertices, and the process repeats on the reduced graph. After n−1 phases (with n the original number of vertices), the smallest cut value observed during all phases is the global minimum cut, and a corresponding partition can be recovered from the sequence of contractions.

A straightforward implementation uses an adjacency matrix and runs in O(n^3) time with O(n^2) space. With careful data structures and optimization, practical performance can be improved, particularly on dense graphs. The method requires an undirected graph with nonnegative edge weights and yields both the minimum cut value and, implicitly, a cut that realizes that value.

Stoer-Wagner is related to other min-cut concepts and algorithms, such as the Gomory–Hu tree, which represents all pairwise minimum cuts, and randomized approaches like the Karger–Stein algorithm. The Stoer-Wagner algorithm is appreciated for its conceptual simplicity and reliability, and it remains widely used in graph partitioning, network reliability analyses, and related applications.