Algorithm

Let G=(V,E)G = (V, E) be an undirected connected graph with nn vertices, mm edges, and min-cut size c∗c^*. David R. Karger [1] proposed a simple randomized algorithm for estimating the value of c∗c^*, as described thus.

Karger Algorithm.

  1. repeat until two nodes are left in the graph:
  2. \qquad Select an edge e=(u,v)e = (u,v) from the graph uniformly at random.
  3. \qquad Merge its endpoints uu and vv into new vertex ww.
  4. \qquad Remove self loops created by the merge.
  5. \qquad Connect the edges incident to uu or vv to new vertex ww.
  6. Return the number of edges, denoted as cc, between the remaining two vertices.

Each iteration in the algorithm is called a contraction.

Analysis

Theorem. It holds that

Pr⁡[c=c∗]=2n(n−1). \Pr[ c = c^* ] = \frac{2}{n(n - 1)}.

We can boost the successful probability via repetitions.

Corollary. If we repeat the algorithm 0.5⋅n⋅(n−1)⋅ln⁡n0.5 \cdot n \cdot (n - 1) \cdot \ln n times, the probability we don't find c∗c^* is at most 1/n1 / n.

Proof of the Corollary.

(1−2n(n−1))0.5⋅n⋅(n−1)⋅ln⁡n≤eln⁡n=1n \left( 1 - \frac{2}{n (n - 1)} \right)^{0.5 \cdot n \cdot (n - 1) \cdot \ln n} \le e^{\ln n} = \frac{1}{n}

□\square

Proof of the Theorem.

Consider the first iteration of the algorithm. The key observation is that the degree of each vertex is at least c∗c^*. Therefore,

m≥c∗⋅n/2. m \ge c^* \cdot n / 2.

Fix a min-cut in GG, the probability that any of its edges is selected at most

c∗m≤2n. \frac{c^*}{m} \le \frac{2} { n }.

Therefore, with probability at least 1−2/n1 - 2 / n, none of the edges in the chosen min-cut is contracted in the first iteration. Moreover, we have the following observation.

After contracting an edge, each cut in the new graph corresponds to a cut in the original graph.

Therefore, if none of the edges of the chosen min-cut is contracted, it remains to be the min-cut in the new graph. Conditioned on this, via similar argument, we can prove that in the second iteration, none of the edges of the chosen min-cut is contracted with probability at least 1−2/(n−1)1 - 2 / (n - 1).

By induction, it holds that, none of the edges of the chosen min-cut is contracted over all iterations is given by

(1−2n)(1−2n−1)…(1−23)=(n2)−1. \left(1 - \frac{2}{n} \right) \left(1 - \frac{2}{n - 1} \right) \ldots \left(1 - \frac{2}{3} \right) = \binom{n}{2}^{-1}.

□\square

Number of Min Cuts

Corollary. There are n(n−1)/2n (n - 1) / 2 min-cuts in the graph.

Proof.
The events of outputting different min-cuts are disjoint.
□\square

By slightly modifying the algorithm, we can obtain another useful fact.

Theorem. (Approximate Min-Cut). Given t∈[1,n/2]t \in [1, n / 2], an tt-minimal cut is a cut with value ≤tc∗\le t c^*. It follows that the number of tt-minimal cut is bounded by

O(22t⋅n(n−2t)⋅2t(nn−2t)n−2t(n2t)2t) O \left( 2^{2t} \cdot \sqrt{ \frac{n}{(n - 2t) \cdot 2t} } \left( \frac{n}{n - 2t} \right)^{n - 2t} \left( \frac{n}{2t} \right)^{2t}\right)

Remark. The bound can be further upper bounded by

O(n(n−2t)⋅2t⋅exp⁡(2tn−2t⋅(n−2t))⋅(nt)2t)⊆O((e⋅nt)2t). \begin{aligned} &O \left( \sqrt{ \frac{n}{(n - 2t) \cdot 2t} } \cdot \exp \left( \frac{2t}{n - 2t} \cdot (n - 2t) \right) \cdot \left( \frac{n}{t} \right)^{2t} \right) \subseteq O \left( \left( \frac{e \cdot n}{t} \right)^{2t} \right). \end{aligned}

