4
$\begingroup$

I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).

It states that a single round of contractions yields a min-cut with probability $\Omega(n^{-2})$ and concludes that $O(n^2 \log n)$ independent contractions are sufficient to find a min-cut with high probability.

It makes sense to me that $O(n^2)$ independent contractions yields a min-cut with a probability of approximately 1. Anything above this increases the probability, but why has $\log n$ being chosen?

$\endgroup$
6
$\begingroup$

Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2})$, i.e. with probability $\ge \frac{c}{n^2}$ for some $c>0$.

This is, of course, very bad. For large $n$ our success probability converges to zero. However, if we run it independently $k$ times, then our failure probability is now $\left(1-\frac{c}{n^2}\right)^k$ (we choose the minimal cut obtained from the $k$ runs, in order to fail finding the cut in this manner we must fail every time). Finally, we have:

$\Pr\left[\text{failure}\right]\le \left(1-\frac{c}{n^2}\right)^k\le e^{-\frac{kc}{n^2}}$, taking $k=n^2\log n$ we get:

$\Pr\left[\text{failure}\right]\le e^{-c\log n} = \frac{1}{n^c}$, which converges to zero, as apposed to our failure probability after a single run of the algorithm.

$\endgroup$
  • $\begingroup$ So the a probability of failure which is $\le \frac{1}{n^c}$ is a high probability of success and an appropriate expression for $k$ is sought? $\endgroup$ – Richard May 6 '16 at 23:19
  • $\begingroup$ I'm not sure i understand your question. "High" means (in this context) that your success probability goes to 1 as your input's size increases. I added $k$ just to show how the error probability is bounded in terms of the number of independent runs. $\endgroup$ – Ariel May 6 '16 at 23:25
  • $\begingroup$ If anyone wonders why $(1 - c/n^2)^k \leq e^{-kc/n^2}$, it follows from $1 - x \leq e^{-x}$ which is a fundamental inequality in calculus. $\endgroup$ – Björn Lindqvist 8 hours ago
4
$\begingroup$

Approximately, if a chance NOT to find a cut in independent contraction is $1-\frac{a}{n^2}$, then a chance to find it in $n^2\log n$ contractions is $$ 1-\left(1-\frac{a}{n^2}\right)^{n^2\log n}=1-\left(\left(1-\frac{a}{n^2}\right)^{n^2}\right)^{\log n}\approx 1-\exp(-a\log n)=1-\frac{a}{n}. $$

$\endgroup$

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.