Karger's algorithm

A graph with two cuts. The dotted line in red is a cut with three crossing edges. The dashed line in green is the min-cut of this graph, crossing only two edges.

In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute the minimum cut of a connected graph. It was invented by David Karger and first published in 1993.

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

The general min-cut problem

Main article: Minimum cut

This problem is that given an undirected graph $G=(V,E)$, trying to find a partition that divides $V$ into a pair of non-empty, disjoint node sets $S\cup T=V$ that minimizes the number of crossed edges between $S$ and $T$:

${\text{minimize }}\sum _{(u,v)\in E}{\mathbf {1} _{S\times T}(u,v)}.$

Algorithm description

Successful run of Karger’s algorithm on a 10-vertex graph. The minimum cut has size 3 and is indicated by the vertex colours.

The fundamental operation of Karger’s algorithm is a form of edge contraction. The result of contracting the edge $e=\{u,v\}$ is new node $uv$. Every edge $\{w,u\}$ or $\{w,v\}$ for $w\notin \{u,w\}$ to the endpoints of the contracted edge is replaced by an edge $\{w,uv\}$ to the new node. Finally, the contracted nodes $u$ and $v$ with all their incident edges are removed. In particular, the resulting graph $G/e$ contains no self-loops.

This algorithm works by repeatedly contracting random edges in the graph, until only two nodes remain, at which point there is only a single cut.

   procedure contract($G=(V,E)$):
   while $|V|>2$
       choose $e\in E$ uniformly at random
       $G\leftarrow G/e$
   return the only cut in $G$

When the graph is represented using adjacency lists or an adjacency matrix, a single edge contraction operation can be implemented with a linear number of updates to the data structure, for a total running time of $O(|V|^{2})$. Alternatively, the algorithm can be viewed as the first constructing the minimum spanning tree in a graph where the edges have weights $w(e_{i})=\pi (i)$ according to a random permutation $\pi$. Removing the heaviest edge of this tree results in two components that describe a cut. In this way, the algorithm can be implemented like Kruskal’s algorithm in time $O(|E|\log |E|)$. The best known implementations use $O(|V|)$ time and space, or $O(|E|\log |E|)$ time and $O(|V|)$ space, respectively.

Analysis

Proof of correctness

Lemma 1: let k denote the actual result of the min-cut of G, every node in the graph has a degree that is equal or larger than k.

Proof: If there exists a node N in G, whose degree is smaller than k, then select N as on one side and the other nodes on the other side. As a result we get a min-cut which is smaller than k. This is a contradiction. ∎

Theorem: With high probability we can find the min-cut of given graph G by executing Karger's algorithm.

Proof: Let C denote the edge set of minimum k-cut. At each stage. we have n − i node and by Lemma 1 there are at least (n − i)k⁄2 edges. As such, the probability of selecting an edge in C to make a contraction is

$Pr[(u,v)\in C]\leq {\frac {k}{(n-i)k/2}}={\frac {2}{n-i}}$

In this manner, we have to run n − 2 iterations to reduce a graph of n nodes to a graph of only two nodes with i from 0 to n − 3. Thus, the probability of C surviving after n − 2 iterations is

${\begin{aligned}Pr[C]&\geq \prod _{i=0}^{n-3}{(1-{\frac {2}{n-i}})}\\&=(1-{\frac {2}{n}})(1-{\frac {2}{n-1}})(1-{\frac {2}{n-2}})\cdots ({\frac {1}{3}})\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}\\&={\frac {2}{n(n-1)}}\end{aligned}}$

Therefore, we have at least Ω(1/n²) chances to find the min-cut C in one execution of procedure contract($G$). Suppose Pr[Failure] indicates that the probability of failing finding the min-cut via executing the inner while loop once. As such if we repeat the procedure T = cn(n − 1)/2 = O(n²) times, the probability of successfully returning C is

${\begin{aligned}\Pr[{\text{Final Success}}]&\geq 1-\Pr[{\text{Failure}}]^{T}\\&=1-(1-{\frac {2}{n(n-1)}})^{T}\\&=1-(1-{\frac {2}{n(n-1)}})^{\frac {cn(n-1)}{2}}\\&=1-{\frac {1}{e^{c}}}>99\%{\text{ when }}c=10.\end{aligned}}$

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 prove 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^{2})$ 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 recurrence is solved by $O(n^{2}log(n))$. One run of an algorithm finds a particular minimum cut with probability $\Omega (1/log(n))$. Running algorithm $log^{2}(n)$ times reduce the chance of missing any particular minimum cut to O(1/n²).

