How to Learn Global Minimum-Cut Algorithms: Random Contraction, Stoer–Wagner, Failure Probability and Exact Cuts

Wait, What?

A graph can have a weakest place to break even when nobody tells you which two vertices must be separated.

Minimum cut is often first encountered beside maximum flow, where a source s and sink t are fixed. Global minimum cut asks a different question: among all ways to divide an undirected graph into two non-empty parts, which cut has the smallest total crossing weight?

That distinction is the key to learning this topic cleanly. The existing max-flow/min-cut machinery is valuable background, but global minimum cut deserves its own learning job because its algorithms can look very different. Karger’s algorithm repeatedly contracts random edges and succeeds only probabilistically. Stoer–Wagner grows maximum-adjacency sets and returns an exact global cut for undirected graphs with non-negative weights.

Quick Read

A cut partitions the vertices into two non-empty sets.
Cut weight is the total weight of edges crossing the partition.
s–t minimum cut must separate specified vertices s and t.
Global minimum cut chooses the best partition over all possible non-trivial partitions.
Karger contraction is randomized and simple; repetition raises success probability.
Stoer–Wagner is deterministic and exact for undirected graphs with non-negative edge weights.

1. Learn the Object Before the Algorithm

Draw a weighted undirected graph with six vertices. Circle any non-empty proper subset of the vertices. Every edge with exactly one endpoint inside the circle crosses the cut. Add their weights. That sum is the cut weight.

Repeat with several partitions. The global minimum cut is simply the least cut weight found over all possible partitions. The difficulty is that there are exponentially many partitions, so brute-force enumeration is not a professional solution.

2. Separate Global Cut From s–t Cut

This is the first misconception to remove. If s and t are specified, the algorithm is solving a constrained separation problem. If no terminals are specified, the algorithm is free to discover whichever separation is globally cheapest. A global minimum cut might leave two vertices on the same side even though a different s–t query would force them apart.

A useful exercise is to take one graph, first solve one s–t cut by inspection, then find the global cut. If the answers happen to match, change s and t until they do not. The learner needs to experience the difference, not just read the definitions.

3. Karger’s Insight: Contract Before You Know the Answer

Karger’s random contraction algorithm begins with an unweighted multigraph. Repeatedly choose an edge uniformly at random and contract its two endpoints into a single supernode. Parallel edges are retained. Self-loops created by contraction are discarded. Continue until only two supernodes remain. The edges between them define a cut.

The strange part is that the algorithm can destroy the true minimum cut. If it contracts an edge belonging to that cut, that particular run can no longer recover it. The algorithm works because there is a non-trivial probability that every contraction avoids the edges of one fixed minimum cut.

4. The Probability Argument Is the Algorithm

Suppose the minimum cut has size k. Then every vertex has degree at least k; otherwise the edges incident to a lower-degree vertex would themselves form a smaller cut. With n vertices, the graph therefore has at least nk/2 edges. Only k of those belong to the chosen minimum cut, so the probability that the first random contraction destroys that cut is at most 2/n.

Conditioned on survival, the same style of argument continues as the number of supernodes shrinks. Multiplying the survival probabilities yields a success probability on the order of 1/n² for one basic run. That may sound small, but independent repetition changes the story. If one run succeeds with probability p, then r independent runs all fail with probability (1−p)^r.

This is a major professional lesson: a randomized algorithm is not fully specified until you can state what it guarantees, with what probability, under what independence assumptions, and how many repetitions are needed for the desired confidence.

5. How to Trace Random Contraction Properly

Write the current supernodes explicitly.
Record the random edge chosen at each step.
After contraction, remove self-loops.
Keep parallel edges; they represent multiplicity and affect future selection probabilities.
When two supernodes remain, count or sum crossing edges according to the model.
Repeat the same initial graph with a different random sequence and compare the resulting cut.

Do not let a learner see only successful runs. A failed run is educationally essential because it makes the probability model concrete.

6. Karger–Stein: Recurse Before Contracting Too Far

Karger and Stein improved the contraction idea by not committing to one contraction path all the way down. Their recursive scheme contracts to an intermediate size and branches, improving success probability and expected running time compared with naively repeating the basic algorithm enough times. The important learning point is not the exact recurrence at first. It is the design pattern: retain the simple random contraction primitive, then wrap it in recursion to reduce the chance that one unlucky early choice destroys the answer.

7. Stoer–Wagner: An Exact Deterministic Route

For an undirected graph with non-negative edge weights, the Stoer–Wagner algorithm finds a global minimum cut without fixing source and sink and without relying on random success.

Each phase grows a set A. Start from any vertex. Repeatedly add the vertex outside A that is most tightly connected to A, meaning the total weight of its edges into A is largest. The last two vertices added in the phase are called s and t. The connectivity weight of t at that moment gives an s–t cut for the phase. Record that cut, then merge s and t and repeat on the smaller graph.

The smallest phase cut encountered over all contractions is the global minimum cut.

8. Maximum Adjacency Search Looks Like Prim in Reverse Spirit

