Karger's Contraction Algorithm

External

• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/FKAnq/random-contraction-algorithm
• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/4TLKM/analysis-of-contraction-algorithm

Overview

The algorithm was devised by David Karger. The input of the algorithm is an undirected graph G=(V, E). Parallel edges are allowed. The basic idea is to use random sampling - randomly choose an edge and contract its vertices.

There is one main loop. Each iteration in this loop is going to decrease the number of vertices in the graph by one. The loop terminates when there are only two vertices left.

At a given iteration:

• Pick an edge uniformly at random.
• Take the endpoints of the edge and fuse them into a single vertex.
• The merging may create parallel edges - that's OK.
• The merging may create self-loops, those should be removed.

The number of vertices decreases by one in each iteration, and when there are only two vertices left, return the cut represented by those two vertices. The number of crossing edges is represented by the number of edges between those two remaining vertices.

The result for one contraction depends on the random choices of edges to contract and it is likely sub-optimal. However, repeating the contraction converges to a minimum. We need to do at least n²ln n trials.

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/04-graphs/src/main/java/playground/standford/graphs/AdjacencyListGraph.java