Proof. Suppose we run the contraction algorithm, until k=⌈2t⌉k = \lceil 2t \rceil are left. Then we output one of the 2k2^k cuts uniformly at random. The probability pp that a particular tt-minimal cut is outputted is given by

p≐12k⋅(1−2tn)⋅(1−2tn−1)⋅(1−2tk+1)=12k⋅(n−2t)⋅(n−1−2t)⋅…(k+1−2t)n⋅(n−1)⋅…⋅(k+1). \begin{aligned} p &\doteq \frac{1}{2^k} \cdot \left( 1 - \frac{2t}{n} \right) \cdot \left( 1 - \frac{2t}{n - 1} \right) \cdot \left( 1 - \frac{2t}{k + 1} \right) \\ &= \frac{1}{2^k} \cdot\frac{ (n - 2t) \cdot (n - 1 - 2t) \cdot \ldots (k + 1 - 2t)}{ n \cdot (n - 1) \cdot \ldots \cdot (k + 1)}. \end{aligned}

Denote a=k−2t∈[0,1)a = k - 2t \in [0, 1), b=n−2tb = n - 2t, and

f=∏i∈[n−2k](a+i). f = \prod_{ i \in [n - 2k] } (a + i).

We rely on the following lemmas and facts.

Lemma.

f∈Θ(n−2t(n−2te)n−2t). f \in \Theta \left( \sqrt{n - 2t} \left( \frac{n - 2t}{e} \right)^{n - 2t} \right).

