• Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
  • $(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$
  • $P\big((A_{i},B_{i})\big) \geq \frac{1}{\begin{pmatrix} n \\ 2 \end{pmatrix}} = p$, which I interpret as the lower bound on the probability of having at least one minimal cut.
  • In the problem set that follows two answers A and B are highlighted as being correct. I understand why A is correct; but am puzzled why B is also marked as correct.
  • A: For every graph $G$ with $n$ nodes and every min cut $(A,B)$ (I am assuming same thing as $(A_{i},B_{i})$) $P\big((A,B)\big) \geq p$.
  • B There exists a graph $G$ with $n$ nodes and a min cut $(A,B)$ (again assuming same thing as $(A_{i},B_{i})$) of $G$ such that $P\big((A,B)\big) \leq p$.

I don't understand what you mean by "$(A_i,B_i) = ((A_1,B_1),\ldots,(A_t,B_t))$", an obviously false statement. Perhaps you meant $(A_i,B_i) \in \{(A_1,B_1),\ldots,(A_t,B_t)\}$?

I don't quite understand your interpretation of the statement $P((A_i,B_i)) \geq p := 1/\binom{n}{2}$. Here is the correct interpretation:

For any minimum cut $C$, the probability that Karger's algorithm outputs $C$ is at least $p := 1/\binom{n}{2}$.

This is exactly what A states.

For B, you need to give an example of a graph which satisfies $P(C) \leq 1/\binom{n}{2}$ for all cuts $C$. One such example is a cycle, an example you were probably shown in class.


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.