Randomized Algs:Randomized Min-Cut

This blog, we still talk about randomized algorithms. Today we will focus on Randomized Min-Cut Algorithm.

Problem definition and Randomized Algorithm

Min-Cut Problem: Given a connected graph ${G = (V, E)}$, Our goal is to find smallest ${C \subseteq E}$ that splits ${G}$.

${C}$ is called a min-cut, and we define ${\lambda(G) := \vert C\vert}$ is the edge connectivity of ${G}$.

Then, we give the pseudocode of Randomized Min-Cut Algorithm as below

1
2
3
4
5
function RandMinCut(V, E)
    while |V| > 2 do
        Pick e ∈ E uniformly at random.
        Contract e and remove self-loops.
    return E

Note: In this algorithm, we contract an edge in graph ${G}$ each time, and finally, we left two “nodes” in graph. In fact, the two nodes represent two components, and we return the edges between the two components as result.

Analysis of Algorithm

Observation 1: RandMinCut${(G)}$ may return a cut of size greater than ${\lambda(G)}$.

Observation 2: A specific min-cut ${C}$ is returned, if and only if any of the edge from ${C}$ isn’t contracted.

Lemma: ${G_i = (V_i, E_i)}$ with ${n_i = n - i}$ vertices, we have ${\lambda(G_i) \geq \vert C \vert}$.

Proof. We will show following statement to prove this lemma

Given a graph ${G=(V,E)}$, we contract an edge ${e={u,v}}$ and get graph ${G/e}$. Then we have ${\lambda(G/e) \geq \lambda(G)}$.

We denote ${G/e=(V’,E’)}$, and

\[V'=V\cup \{w\}\setminus\{u,v\}\] \[E'=E\cup \left\{\{w,t\} \mid \{v,t\} \{u,t\} \in E\right\} \setminus N(v) \setminus N(u)\]

Suppose ${\lambda(G/e) < \lambda(G)}$, we denote the minimum cut of ${G/e}$ is ${C’}$.

Case 1: ${N(w) \cap C’ = \emptyset}$, that means vertex ${w}$ is not incident to any edge in ${C’}$. Hence, let ${C=C’}$, we know ${C}$ is also a cut of ${G}$. We have ${\vert C \vert = \vert C’ \vert = \lambda(G/e)}< \lambda(G)$, which contradicts to the definition of ${\lambda(G)}$.
Case 2: ${N(w) \cap C’ \neq \emptyset}$, that means vertex ${w}$ is incident to some edge ${e = \{w,t\} \in C’}$. If we replace the edges in ${C’}$ like ${\{w,t\}}$ as original edges ${\{v,t\} }$ or ${\{u,t\}}$ and construct ${C \subseteq E}$. We have ${\vert C \vert = \vert C’ \vert = \lambda(G/e)}< \lambda(G)$, which contradicts to the definition of ${\lambda(G)}$. ${}$

By, this statement we have $\vert C \vert = \lambda(G_0) \leq \lambda(G_1) \leq \cdots \leq \lambda(G_i)$ Hence, we prove the lemma. ${\square}$

Theorem: For any min-cut ${C}$, the probability that RandMinCut${(G)}$ returns ${C}$ is ${\geq \frac{2}{n(n-1)}}$.

Proof. Let ${e_1,\cdots,e_{n-2}}$ be the contracted edges, ${G_0 = G}$ and ${G_i = G_{i-1} / e_i}$. We define event ${\mathcal{E}_i := [e_i \not\in C]}$. $C$ is returned iff ${\mathcal{E}_1 \cap \ldots \cap \mathcal{E}_{n-2}}$.

Now, we need compute the Conditional Probabilities

Given events ${\mathcal{E}_1, \mathcal{E}_2}$, the conditional probability of ${\mathcal{E}_2}$ given ${\mathcal{E}_1}$ is defined as

\[Pr[\mathcal{E}_2|\mathcal{E}_1] = \frac{Pr[\mathcal{E}_1 \cap \mathcal{E}_2]}{Pr[\mathcal{E}_1]}\]

Then we have that $Pr[\mathcal{E}_1 \cap \mathcal{E}_2] = Pr[\mathcal{E}_1] \cdot Pr[\mathcal{E}_2|\mathcal{E}_1]$

