Epidemic Spreading Algorithm

All the steps done in the previous section also apply to here:
Probability of choosing an edge in the min-cut($G$) in the $i^{th}$ iteration 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 there are $t$ clusters that contain vertices that get infected and there remains one vertex that is not infected:
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 epidemic spreading algorithm, if we do not spread the epidemic over the edges that belong to min cut, this means that we 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)}$
The probability of finding min-cut in one run of the algorithm is same as Randomized Min-cut :
Pr(success) $\geq$ $\displaystyle\frac{t^2}{n^2}$

Ali Salehi 2005-04-29