# How can Karger's algorithm (and other randomized algorithms) be used in practice?

Suppose I am given the following problem (the source is here):

Disconnect two nodes in a graph by removing minimum number of edges.

I would apply Karger's min-cut algorithm. But how can I guarantee that I'll finally find the min-cut? Karger's algorithm is a randomized algorithm. If the probability of success is 1/p, I could run it p times to get the answer, right? Not necessarily! What if I am extremely unlucky, so I will never (or too much time will pass) get the answer?

Karger's algorithm is a randomized algorithm. It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.

If we do one round of the algorithm, it has a probability of success of $p$. If you repeat it $100/p$ times and take the best cut found in any of those iterations, then the probability of success is incredibly high: the algorithm fails only if all $100/p$ iterations fail, so the probability of failure is

$$(1-p)^{100/p} \approx e^{-100} < 2^{-128},$$

and the probability of success is larger than $1 - 2^{-128}$. For Karger's algorithm, $p=1/{n \choose 2}$, so we repeat it $100 {n \choose 2}$ times, and we obtain a probability of success that is larger than $1 - 2^{-128}$.

For all engineering purposes this is equivalent to a guarantee of success. For instance, the probability that a cosmic ray hits your computer and causes a bitflip error that causes the algorithm to produce the wrong result is far higher than $2^{-128}$, but we're apparently willing to accept that -- so we should be glad to accept Karger's algorithm too, as long as we repeat it enough times.

See the Wikipedia article for more explanation: https://en.wikipedia.org/wiki/Karger%27s_algorithm

• Please fix the markdown here: 1 - 2^{-128}\$ Jan 22, 2017 at 17:22
• @D.W. But a suggested edit has to be at least six characters. :-( Jan 22, 2017 at 17:40