Karger's algorithm

In computer science and graph theory, Karger's algorithm is a Monte Carlo method to compute the minimum cut of a connected graph. It was developed by David Karger.

Algorithm

The idea of the algorithm is based on the concept of contraction of an edge e in a graph G = (V,E). Informally speaking, the contraction of an edge makes the two nodes joined by e overlap, reducing the total number of nodes of the graph by one. Algorithm based on a sequences of contractions of a randomly chosen edge in a graph. The edges are selected proportional to its weight. The algorithm is recursive. One level of recursion consists of two independent trials of contraction of G to $\left\lceil n / \sqrt{2} + 1 \right\rceil$ vertices followed by a recursion call.

Contraction

Informally speaking, this operation takes an edge e with endpoints x and y and contracts it into a new node v_e which becomes adjacent to all former neighbors of x and y. It is possible to formalize this concept in mathematical terms.

Given a graph $G = \left ( V, E \right )$ and $e = \lbrace x, y \rbrace \in E$, the contraction of G respect to e (written $G/e = \left ( V', E'\right )$) is a multigraph where:

$V' = \left( V \setminus \lbrace x, y \rbrace \right) \cup \lbrace v_e \rbrace$

and:

$E' = \lbrace \lbrace v, w \rbrace \in E \mid \lbrace v,w \rbrace \cap \lbrace x,y \rbrace = \emptyset \rbrace \cup \lbrace \lbrace v_e,w \rbrace \mid \lbrace x,w \rbrace \in E \setminus \lbrace e \rbrace$ or $\lbrace y,w \rbrace \in E \setminus \lbrace e \rbrace \rbrace$

It is possible to prove that this operation doesn't reduce the cardinality of the minimum cut, but that it might increase it.

Running time

Karger's algorithm is the fastest known minimum cut algorithm, is randomized, and computes a minimum cut with high probability in time O(|V|² log³|V|). To proove this authors at first mention that contraction of G to $\left\lceil n / \sqrt{2} + 1 \right\rceil$ vertices can be implemented in O(n²) time. And the running time is $T(n) = 2 \left( n^2 + T\left( \left\lceil n / \sqrt{2} + 1 \right\rceil \right) \right)$. This recurence is solved by O(n²log(n)). One run of an algorithm finds a particular minimum cut with probability Ω(1 / log(n)). Running algorithm log²(n) times reduce the chance of missing any particular minimum cut to O(1/n²).

References

1. David R. Karger, Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993
2. David R. Karger and Clifford Stein, A New Approach to the Minimum Cut Problem. Journal of the ACM 43(4):601-640, 1996