Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
