A cut ( S , T ) in an undirected graph G = ( V , E ) is a partition of the vertices V into two non-empty, disjoint sets S ∪ T = V . The cutset of a cut consists of the edges { u v ∈ E : u ∈ S , v ∈ T } 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,
There are 2 | V | ways of choosing for each vertex whether it belongs to S or to T , but two of these choices make S or T empty and do not give rise to cuts. Among the remaining choices, swapping the roles of S and T does not change the cut, so each cut is counted twice; therefore, there are 2 | V | − 1 − 1 distinct cuts. The minimum cut problem is to find a cut of smallest size among these cuts.
For weighted graphs with positive edge weights w : E → R + the weight of the cut is the sum of the weights of edges between vertices in each part
which agrees with the unweighted definition for w = 1 .
A cut is sometimes called a “global cut” to distinguish it from an “ s - t cut” for a given pair of vertices, which has the additional requirement that s ∈ S and t ∈ T . Every global cut is an s - t cut for some s , t ∈ V . Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of s , t ∈ V and solving the resulting minimum s - t cut problem using the max-flow min-cut theorem and a polynomial time algorithm for maximum flow, such as the push-relabel algorithm, though this approach is not optimal. Better deterministic algorithms for the global minimum cut problem include the Stoer–Wagner algorithm, which has a running time of O ( m n + n 2 log n ) .
The fundamental operation of Karger’s algorithm is a form of edge contraction. The result of contracting the edge e = { u , v } is new node u v . Every edge { w , u } or { w , v } for w ∉ { u , v } to the endpoints of the contracted edge is replaced by an edge { w , u v } to the new node. Finally, the contracted nodes u and v with all their incident edges are removed. In particular, the resulting graph contains no self-loops. The result of contracting edge e is denoted G / e .
The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.
procedure contract(
G = ( V , E ) ):
while | V | > 2 choose
e ∈ E uniformly at random
G ← G / e return the only cut in
G When the graph is represented using adjacency lists or an adjacency matrix, a single edge contraction operation can be implemented with a linear number of updates to the data structure, for a total running time of O ( | V | 2 ) . Alternatively, the procedure can be viewed as an execution of Kruskal’s algorithm for constructing the minimum spanning tree in a graph where the edges have weights w ( e i ) = π ( i ) according to a random permutation π . Removing the heaviest edge of this tree results in two components that describe a cut. In this way, the contraction procedure can be implemented like Kruskal’s algorithm in time O ( | E | log | E | ) .
The best known implementations use O ( | E | ) time and space, or O ( | E | log | E | ) time and O ( | V | ) space, respectively.
In a graph G = ( V , E ) with n = | V | vertices, the contraction algorithm returns a minimum cut with polynomially small probability ( n 2 ) − 1 . Every graph has 2 n − 1 − 1 cuts, among which at most ( n 2 ) can be minimum cuts. Therefore, the success probability for this algorithm is much better than the probability for picking a cut at random, which is at most ( n 2 ) / ( 2 n − 1 − 1 )
For instance, the cycle graph on n vertices has exactly ( n 2 ) minimum cuts, given by every choice of 2 edges. The contraction procedure finds each of these with equal probability.
To establish the bound on the success probability in general, let C denote the edges of a specific minimum cut of size k . The contraction algorithm returns C if none of the random edges belongs to the cutset of C . In particular, the first edge contraction avoids C , which happens with probability 1 − k / | E | . The minimum degree of G is at least k (otherwise a minimum degree vertex would induce a smaller cut), so | E | ≥ n k / 2 . Thus, the probability that the contraction algorithm picks an edge from C is
The probability p n that the contraction algorithm on an n -vertex graph avoids C satisfies the recurrence p n ≥ ( 1 − 2 n ) p n − 1 , with p 2 = 1 , which can be expanded as
By repeating the contraction algorithm T = ( n 2 ) ln n times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is
The total running time for T repetitions for a graph with n vertices and m edges is O ( T m ) = O ( n 2 m log n ) .
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 t vertices.
procedure contract(
G = ( V , E ) ,
t ):
while | V | > t choose
e ∈ E uniformly at random
G ← G / e return G The probability p n , t that this contraction procedure avoids a specific cut C in an n -vertex graph is
p n , t ≥ ∏ i = 0 n − t − 1 ( 1 − 2 n − i ) = ( t 2 ) / ( n 2 ) .
This expression is approximately t 2 / n 2 and becomes less than 1 2 around t = n / 2 . In particular, the probability that an edge from C 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(
G = ( V , E ) ):
if | V | ≤ 6 :
return mincut(
V )
else:
t ← ⌈ 1 + | V | / 2 ⌉ G 1 ← contract(
G ,
t )
G 2 ← contract(
G ,
t )
return min {fastmincut(
G 1 ), fastmincut(
G 2 )}
The probability P ( n ) the algorithm finds a specific cutset C is given by the recurrence relation
with solution P ( n ) = O ( 1 log n ) . The running time of fastmincut satisfies
with solution T ( n ) = O ( n 2 log n ) . To achieve error probability O ( 1 / n ) , the algorithm can be repeated O ( log n / P ( n ) ) times, for an overall running time of T ( n ) ⋅ log n P ( n ) = O ( n 2 log 3 n ) . This is an order of magnitude improvement over Karger’s original algorithm.
Theorem: With high probability we can find all min cuts in the running time of O ( n 2 ln 3 n ) .
Proof: We know that P ( n ) = O ( 1 ln n ) , therefore after running this algorithm O ( ln 2 n ) times the probability of missing a specific min-cut is
And there are at most ( n 2 ) min-cuts, hence the probability of missing any min-cut is
The probability of failures is considerably small when n is large enough.∎
To determine a min-cut, one has to touch every edge in the graph at least once, which is O ( n 2 ) time in a dense graph. The Karger–Stein's min-cut algorithm takes the running time of O ( n 2 ln O ( 1 ) n ) , which is very close to that.
