Motivation
A minimum cut separates an undirected graph into two nonempty parts while minimizing the number of crossing edges. A random algorithm can find one by repeatedly contracting an edge chosen uniformly at random. Contracting an edge inside each side of a particular minimum cut preserves that cut; contracting one of its crossing edges destroys it.
The algorithm does not know which edges cross the minimum cut. Its analysis instead bounds the chance of avoiding a fixed minimum cut at every stage. The resulting success probability is small for large graphs, but independent repetitions amplify it. The output is always a valid cut; randomness affects whether that cut is minimum.
Definitions
Definition 6.2.1
(Cuts and the minimum cut size)
Let be a connected undirected multigraph with vertices. Parallel edges are distinct edge copies; loops do not cross cuts and may be discarded. A cut is a partition of the original vertices into two nonempty sets. Its size is the number of edge copies with endpoints on opposite sides. Let be the minimum cut size; connectedness gives .
Definition 6.2.2
(Contraction and the random contraction algorithm)
Contract an edge by merging its endpoint vertices into one supervertex. Keep parallel edges as distinct copies and discard loops created by the merge. Each supervertex represents a nonempty set of original vertices. The random contraction algorithm repeatedly chooses uniformly among all current edge copies and contracts the chosen edge until exactly two supervertices remain. It returns the original-vertex partition represented by those two supervertices.
Uniform selection from an arbitrary number of edge copies is an ideal random-choice operation in the analysis. An implementation based on finite random bits must separately account for how it samples uniformly and how it handles rejection.
Theorems
Theorem 6.2.3
(One-trial success probability)
For every connected undirected multigraph with , one random contraction trial returns a minimum cut with probability at least .
Theorem 6.2.4
(Independent repetition)
For independent trials, returning the smallest cut found fails to return a minimum cut with probability at most
Proofs
Proof: protect one minimum cut
Proof
(Surviving a fixed minimum cut)
Fix one particular minimum cut of size . Say that the cut survives as long as no contracted edge crossed it. If it survives, every current supervertex lies wholly on one side. The two sides are still nonempty until the algorithm stops, and the same edge copies still cross between them: an edge crossing the fixed cut has not been contracted and cannot become a loop while the cut survives.
Suppose there are supervertices and the cut has survived. Every supervertex represents a nonempty proper subset of original vertices, so the number of edges leaving it is at least , by the definition of a minimum cut. Counting degrees in the current loopless multigraph gives at least total degree and therefore at least edge copies. Parallel copies count separately in both the degree sum and the random choice.
Exactly current edge copies cross the fixed cut. Conditional on survival so far, the chance that the next uniformly selected edge crosses it is at most
Thus the conditional probability of preserving the cut in the next contraction is at least . Multiply these conditional bounds for :
For the product is empty, equals one, and the sole cut is already returned. If the fixed cut survives until two supervertices remain, each side contains at least one supervertex, so one supervertex represents each side. The returned cut is exactly the fixed minimum cut. The algorithm may also succeed by returning a different minimum cut, so this gives a lower bound on total success probability.
Proof X-ray
Where minimality of the cut is used
The proof has one non-obvious move: it protects a single fixed minimum cut instead of asking whether the final output is minimum. Minimality of is used exactly once, to bound every degree below by . The edge copies leaving a supervertex form a cut of the original graph, and no cut is smaller than . Because parallel copies are kept, this degree count holds however many have formed. Connectedness gives , so the ratio is defined.
The same step shows why the protected cut must be minimum: for a cut of size the crossing probability would only be bounded by , which can exceed one. The product then telescopes, since cancels all but . The argument closes because a surviving cut with two supervertices left is exactly the fixed cut.
Proof: repeated trials
Proof
(Independent repetitions)
Run each trial from a fresh copy of the original graph, using independent random choices, and evaluate the returned partition in the original graph. Each trial succeeds with probability at least . Independence gives failure probability at most . The elementary inequality yields the exponential bound.
If at least one trial returns a minimum cut, the smallest cut among all returned cuts has size : no valid cut can have size smaller than the minimum. Therefore returning the smallest observed cut succeeds whenever any trial succeeds. To make failure probability at most for , it suffices to choose
rounding up to an integer. The guarantee concerns the probability of missing all minimum cuts, not the probability that an invalid partition is output.
Why edge contraction preserves a cut
A current supervertex represents the union of the original vertices merged into it. Contracting a current edge joins its two represented sets. If both sets lie on the same side of the fixed cut, their union still lies on that side, so every current supervertex remains entirely within one side. An original edge with endpoints on different sides still has endpoints in different supervertices and remains a crossing edge copy. Internal edges can become loops and disappear without changing the crossing count.
Conversely, contracting an edge crossing the fixed cut creates a supervertex containing vertices from both sides. No later partition of whole supervertices can separate those original vertices again, so that particular cut is lost. These two statements explain the survival event without assuming that contraction preserves every cut simultaneously.
The conditional product does not require the contraction choices at different stages to be independent. It uses the chain rule for the probability of successive survival events and a lower bound valid after every surviving history. Independence is needed later for the separate repetition guarantee, where each complete trial uses fresh random choices.
Worked examples
Worked example 6.2.5
(Two vertices)
Two vertices joined by three parallel edge copies already form the final two supervertices. The algorithm performs no contractions and returns the only cut, of size three, with probability one. The formula gives .
Worked example 6.2.6
(A triangle)
In a triangle, every cut separating one vertex has size two. The algorithm contracts one uniformly chosen edge, leaving two supervertices joined by two parallel edges. Every possible choice therefore returns a minimum cut. The theorem's lower bound is only , so it need not be tight.
Worked example 6.2.7
(Parallel edges are sampled separately)
Suppose the current graph has two copies of edge and one copy of edge . Uniform selection among edge copies chooses an copy with probability , not . Treating each distinct endpoint pair equally would define a different algorithm and invalidate the stated probability calculation.
Worked example 6.2.8
(Choosing the number of trials)
For , one trial has guaranteed success probability at least . To make the displayed exponential failure bound at most , choose independent trials. Their actual success probability can be higher than the guarantee.
A four-cycle calculation
Take the cycle with one copy of each edge, and fix the cut separating from the other three vertices. Its size is two. The first contraction avoids this cut exactly when it chooses or , each with probability , so the fixed cut survives the first step with probability .
If was contracted, the current graph has three supervertices: , and . Its remaining edges are determined by the original cycle: –, –, and –, with – appearing once from and – once from ; the contracted edge became a loop and was discarded. Thus the current graph is a triangle with three edge copies. Exactly one edge, –, lies within the non- side, so conditional survival at the second step is . The case where was contracted is symmetric. The fixed cut therefore survives with probability , equal to .
This calculation tracks one fixed cut. Other minimum cuts of the four-cycle may be returned even if the cut isolating is destroyed. In fact, after the first contraction the graph is a triangle, and any further contraction leaves two supervertices joined by two edge copies. Every trial on this graph therefore returns a minimum cut, and the fixed-cut survival probability is only a lower bound for the success probability.
Common mistakes
Counterexample mode
A contraction can destroy a particular minimum cut
In a triangle, fix the cut isolating vertex . Contracting either edge incident to merges the two sides of that fixed cut, so it does not survive. The algorithm can still return another minimum cut. The proof tracks one fixed cut to obtain a lower bound, not a necessary condition for all possible success.
Common mistake
(Discarding parallel edges is not safe)
Discarding self-loops is safe because they never cross any partition of the current supervertices. Discarding parallel edges is not safe: each copy contributes to cut size and must be represented in the uniform sampling probability. A weighted variant requires a separate sampling and cost model.
Common mistake
(Repetition needs fresh randomness)
A one-trial lower bound does not make repetitions independent automatically. The exponential failure calculation assumes fresh independent choices in each run. Reusing correlated random choices can leave the failure events correlated and requires a different analysis.
Running time and probability model
A straightforward implementation can keep an explicit list of current edge copies and scan it to update endpoints and remove loops after each contraction. This is polynomial time, though not necessarily the fastest implementation. Repeating the trial times multiplies its cost by , and the logarithm of determines how many repetitions the stated sufficient bound needs.
The proof treats a uniform edge-copy choice as exact. If a finite-bit implementation uses rejection sampling, it should state its stopping and error guarantees rather than silently assume every edge count is a power of two. The ideal-choice probability theorem remains valid independently of such implementation details.
Connectedness ensures that when more than one supervertex remains, at least one edge joins two supervertices, so the algorithm can continue. For a disconnected input the minimum cut is zero and can be found by taking a connected component against the rest; blindly applying the connected-graph contraction proof would divide by .
Evaluating a returned partition
The final two supervertices encode two nonempty sets of original vertices. A direct implementation can count original edge copies crossing between those sets to evaluate the cut, even if its contraction data structure has changed or discarded internal edges. The answer is always a legitimate partition, so its cost cannot fall below the true minimum. This one-sided property is what lets repetition choose the smallest result without introducing a false minimum.
The algorithm can return a nonminimum cut in some trials. The success probability theorem is a lower bound for every connected input, not a certificate that a particular observed cut is optimal. A deterministic certificate or an independent exact minimum-cut method would be needed to verify a single trial's optimality without relying on the probabilistic guarantee.
The survival argument forces at most n(n-1)/2 minimum cuts, and cycles attain this.
A natural next question
How many minimum cuts can a graph have?
The survival argument forces at most n(n-1)/2 minimum cuts, and cycles attain this.
The survival proof applies to every minimum cut, so each one is returned with probability at least . The events "the output is the cut " are disjoint for different cuts and their probabilities sum to at most one. Hence a connected graph on vertices has at most minimum cuts. The bound is attained: in the cycle on vertices, deleting any two edges leaves two paths, giving minimum cuts of size two. The four-cycle example above is this case, and there every trial succeeds.
Summary
A fixed minimum cut has crossing edges, while a surviving -supervertex graph has at least edges. The product of the conditional survival probabilities is at least . Independent trials amplify this one-sided success guarantee.
Exercises
Quick check
(What is the guaranteed one-trial success probability when ?)
Substitute into .
Solution · Answer
The bound is .
Quick check
(Why are self-loops discarded after a contraction?)
Ask whether a loop can cross any partition of the supervertices.
Solution · Answer
A self-loop has both endpoints in the same supervertex, so it crosses no partition of the supervertices and cannot contribute to a returned cut. It should not be selected as a contraction edge.
Quick check
(For , give an upper bound on the probability that independent trials all fail.)
Use the one-trial bound and independence.
Solution · Answer
The one-trial success probability is at least , so failure in all six is at most . The exponential bound is another valid, slightly weaker upper bound.
Quick check
(Explain why the minimum returned cut across trials is correct if any trial succeeds.)
Compare the smallest observed size with from both sides.
Solution · Answer
Every trial returns a valid cut, whose size is at least . If one trial returns size , the smallest observed size is both at most and at least , hence is minimum.