Probability of choosing an edge in the min-cut() in the iteration is:

Pr( e min-cut(G)) =

Pr( e min-cut(G))

Pr( e min-cut(G))

Pr( e min-cut(G)) 1-

Pr( e min-cut(G))

In the last iteration there are clusters that contain vertices that get infected and there remains one vertex that is not infected:

Pr( e min-cut(G)) 1-

Pr( e min-cut(G))

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)

Pr(success)

The probability of finding min-cut in one run of the algorithm is same as Randomized Min-cut :

Pr(success)

Ali Salehi 2005-04-29