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 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 into two non-empty, disjoint sets. The cutset 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,

distinct cuts. The minimum cut problem is to find a cut of smallest size among these cuts.

the weight of the cut is the sum of the weights of edges between vertices in each part

.

. Thus, the minimum cut problem can be solved in polynomial time 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.

Contraction algorithm

The fundamental operation of Karger’s algorithm is a form of edge contraction.

The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.

The key idea of the algorithm is that it is far more likely for non min-cut edges than min-cut edges to be randomly selected and lost to contraction, since min-cut edges are usually vastly outnumbered by non min-cut edges. Subsequently, it is plausible that the min-cut edges will survive all the edge contraction, and the algorithm will correctly identify the min-cut edge.

   procedureG=(V,E)):
   while|V| > 2
e\in E uniformly at random
G \leftarrow G/e
   returnG

When the graph is represented using adjacency lists or an adjacency matrix. Alternatively, the procedure can be viewed as an execution of Kruskal’s algorithm for constructing the minimum spanning tree 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.

space, respectively.

Success probability of the contraction algorithm

.

For instance, the cycle graph minimum cuts, given by every choice of 2 edges. The contraction procedure finds each of these with equal probability.

. The minimum degree is

, which can be expanded as

Repeating the contraction algorithm

times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is

.

Karger–Stein algorithm

An extension of Karger’s algorithm due to David Karger and Clifford Stein achieves an order of magnitude improvement.

vertices.

   procedureG=(V,E)t):
   while|V| > t
e\in E uniformly at random
G \leftarrow G/e
   returnG

-vertex graph is

is contracted grows towards the end. This motivates the idea of switching to a slower algorithm after a certain number of contraction steps.

   procedureG= (V,E)):
   if|V| \le 6:
       returnG2)
   else:
t\leftarrow \lceil 1 + |V|/\sqrt 2\rceil
G_1 \leftarrow Gt)
G_2 \leftarrow Gt)
       returnG_1G_2)}

Analysis

). 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.

is given by the recurrence relation

. The running time of fastmincut satisfies

. This is an order of magnitude improvement over Karger’s original algorithm.

Improvement bound

time in a dense graph, which is very close to that.

References