Students often find Stoer–Wagner easier after learning Prim’s minimum spanning tree algorithm because both repeatedly grow a set by choosing a vertex according to a key that changes as the set grows. But the objective is different. Prim chooses a cheapest connection that extends a tree. Stoer–Wagner chooses the vertex most strongly connected to the accumulated set during a phase.

Do not collapse the two algorithms into one analogy. Use the analogy only to help learners understand the repeated “grow a set, update keys, choose next vertex” control structure.

9. Why the Last Vertex Defines a Phase Cut

At the moment t is added last, every other current vertex is already inside A. Its accumulated adjacency weight is therefore the weight of the cut separating t from the rest of the current contracted graph. The correctness proof shows that for the chosen final pair s,t, this phase produces a minimum s–t cut. Repeated contractions ensure that some phase captures a global minimum cut unless its two sides have already been merged together—in which case the induction argument transfers the answer to the contracted graph.

10. What Contraction Must Preserve

When two vertices or supernodes are merged, edge weights to a common neighbour add together. Self-loops disappear because they no longer cross any possible cut in the contracted graph. The implementation must preserve the total crossing weight between supernodes; otherwise later cut values become meaningless.

11. Choosing Between the Algorithms

Karger basic contraction: excellent for understanding randomized algorithms and useful when simple implementations and repeated trials are acceptable.
Karger–Stein: improves the randomized contraction strategy and is appropriate when the probabilistic route is being taken seriously.
Stoer–Wagner: deterministic exact global minimum cut for undirected non-negative weighted graphs.
Flow-based methods: still matter for fixed-terminal s–t cuts and for formulations outside the exact Stoer–Wagner contract.

Always state whether the graph is directed or undirected, weighted or unweighted, whether weights are non-negative, whether terminals are fixed, and whether probabilistic success is acceptable.

12. Engineering Details Professionals Notice

Parallel edges are not an implementation nuisance in random contraction; their multiplicity matters.
Weighted random contraction needs careful definition if edge-selection probabilities differ from the unweighted model.
Priority-queue choices affect Stoer–Wagner implementation cost.
Contraction data structures must preserve partitions if the final vertex sets, not only the cut weight, are required.
Floating-point weights can make equality and reproducibility awkward.
Disconnected input may make the global minimum cut trivially zero depending on the problem contract.

13. Learn It With Predict–Trace–Explain–Implement

For novices, a worked graph is more useful than a wall of pseudocode. Research-informed programming pedagogy recommends code reading and tracing before unsupported code generation. A practical sequence is:

Predict: identify which visible partition looks cheapest.
Trace: run one Karger contraction sequence by hand.
Explain: state exactly when the true minimum cut was destroyed or preserved.
Modify: repeat with another random sequence.
Trace: perform one Stoer–Wagner maximum-adjacency phase.
Implement: begin with a tiny adjacency-matrix version before optimizing.
Test: compare against brute force on graphs small enough to enumerate all partitions.

14. Testing Strategy

Single edge between two vertices.
Triangle with equal weights.
Two dense clusters connected by one light bridge.
Graph with parallel edges for Karger.
Weighted graph where the fewest-edge cut is not the minimum-weight cut.
Disconnected graph, according to the chosen contract.
Random small graphs checked against exhaustive partition enumeration.

For randomized implementations, test both correctness of returned cuts and empirical success rate across many seeds. A probabilistic algorithm can be coded incorrectly while still occasionally returning the right answer.

Common Failure States

Calling an s–t minimum cut a global minimum cut.
Deleting parallel edges during Karger contraction.
Forgetting to remove self-loops.
Reporting one Karger run as if it were an exact algorithm.
Using a probability bound without stating how many independent repetitions were run.
Applying Stoer–Wagner outside its undirected non-negative-weight contract without justification.
Returning a cut weight without preserving enough information to reconstruct the partition.

Practice Ladder: Beginner to Professional

Beginner: calculate cut weights by hand.
Foundation: distinguish global from fixed-terminal cuts.
Intermediate: trace Karger contraction, including parallel edges and self-loops.
Intermediate: derive the basic survival-probability bound.
Advanced: trace one full Stoer–Wagner phase.
Advanced: implement Stoer–Wagner and compare with exhaustive search on small graphs.
Professional: compare Karger-style randomized methods, Stoer–Wagner and flow-based alternatives under realistic graph sizes and requirements.

Learning Hall Boundary

This article owns global minimum-cut learning. It deliberately does not replace the existing eduKateSengkang articles on general graph algorithms, max-flow/min-cut, randomized algorithms, minimum spanning trees or graph partitioning. Those are neighbouring jobs; this page teaches the specific question “What is the cheapest unrestricted two-way cut, and how do we find it?”

Authoritative Starting Points

Princeton Algorithms 4/e: GlobalMincut
NetworkX connectivity and Stoer–Wagner documentation
Mechthild Stoer and Frank Wagner, A Simple Min-Cut Algorithm, Journal of the ACM 44(4), 1997.
UC Berkeley CS174 notes on randomized minimum cuts

Professional rule: you understand global minimum cut when you can define the problem independently of max flow, explain why random contraction can succeed despite destructive choices, trace Stoer–Wagner’s phase invariant, and choose an algorithm whose guarantee matches the graph model and the required certainty.