Randomized algorithm for minimum cuts
In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.
The idea of the algorithm is based on the concept of contraction of an edge formula_1 in an undirected graph formula_2. Informally speaking, the contraction of an edge merges the nodes formula_3 and formula_4 into one, reducing the total number of nodes of the graph by one. All other edges connecting either formula_3 or formula_4 are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probability.
The global minimum cut problem.
A "cut" formula_7 in an undirected graph formula_2 is a partition of the vertices formula_9 into two non-empty, disjoint sets formula_10. The "cutset" of a cut consists of the edges formula_11 between the two parts. The "size" (or "weight") of a cut in an unweighted graph is the cardinality of the cutset, i.e., the number of edges between the two parts, 
 formula_12
There are formula_13 ways of choosing for each vertex whether it belongs to formula_14 or to formula_15, but two of these choices make formula_14 or formula_15 empty and do not give rise to cuts. Among the remaining choices, swapping the roles of formula_14 and formula_15 does not change the cut, so each cut is counted twice; therefore, there are formula_20
The probability formula_21 that the contraction algorithm on an formula_22-vertex graph avoids formula_23 satisfies the recurrence formula_24, with formula_25, which can be expanded as
formula_26
Repeating the contraction algorithm.
By repeating the contraction algorithm formula_27 times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is
formula_28
The total running time for formula_15 repetitions for a graph with formula_22 vertices and formula_31 edges is formula_32.
Karger–Stein algorithm.
An extension of Karger’s algorithm due to David Karger and Clifford Stein achieves an order of magnitude improvement.
The basic idea is to perform the contraction procedure until the graph reaches formula_33 vertices.
 procedure contract(formula_34, formula_33):
 while formula_36
 choose formula_37 uniformly at random
 formula_38
 return formula_39
The probability formula_40 that this contraction procedure avoids a specific cut formula_23 in an formula_22-vertex graph is
formula_43
This expression is approximately formula_44 and becomes less than formula_45 around formula_46. In particular, the probability that an edge from formula_23 is contracted grows towards the end. This motivates the idea of switching to a slower algorithm after a certain number of contraction steps.
 procedure fastmincut(formula_48):
 if formula_49:
 return contract(formula_39, formula_51)
 else:
 formula_52
 formula_53 contract(formula_39, formula_33)
 formula_56 contract(formula_39, formula_33)
Analysis.
The contraction parameter formula_33 is chosen so that each call to contract has probability at least 1/2 of success (that is, of avoiding the contraction of an edge from a specific cutset formula_23). This allows the successful part of the recursion tree to be modeled as a random binary tree generated by a critical Galton–Watson process, and to be analyzed accordingly.
The probability formula_63 that this random tree of successful calls contains a long-enough path to reach the base of the recursion and find formula_23 is given by the recurrence relation
formula_65
with solution formula_66. The running time of fastmincut satisfies
formula_67
with solution formula_68. To achieve error probability formula_69, the algorithm can be repeated formula_70 times, for an overall running time of formula_71. This is an order of magnitude improvement over Karger’s original algorithm.
Improvement bound.
To determine a min-cut, one has to touch every edge in the graph at least once, which is formula_72 time in a dense graph. The Karger–Stein's min-cut algorithm takes the running time of formula_73, which is very close to that.