Randomized Min-Cut Algorithm

We assume that mininmal cut has a size of k. Due to this assumption, every vertex in the graph must have a degree of at least $k$.
The number of edge-vertex pairs is at least $kn$. Every edge is incident to two vertices, that is why the number of edges in $G$ is at least $kn/2$.
Probability of choosing an edge in the min-cut($G$) in the $i^{th}$ contraction is:
Pr( e $\in$ min-cut(G)) = $\displaystyle\frac {k} {Remaining {}Edges}$
Pr( e $\in$ min-cut(G)) $\leq$ $\displaystyle\frac {k} {k(n-i)/2}$
Pr( e $\in$ min-cut(G)) $\leq$ $\displaystyle\frac {2} {(n-i)}$
Pr( e $\notin$ min-cut(G)) $\geq$ 1- $\displaystyle\frac {2} {(n-i)}$
Pr( e $\notin$ min-cut(G)) $\geq$ $\displaystyle\frac {n-2-i} {(n-i)}$
In the last iteration :
Pr( e $\notin$ min-cut(G)) $\geq$ 1- $\displaystyle\frac {2} {(t+1)}$
Pr( e $\notin$ min-cut(G)) $\geq$ $\displaystyle\frac {(t-1)} {(t+1)}$

During all iterations of the contraction algorithm, if we do not contract any of the edges that belong to min cut, we will successfully find the min-cut. Probability of this is:
Pr(success) $\geq$ $\displaystyle\frac{(n-2)}{n}$ $\displaystyle\frac{(n-3)}{(n-1)}$ $\displaystyle\frac{(n-4)}{(n-2)}$ $\displaystyle\frac{(n-5)}{(n-3)}$ $\ldots$ $\displaystyle\frac{t}{(t+2)}$ $\displaystyle\frac {(t-1)} {(t+1)}$
Pr(success) $\geq$ $\displaystyle\frac{t(t-1)}{n(n-1)}$
Pr(success) $\geq$ $\displaystyle\frac{t^2}{n^2}$
This result conforms to the lemma put forth by R. Motwani et al. [6].
Lemma: Suppose that the Algorithm Contract is terminated when the number of vertices remaining in the contracted graph is exactly $t$. Then any specific min-cut $K$ survives in the resulting contracted graph with probability at least $\Omega\displaystyle\left(\frac{t^2}{n^2}\right)$.



Subsections
Ali Salehi 2005-04-29