Lemma 2: For each execution of the inner while loop (Line 3–5) of Karger's Basic Algorithm, it takes $O(n^{2})$ running time.

Proof: We can represent this graph G by maintaining an adjacency list, which means all edges incident to node v are in a linked list. What is more, we have to construct pointers between the two copies the same edge (u, w) and (w, u). When v and w are contracted, we traverse the adjacency list of v, and for each edge (v, u) find the corresponding edge(u, v) by the pointer and rename it to (u, w). As such, each contraction costs O(n) time and we have to contract n − 2 times, which in total is O(n²).∎

According to the algorithm, we have to repeat the inner while loop of Karger's Basic Algorithm O(n²) times. Hence, with the correctness of Lemma 2, the overall running time is O(n⁴).

The Karger–Stein's algorithm

This algorithm is developed by David Karger and Clifford Stein. And it is an order of magnitude improvement of the running time compared with Karger's Basic Algorithm.
Before we move forwards to the detailed description, we notice that when we do the contractions until i vertices are left, the probability that C survives is

${\begin{aligned}\Pr[C]&\geq \prod _{j=0}^{n-i}{(1-{\frac {2}{n-j}})}\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {n-i}{n-i+2}}\cdot {\frac {n-i-1}{n-i+1}}\cdot {\frac {n-i-2}{n-i}}\\&={\frac {(n-i-1)(n-i-2)}{n(n-1)}}\\&\in O\left({\frac {i^{2}}{n^{2}}}\right)\end{aligned}}$

Algorithm description

Inspired by the formula above, we can find that the less edges that left in this graph, the less chance that C survives. We, therefore, improve the basic algorithm that

   INPUT:  An undirected graph G = (V, E)

   OUTPUT: find the min-cut of G
   function Karger–Stein's Min-Cut(G):
      1, run the Karger's Basic Algorithm to i = n⁄√2  twice getting G1 and G2,
      2, recursively run the Karger–Stein's Min-Cut Algorithm on G1 and G2
   end function

Running time

Then we can get the probability of min cut survive P(n) (n is the number of vertices) meets this recurrence relation:

$P(n)=1-\left(1-{\frac {1}{2}}P\left({\frac {n}{\sqrt {2}}}\right)\right)^{2}$

Also, we can prove that $P(n)=O\left({\frac {1}{\ln n}}\right)$. and the recurrence relation of running time is

$T(n)=2T\left({\frac {n}{\sqrt {2}}}\right)+O(n^{2}){\text{ and }}T(n)=O(1){\text{ when }}n\leq 2.$

According to the Master Theorem, $T(n)=O(n^{2}\ln n)$. Therefore the overall running time is $T(n)\cdot {\frac {1}{P(n)}}=O(n^{2}\ln ^{2}n)$, which is an order of magnitude improvement.

Finding all min-cuts

Theorem: With high probability we can find all min cuts in the running time of $O(n^{2}\ln ^{3}n)$.

Proof: Since we know that $P(n)=O\left({\frac {1}{\ln n}}\right)$, therefore after running this algorithm $O(\ln ^{2}n)$ times The probability of missing a specific min-cut is

$\Pr[{\text{miss a specific min-cut}}]=(1-P(n))^{O(\ln ^{2}n)}\leq \left(1-{\frac {c}{\ln n}}\right)^{\frac {3\ln ^{2}n}{c}}\leq e^{-3\ln n}={\frac {1}{n^{3}}}$.

And there are at most ${\binom {n}{2}}$ min-cuts, hence the probability of missing ant min-cut is

$\Pr[{\text{miss any min-cut}}]\leq {\binom {n}{2}}\cdot {\frac {1}{n^{3}}}=O\left({\frac {1}{n}}\right).$

The probability of failures is considerably small when n is large enough.∎

Improvement bound

To determine a min-cut, one has to touch every edge in the graph at least once, which is $O(n^{2})$ time. The Karger–Stein's min-cut algorithm takes the running time of $O(n^{2}\ln ^{O(1)}n)$, which is very close to that.