2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please fix the markdown here: 1 - 2^{-128}$ $\endgroup$ – Maksim Dmitriev Jan 22 '17 at 17:22
  • $\begingroup$ @D.W. But a suggested edit has to be at least six characters. :-( $\endgroup$ – David Richerby Jan 22 '17 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.