Given a dense graph G=⟨V,E⟩G = \langle V,E \rangle and relative error threshold ϵ\epsilon, we want to get a spare graph G′=⟨V,E′⟩G' = \langle V, E' \rangle, such that G′(S,Sˉ)∈(1±ϵ)G(S,Sˉ)G'(S, \bar{S}) \in (1 \pm \epsilon) G(S, \bar{S}) for any cut (S,Sˉ)∈V×V(S, \bar{S}) \in V \times V, where G′(S,Sˉ)G'(S, \bar{S}) stands for the number of edges between SS and S′S' in G′G'.

G′G' can be constructed as follows:

  1. Keep all vertices VV in G′G',

  2. Keep each edge e∈Ee \in E in G′G' with probability pp. If an edge is kept, set its weight to 1/p1/p.

We will determine the value of pp later.

There are many possible G′G''s -- precisely, 2∣E∣2^{|E|} of G′G''s. At the first glimpse, it not clear what we get out of them. However, we will show that for a large fraction of them satisfy our requirement. In other words, we get a good G′G' with high probability.

To show this, first observe that each edge has expected weight p⋅1/p+(1−p)⋅0=1p \cdot 1 / p + (1 - p) \cdot 0 = 1. Therefore, by linearity of expectation, the expected value of each cut in G′G' equals to its value in GG, i.e., E[G′(S,Sˉ)]=G(S,Sˉ)E[G'(S, \bar{S})] = G(S, \bar{S}), for ∀(S,Sˉ)∈V×V\forall (S, \bar{S}) \in V \times V.

By proper choice of pp, all G′(S,Sˉ)G'(S, \bar{S}) will concentrate around its expectation. Moreover, the more edges a cut (S,Sˉ)∈G(S, \bar{S}) \in G has, the more likely its expectation has a smaller deviation. This motivates that pp is set according to the min-cut of GG.

Throughout discussion below, we denote nn as the number of vertices, mm the number of edges, and c∗c^* the min-cut value in GG.

Two Important Results

The first one is the famous combinatorial ramification of Karger Algorithm.

Theorem 1. The number of cuts whose weight are within αc∗\alpha c^* is upper bounded by n2α22α(2α)!e2π2n^{2 \alpha} \frac{2^{2\alpha}}{ (2\alpha)! } \frac{e}{2 \pi \sqrt 2}, where α≥1,2α∈N+\alpha \ge 1, 2 \alpha \in N^+.

Define f(x)f(x) (x∈R,x≥1x \in R, x \ge 1) the number of cuts in G′G' with value xc∗x c^*, where xc∗x c^* is an integer. F(α)=∑x≤αf(x)F(\alpha) = \sum_{x \le \alpha} f(x) is bounded by n2αn^{2\alpha}.

The second is Chernoff Bound.

Theorem 2. Let {Xi}\{ X_i \} be a set of random variables and X≐ΣXiX \doteq \Sigma X_i, E[X]=μE[X] = \mu, then Pr[∣X−μ∣≥ϵμ]≤2exp⁡(−ϵ2μ/3)Pr[|X - \mu| \ge \epsilon \mu] \le 2 \exp(- \epsilon^2 \mu /3).

By Chernoff bound, the probability that a min-cut derivate more than ϵc∗\epsilon c^* is bounded by 2exp⁡(−ϵ2pc∗/3)2 \exp (-\epsilon^2 p c^* / 3). Similarly, the bound for a cut with value αc∗\alpha c^* is 2exp⁡(−ϵ2αpc∗/3)2 \exp (-\epsilon^2 \alpha p c^* / 3).

Denote c′=cpc' = cp. It follows by union bound that the probability that some cut deviate more than ϵ\epsilon times it expected value is at most ∑xf(x)⋅2exp⁡(−ϵ2xc′/3)\sum_x f(x) \cdot 2 \exp(-\epsilon^2xc'/3).

It can be shown that to maximum this value, we need F(α)F(\alpha) takes the value n2αn^{2 \alpha} any for α≥1,2α∈N+\alpha \ge 1, 2\alpha \in N^+. Hence the sum is less than

2f(1)e−ϵ2c′/3+2∫x=1∞∂n2x∂xe−ϵ2xc′/3dx 2f(1)e^{-\epsilon^2 c' /3} + 2 \int_{x = 1}^\infty {\partial n^{2x} \over \partial x} e^{-\epsilon^2 x c'/ 3} dx

That is

2n2e−ϵ2c′/3(1+ln⁡n2ϵ2c′/3−ln⁡n2) 2 n^2 e^{-\epsilon^2 c' /3}(1 + {\ln n^2 \over \epsilon^2 c' /3 - \ln n^2})

If we let p=3(d+2)ln⁡n/(ϵ2c)p = 3(d + 2) \ln n / (\epsilon^2 c) for some parameter d, then the bound becomes O(n−d)O(n^{-d}).