Karger's algorithm

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 in an undirected graph . Informally speaking, the contraction of an edge merges the nodes and into one, reducing the total number of nodes of the graph by one. All other edges connecting either or 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. Minimum cut A cut in an undirected graph is a partition of the vertices into two non-empty, disjoint sets . The cutset of a cut consists of the edges 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 ways of choosing for each vertex whether it belongs to or to , but two of these choices make or empty and do not give rise to cuts. Among the remaining choices, swapping the roles of and does not change the cut, so each cut is counted twice; therefore, there are distinct cuts. The minimum cut problem is to find a cut of smallest size among these cuts. For weighted graphs with positive edge weights 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 . A cut is sometimes called a “global cut” to distinguish it from an “- cut” for a given pair of vertices, which has the additional requirement that and . Every global cut is an - cut for some . Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of and solving the resulting minimum - 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.