A&W assignment 7

7.1 Finding Minimum Cuts

a)

suppose $C$ is a cut of size $\mu$, then each vertex has degree at least $\mu$ and the total amount of edges $|E|\ge \frac{n\mu }{2}$ Thus the probability that a chosen edge is in cut $C$ is at most $\frac{\mu }{|E|}\le \frac{2}{n}$ we denote $p(n)$ for the probability that a chosen edge is in cut $C$ in a graph with $n$ vertices. Then $p(n)\ge (1-\frac{2}{n})p(n-1)$ Iterating this recurrence gives: $p(n)\ge \frac{2}{n(n-1)}=\frac{1}{\left(\begin{array}{c}n\\ 2\end{array}\right)}$

b)

Let $m$ be the number of minimum cuts, and $C_i$ be each minimum cut. (Event $C_i$ is returned is disjoint from each other)

$$1\ge \sum _{i=1}^m\mathrm{Pr}[{\text{Cut(G) returns C}}_i]\ge m\cdot \frac{1}{\left(\begin{array}{c}n\\ 2\end{array}\right)}$$

Therefore, $m\le \left(\begin{array}{c}n\\ 2\end{array}\right)$

c)

Suppose we have $n\ge 3$ vertices. We construct a cycle $C_n$ Any two chosen edges is a minimum cut, and there are $\left(\begin{array}{c}n\\ 2\end{array}\right)$ possible choices.

d)

From part (a), each fixed minimum cut is returned in one run with probability at least $p=\frac{1}{\left(\begin{array}{c}n\\ 2\end{array}\right)}$ Since we want all minimum cuts to appear at least once, we can use the coupon collector model. From lecture we know that the expected running time to complete a coupon collector problem is $O(m\log m)$ (where each coupon has $\frac{1}{m}$ chance to be chosen)

Here each minimum cut (“coupon” ) has chance at most $\frac{1}{\left(\begin{array}{c}n\\ 2\end{array}\right)}$ to be chosen, so we have an upper bound $O(\left(\begin{array}{c}n\\ 2\end{array}\right)\log \left(\begin{array}{c}n\\ 2\end{array}\right))$ Since $\left(\begin{array}{c}n\\ 2\end{array}\right)=\frac{n^2-n}{2}=\Theta (n^2)$ $O(\left(\begin{array}{c}n\\ 2\end{array}\right)\log \left(\begin{array}{c}n\\ 2\end{array}\right))=O(n^2\log n^2)=O(n^2\log n)$