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.^[1]

The idea of the algorithm is based on the concept of contraction of an edge ${\displaystyle (u,v)}$ in an undirected graph ${\displaystyle G=(V,E)}$. Informally speaking, the contraction of an edge merges the nodes ${\displaystyle u}$ and ${\displaystyle v}$ into one, reducing the total number of nodes of the graph by one. All other edges connecting either ${\displaystyle u}$ or ${\displaystyle v}$ 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.