Random Sampling and Cuts II

Sampling Theorem

In 1994, Karger gave the following result:

[Sampling Karger] [Using randomized sparsification to approximate minimum cuts] Given a graph G and a collection of random variables $X_e (X_e \le M)$ associated with all edges e, with probability $1 - O(n^{-d})$ that every cut in the instance $G(X_e)$ generated by putting weight $X_e$ on each e has value with $(1 - \epsilon, 1 + \epsilon)$ times its expected value, where

\epsilon = \sqrt{2(d + 2)M\ln n \over c'}

and c' is G's minimum expected value.

As an application, if we fix $\epsilon$ and let $p = \Theta({\ln n \over \epsilon^2 c})$ , where c is the minimum cut of G, then G' approximate all its original graph cuts by a factor p with high probability.

The limitation is that either $\epsilon$ or p depends on c. When c is little, we could not reduce many edges.

Improvement: In 1996, Benczur and Karger improved previous sampling method such that the dependence on c is removed.

New Result:

Given a graph G and a parameter $\epsilon$ , there is a new graph G' such that

G' has $O({n \ln n \over \epsilon^2})$ edges.

every cut in G' has value $(1 \pm \epsilon)$ times its original cut value.

The intuition is that in the dense parts of the graph, each edge can be sample with smaller probability in order to preserve cut value while edge should be sample with higher probability where the graph is sparse.

Before moving on we first formalize the notion of a dense region. We characterize a dense region by Strong Connectivity.

k-Connected

A graph G is k connected if its minimum cut value is no less than k.

Vertex-Induced Subgraph

$G'=<V',E'>$ is a vertex induced subgraph of $G =<V,E>$ if $V'$ is a subset of $V$ and $E'$ is all edges of $E$ whose endpoints are both in $V'$ .

k-Strong Component

A k-Strong Component is a maximal k-connected vertex-induced subgraph.

Strong Connectivity

The strong connectivity $c_e$ of an edge e is the maximum value of k such that a k-Strong component contains e.

Generating the graph

Here is how new sampling technique operates

Given a parameter $\epsilon$ , let $\rho = {16(d + 2)M \ln n \over \epsilon^2}$ , we assign to each edge a random weight $X_e$ , which takes value $1/p$ with probability $p$ and $0$ with probability $(1 - p)$ , where $p = \min \{ \rho / c_e, 1 \}$ . When $X_e = 0$ , we eliminate e from the new graph.

Immediately follows from the definition of $X_e$ we see that $E[X_e] = 1$ .

To check the sampling technique works, we need to verify two things:

The number of edge generated is $O(n \ln n / \epsilon^2)$
Each cut does not deviate much from its original value.

Number of edges

Theorem 1

If an undirected connected graph has k(n - 1) edges, then it must has a k strong component.

Proof: We prove it by induction. When k = 1, then the graph itself is a k-strong component. When n = 2, the theorem clearly holds.

Now we consider the general case. Suppose that the graph does not contain a k-strong component. Then there exist a cut $C = <A, B>$ in the graph such that $cut(A,B) < k$ . Now both A and B have less than n nodes. By induction, A has less then k(|A| - 1) edges inside and B has less then k(|B| - 1) edges inside. The total number of edges is less than k(|A| - 1) + k + k(|B| - 1) = k(|A|+|B| - 1) = k(n - 1). A contradiction.

Theorem 2

$\Sigma {1 \over c_e} < 2(n -1)$

Proof: Suppose that $\Sigma {1 \over c_e} \ge 2(n -1)$ , then by theorem 1, there is a 2-strong component. Let e* be the edge with minimum $c_{e^*}$ in that component. Then there is a cut C in the 2-strong component containing e* such that $cut(C) \le c_{e^*}$ . Now

{\underset{e \in C}{\Sigma }} c_e^{-1} \le c_{e^*}^{-1} c_{e^*} = 1 < 2

A contradiction.

Error analysis

To analyze the errors, we denote $F_i$ the set of edges whose strong connectivity are between $[2^i, 2^{i+1}]$ for $i \ge 0$ . Let $G_i = <V, F_i \cup F_{i + 1} \cup F_{i + 2}...>$ .

In $G_i$ , each edge is sampled in the following way

X_e = \begin{cases} 1, if \ e \notin F_i \\ \begin{Bmatrix} {1 \over p} with \ probability \ p, \\ 0 \ with \ probability \ 1 - p \end{Bmatrix} \ if \ e \in F_i \end{cases}

Then, by sampling theorem, the sampled graph $G_i'$ is within $(1 \pm \epsilon)G_i$ .

\begin{aligned} G' & = \Sigma_{i = 0}^{\log m} F_i' \\ & = \Sigma G_i' - \Sigma G_{i + 1} \\ & = \Sigma (1 \pm \epsilon)G_i - \Sigma G_{i + 1} \\ & = (1 \pm \epsilon)G_0 \pm \epsilon\Sigma G_{i + 1} \\ & \in G \pm \epsilon \log m \ G \end{aligned}

But there is a log m term in the final result. We can eliminate the log m term with more sophisticated techniques.

The random variable $X_e$ assigned to e in $G_i$ is revised as follows:

X_e = \begin{cases} 2^{i - j}, if \ e \notin F_i \ and \ e \in F_j \\ \begin{Bmatrix} {1 \over p} with \ probability \ p, \\ 0 \ with \ probability \ 1 - p \end{Bmatrix} \ if \ e \in F_i \end{cases}

It can be shown that every cut in $G_i$ is at least $2^i$ heavy.

\begin{aligned} G' & = \Sigma_{i = 0}^{\log m} F_i' \\ & = \Sigma G_i' - \Sigma_{i = 0}^{\log m} \Sigma_{j = i + 1}^{\log m} 2^{i - j} F_j \\ & = \Sigma (1 \pm \epsilon)G_i - \Sigma_{i = 0}^{\log m} \Sigma_{j = i + 1}^{\log m} 2^{i - j} F_j \\ & = \Sigma F_i + (1 \pm \epsilon)\Sigma_{i = 0}^{\log m} \Sigma_{j = i + 1}^{\log m} 2^{i - j} F_j - \Sigma_{i = 0}^{\log m} \Sigma_{j = i + 1}^{\log m} 2^{i - j} F_j \\ & = G \pm 2 \epsilon \ \Sigma_{i = 0}^{\log m} \Sigma_{j = i + 1}^{\log m} 2^{i - j} F_j \\ & = G\pm 2 \epsilon \ G \end{aligned}