By induction, for events ${\mathcal{E}_1, \ldots, \mathcal{E}_k}$, we have

\[Pr\left[\bigcap_{i=1}^k \mathcal{E}_i\right] = Pr[\mathcal{E}_1] \cdot Pr[\mathcal{E}_2|\mathcal{E}_1] \cdots Pr\left[\mathcal{E}_k \Bigg| \bigcap_{i=1}^{k-1} \mathcal{E}_i\right]\]

Hence, we have the probability that ${C}$ is returned

\[\begin{aligned} Pr[C \text{ returned}] &= Pr[\mathcal{E}_1 \cap \ldots \cap \mathcal{E}_{n-2}] \\ &= Pr[\mathcal{E}_1] \cdot Pr[\mathcal{E}_2|\mathcal{E}_1] \cdot \ldots \cdot Pr[\mathcal{E}_{n-2}|\mathcal{E}_1 \cap \ldots \cap \mathcal{E}_{n-3}] \\ &= \prod_{i=1}^{n-2} p_i \end{aligned}\]

where ${p_i = Pr[\mathcal{E}_i \mid \mathcal{E}_1 \cap \cdots \cap \mathcal{E}_{i-1}] }$.

By lemma, we have ${\lambda(G_i)\geq \vert C \vert}$. So ${\vert E_i \vert = \frac{1}{2}\sum_{v \in V_i} d(v) \geq \frac{n_i}{2}\lambda(G_i) \geq \frac{n_i}{2}\vert C\vert}$ (Otherwise for some ${v \in V_i, d(v) \leq \lambda(G_i)}$, we can pick up all the edges that are incident to vertex ${v}$ as a cut that is smaller than min-cut).

Then, we have (denote the ${n_i:= \vert V_i \vert = n-i}$, and we also use the assumption that no edge from $C$ has been contracted yet.)

\[\begin{aligned} 1 - p_i &= Pr[\text{select }e \in E_{i-1} \text{ in } C \big| \cap^{i-1}_{j=1}\mathcal{E}] \\ &= \frac{|C|}{|E_{i-1}|} \\ &\leq \frac{|C|}{\frac{1}{2}n_{i-1}|C|} \\ &= \frac{2}{n - (i - 1)} = \frac{2}{n + 1 - i} \end{aligned}\]

Thus, we have

\[p_i \geq 1 - \frac{2}{n + 1 - i} = \frac{n - 1 - i}{n + 1 - i}\] \[\require{cancel} \begin{aligned} Pr[C \text{ returned}] &= \prod_{i=1}^{n-2} p_i \quad \text{where } p_i = Pr[\mathcal{E}_i | \mathcal{E}_1 \cap \ldots \cap \mathcal{E}_{i-1}] \\ &\geq \prod_{i=1}^{n-2} \frac{n - 1 - i}{n + 1 - i} \\ &= \frac{\bcancel{n - 2}}{n} \cdot \frac{\bcancel{n - 3}}{n - 1} \cdot \frac{\bcancel{n - 4}}{\bcancel{n - 2}} \cdot \cdots \frac{\bcancel{3}}{\bcancel{5}} \cdot \frac{2}{\bcancel{4}} \cdot \frac{1}{\bcancel{3}} \\ &= \frac{2}{n(n - 1)} \end{aligned}\]

Hence, we prove ${Pr[C \text{ returned}]\geq \frac{2}{n(n - 1)} }$. ${\square}$

Repeat makes better

Actually, the above probability is not a good result, but we can repeatedly call RandMinCut${(G)}$ to get better result and return the smallest cut. If we call it ${t\frac{n(n-1)}{2}}$ times, we have $\begin{aligned} \Pr[\text{not a min-cut}] &\leq \left(1 - \frac{2}{n(n - 1)}\right)^{t\frac{n(n-1)}{2}} \\ &\leq \left(e^{-\frac{2}{n(n-1)}}\right)^{t\frac{n(n-1)}{2}} \\ &= e^{-t} \end{aligned}$

(This uses that $1 + x \leq e^x$ for all $x \in \mathbb{R}$.)