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.
Contents |
Algorithm
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 makes the two nodes joined by overlap, reducing the total number of nodes of the graph by one. The algorithm is based on 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 
to 
vertices followed by a recursion call.
Contraction
Informally speaking, this operation takes an edge e with endpoints x and 
and contracts it into a new node 
which becomes adjacent to all former neighbors of x and y. It is possible to formalize this concept in mathematical terms.
Given a graph 
and 
, the contraction of with respect to (written 
) is a multigraph where:
and:
or 
It is possible to prove that this operation does not 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|2 log3|V|). To prove this authors at first mention that contraction of to vertices can be implemented in 
time. And the running time is 
. This recurrence is solved by 
. One run of an algorithm finds a particular minimum cut with probability 
. Running algorithm 
times reduce the chance of missing any particular minimum cut to O(1/n2).
References
- 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
- David R. Karger and Clifford Stein, A New Approach to the Minimum Cut Problem. Journal of the ACM 43(4):601-640, 1996