Fact (Stirling's Approximation).

n!∈Θ(n(ne)n),k!∈Θ(k(ke)k). n! \in \Theta \left( \sqrt{n} \left( \frac{n}{e} \right)^{n}\right), \quad k! \in \Theta \left( \sqrt{k} \left( \frac{k}{e} \right)^{k}\right).

It follows that

p=12k⋅f⋅k!n!∈Θ(12k⋅(n−2t)⋅kn⋅(n−2t)n−2tkknn). p = \frac{1}{2^k} \cdot \frac{f \cdot k!}{n!} \in \Theta \left( \frac{1}{2^k} \cdot \frac{ \sqrt{(n - 2t) \cdot k}}{n} \cdot \frac{\left( n - 2t \right)^{n - 2t} k^k }{ n^n } \right).

□\square

It remains to prove the lemma.

Proof of the Lemma. Note

ln⁡f=∑i∈[n−2k]ln⁡(a+i). \begin{aligned} \ln f &= \sum_{ i \in [n - 2k] } \ln (a + i). \end{aligned}

For each r≥1r \ge 1, define

Ur≐∫rr+1ln⁡x dx=(xln⁡x−x)∣rr+1=ln⁡(r+1)r+1rr−1, U_r \doteq \int_{r}^{r + 1} \ln x \, dx = \left( x \ln x - x \right) \mid_r^{r + 1} = \ln \frac{(r + 1)^{r + 1}}{r^r} - 1,

and

Lr≐12(ln⁡r+ln⁡(r+1))=ln⁡r(r+1). L_r \doteq \frac{1}{2} \big( \ln r + \ln (r + 1) \big) = \ln \sqrt{ r (r + 1) }.

Denote the gap between them as ϵr≐Ur−Lr\epsilon_r \doteq U_r - L_r. Then

ln⁡f=∑i∈[n−2k]ln⁡(a+i)=12(ln⁡(a+1)+ln⁡b)+∑i∈[n−2k−1]La+i. \begin{aligned} \ln f = \sum_{ i \in [n - 2k] } \ln (a + i) = \frac{1}{2} \left( \ln (a + 1) + \ln b \right) + \sum_{i \in [n - 2k - 1] } L_{a + i}. \end{aligned}

Moreover, via that a+1∈[1,2)a + 1 \in [1, 2),

U≐∑i∈[n−2k−1]Ua+i=∫a+1bln⁡x dx=(bln⁡b−(a+1)ln⁡(a+1)−(b−a−1))∈Θ(bln⁡b−b). \begin{aligned} U &\doteq \sum_{i \in [n - 2k - 1] } U_{a + i} = \int_{a + 1}^{b} \ln x \, dx \\ &= \big( b \ln b - (a + 1) \ln (a + 1) - (b - a - 1) \big) \in \Theta (b \ln b - b). \end{aligned}

Therefore,

(ln⁡f)−U∈Θ(12ln⁡b+bln⁡b−b−∑i∈[n−2k−1]ϵa+i). \big( \ln f \big) - U \in \Theta \left( \frac{1}{2} \ln b + b \ln b - b - \sum_{i \in [n - 2k - 1] } \epsilon_{a + i} \right).

Finally,

ϵr≐Ur−Lr=ln⁡(r+1)r+0.5rr+0.5−1=(r+0.5)ln⁡r+1r−1. \begin{aligned} \epsilon_r &\doteq U_r - L_r = \ln \frac{(r + 1)^{r + 0.5}}{r^{r + 0.5}} - 1 = (r + 0.5) \ln \frac{r + 1}{r} - 1. \end{aligned}

We will prove that ϵr∈Θ(1/r2)\epsilon_r \in \Theta(1 / r^2). Let 1/z≐2⋅(r+0.5)=2r+11 / z \doteq 2 \cdot (r + 0.5) = 2r + 1. Then

ϵr=12z⋅ln⁡1/z+11/z−1−1=12z⋅ln⁡1+z1−z−1=12z⋅(−∑i∈N+(−z)ii+∑i∈N+zii)−1=1z⋅(z+z33+z55+…)−1=z23+z45+z67+…. \begin{aligned} \epsilon_r &= \frac{1}{2 z} \cdot \ln \frac{1 / z + 1}{1 / z - 1} - 1 = \frac{1}{2 z} \cdot \ln \frac{1 + z}{1 - z} - 1\\ &= \frac{1}{2 z} \cdot \left( -\sum_{ i \in \mathbb{N}^+ } \frac{(-z)^i}{i} + \sum_{ i \in \mathbb{N}^+ } \frac{z^i}{i} \right) - 1 \\ &= \frac{1}{z} \cdot \left( z + \frac{z^3}{3} + \frac{z^5}{5} + \ldots \right) - 1 \\ &= \frac{z^2}{3} + \frac{z^4}{5} + \frac{z^6}{7} + \ldots. \end{aligned}

It follows that

ϵr∈Θ(z23(1+z2+z4+…))⊂Θ(z23⋅11−z2)⊂Θ(13⋅1(2r+1)2−1)⊂Θ(131(2r+2)⋅2r)⊂Θ(112⋅(1r−1r+1)), \begin{aligned} \epsilon_r &\in \Theta \left( \frac{z^2}{3} \left( 1 + z^2 + z^4 + \ldots \right) \right) \\ &\subset \Theta \left( \frac{z^2}{3} \cdot \frac{1}{1 - z^2} \right) \\ &\subset \Theta \left( \frac{1}{3} \cdot \frac{1}{ (2 r + 1)^2 - 1} \right)\\ &\subset \Theta \left( \frac{1}{3} \frac{1}{(2r + 2) \cdot 2r} \right) \\ &\subset \Theta \left( \frac{1}{12} \cdot \left( \frac{1}{r} - \frac{1}{r + 1}\right) \right), \end{aligned}

and

∑i∈[n−2k−1]ϵa+i∈Θ(112⋅∑i∈[n−2k−1](1a+i−1a+i+1))⊂Θ(1). \begin{aligned} \sum_{i \in [n - 2k - 1] } \epsilon_{a + i} \in \Theta \left( \frac{1}{12} \cdot \sum_{i \in [n - 2k - 1] } \left( \frac{1}{a + i} - \frac{1}{a + i + 1}\right) \right) \subset \Theta \left( 1 \right). \end{aligned}

□\square

Reference

[1] Karger, David R. "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm." Soda. Vol. 93. 1993.

[2] D. R. Karger and C. Stein, “A new approach to the minimum cut problem,” J. ACM, 1996.