Karger's algorithm

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

Algorithm

The idea of the algorithm is based on the concept of contraction of an edge $e$ in a graph. 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. The algorithm proceeds iterating contractions until only two nodes are left in the graph. With high probability, the algorithm will return a minimal cut by returning the set of edges joining the two remaining nodes.

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\; ight\; )$ and $e\; =\; lbrace\; x,\; y\; brace\; in\; E$, the contraction of $G$ respect to $e$ (written $G/e\; =\; left\; (\; V\text{'},\; E\text{'}\; ight\; )$) is a multigraph where:

:$V\text{'}\; =\; left(\; V\; setminus\; lbrace\; x,\; y\; brace\; ight)\; cup\; lbrace\; v\_e\; brace$

and:

:$E\text{'}\; =\; lbrace\; lbrace\; v,\; w\; brace\; in\; E\; mid\; lbrace\; v,w\; brace\; cap\; lbrace\; x,y\; brace\; =\; emptyset\; brace\; cup\; lbrace\; lbrace\; v\_e,w\; brace\; mid\; lbrace\; x,w\; brace\; in\; E\; setminus\; lbrace\; e\; brace$ or $lbrace\; y,w\; brace\; in\; E\; setminus\; lbrace\; e\; brace\; brace$

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

Pseudocode

The algorithm can be implemented using two functions:

function Karger(G, K) min := $+\; infty$ for i = 1 to K do t := Full_contraction(G) if t < min then min := t return min

function Full_contraction(G) for i := 1 to |V| - 2 do e := Random($varepsilon$) G' = ( V', $varepsilon$') := $G\; /\; e$ V := V' $varepsilon$ := $varepsilon$' return |$varepsilon$

The function Full_contraction implements the contraction of the edges following the given definition. The iteration lasts until only two nodes are left in the graph. With a certain probability, the set of edges left are the minimum cut.It is not sure anyway that this algorithm returns a cut which is minimum, therefore K execution of Full_contraction is performed by the Karger function, where K has to be passed as a parameter. Computing the minimum of the K executions reduces the probability of having a wrong minimum cut returned.

References

# A. A. Tsay, W. S. Lovejoy, David R. Karger, [http://www.cs.elte.hu/~benczur/CombOptStuff/sampling.ps.gz Random Sampling in Cut, Flow, and Network Design Problems] , Mathematics of Operations Research, 24(2):383–413, 1999.