CSCE 411 Lecture 25

Lecture Handout

« previous | Friday, October 26, 2012 | next »

Minimum Cut Algorithm

Contract edges at random until two nodes remain.

def contract G
  until g.vertices.size = 2
    e = g.edges.sample
    g /= e
  end
  g.edges.size
end

Count the number of edges remaining in the graph.

Minimum cut has fewest edges $m$ between two partitions. The chances that we'll contract one of these edges (thus getting rid of it) are very low: ${\tfrac {m}{|E|}}$.

Analysis

$Pr[E\cap F]=Pr[E\mid F]\,Pr[F]$

Therefore

$Pr\left[\bigcap _{\ell =1}^{n}E_{\ell }\right]=\left(\prod _{m=2}^{n}Pr\left[E_{m}\mid \bigcap _{\ell =1}^{m-1}E_{\ell }\right]\right)Pr[E_{1}]$

Let $G=(V,E)$ be a loop-free connected multigraph with $n=|V|$ vertices.

The program terminates after performing $n=2$ contractions.

Suppose that $C$ is a particular minimum cut of $G$.

Let $E_{i}$ denote the event that the algorithm selects an edge in the $i$^th iteration that does not cross the cut $C$. Therefore, the probability that no edge crossing the cut $C$ is ever picked during an execution of the algorithm is

$Pr[\bigcap _{j=1}^{n-2}E_{i}]=\left(\prod _{m=2}^{n-2}Pr\left[E_{m}\mid \bigcap _{\ell =1}^{m-1}E_{\ell }\right]\right)Pr[E_{1}]$

Suppose that the size of the minimum cut $C$ is $k$. This means that the degree of each vertex is at least $k$; hence, there exists at least ${\tfrac {kn}{2}}$ edges.

The probability to select an edge crossing $C$ in the first step is at most ${\tfrac {k}{kn/2}}={\tfrac {2}{n}}$.

Thus

$Pr[E_{1}]\geq 1-{\frac {2}{n}}={\frac {n-2}{n}}$

At the beginning of the $m$^th iteration, there are $n-m+1$ remaining vertices. The minimum cut is tstill at least $k$, hence the graph at this stage has at least ${\tfrac {k(n-m+1)}{2}}$ edges.

Assuming none of the edges crossing $C$ were picked in an earlier step, the probability to select an edge crossing $C$ (unlucky) is at most ${\tfrac {2}{(n-m+1)}}$.

It follows that

$Pr\left[E_{m}\mid \bigcap _{j=1}^{m-1}E_{j}\right]\geq 1-{\frac {2}{n-m+1}}={\frac {n-m-1}{n-m+1}}$

Combining what we know,

${\begin{aligned}Pr\left[\bigcap _{j=1}^{n-2}E_{j}\right]&\geq \prod _{m-1}^{n-2}{\frac {n-m-1}{n-m+1}}\\&={\frac {(n-2)(n-3)\dots (3)(2)(1)}{n(n-1)(n-2)\dots (3)}}\\&={\frac {2}{n(n-1)}}\in \Omega ({\frac {1}{n^{2}}})\end{aligned}}$

Repeat the algorithm slightly more than $n^{2}$ times, say $n^{2}\log {n}$ times, the algorithm will more than likely return the correct result.