Phase
Start with arbitrary vertex. Grow set S by adding 'most connected' vertex to S each step. Last two vertices added = s, t. Weight of s in last step = min s-t cut. Merge s, t.
Advertisement
Complexity
O(VE + V² log V) with Fibonacci heap. O(V³) with arrays. Comparable to Ford-Fulkerson for min cut.
Advertisement
Why it works
Non-trivial theorem (Stoer-Wagner 1997). Uses submodularity of cut function.
vs Karger
Deterministic. Slightly slower than randomized Karger-Stein but proven correct.