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: $\frac{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[E_m\mid \bigcap _{\ell =1}^{m-1}{E}_{\ell }]\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[E_m\mid \bigcap _{\ell =1}^{m-1}{E}_{\ell }]\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 $\frac{kn}{2}$ edges.

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

Thus

$Pr[E_1]\ge 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 $\frac{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 $\frac{2}{(n-m+1)}$.

It follows that

$Pr[E_m\mid \bigcap _{j=1}^{m-1}{E}_j]\ge 1-\frac{2}{n-m+1}=\frac{n-m-1}{n-m+1}$

Combining what we know,

$\begin{array}{rl}Pr\left[\bigcap _{j=1}^{n-2}{E}_j\right]& \ge \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 \mathrm{\Omega }(\frac{1}{n^2})\end{array}$

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.