Probabilistic r-way cut set algorithm

Question

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph.

In this generalized version, instead of finding a set of edges that would break the graph into two components, it would break it in r components. The approach used for the 2-way cut-set is to contract edges until only two vertices remain, and treat the edges remaining as the cut-set $C$.

The question then is

Explain how the randomized min-cut algorithm can be used to find minimum r-way cut-sets, and bound the probability that it succeeds in one iteration.

My idea is to instead of stopping when there are r vertices remaining, instead of 2. But I am unable to bound its success probability. A possible approach would be to find the probability of contracting an edge $\in C$. To do so, I define $|C|=k$, and based on that, $d(v)\ge k-r+2$, $\forall v \in V$. Thus, $|E|\ge \frac{(k-r+2) \cdot (n)}{2}$. But i can't remove this $k$ from the equation latter...

Any ideas here?

Answer 1

Your idea of stopping when there are $r$ vertices remaining is the correct approach. Now let us see how to bound the success probability of contracting one arbitrary edge not in a fixed $r$ way cut-sets.

Denote the graph by $(V,E)$ with $n=|V|$ and $m=|E|$.

Lemma: Let $C$ be an $r$-way minimum cut. The probability that a randomly selected edge is not in $C$ is at least $$\frac{(n-r+1)(n-r)}{n(n-1)}.$$

Proof: Let us count the number of elements in the following sets.

$$\begin{align} V^{r-1}&=\{Q: Q \subseteq V\text{ such that } |Q| = r-1\}\\ S&=\{(e, Q): Q\in V^{r-1}, e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\ S_{e}&=\{\phantom{(e,\,} Q\phantom{)}: Q\in V^{r-1}\phantom{, e\in E } \text{ such that none of the endpoints of } e\text{ is in } Q \}\\ S_{Q}&=\{\phantom{(}e\phantom{,Q)}: \phantom{Q\in V^{r-1},\,} e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\ \end{align}$$

$|V^{r-1}|=\binom{n}{r-1}.$
$|S_e|=\binom{n-2}{r-1}$ for all $e\in V$.

Fix an arbitrary $Q\in V^{r-1}$. If we removes all edges not in $S_Q$, i.e., all edges whose endpoints are in $Q$ and all edges between a vertex in $Q$ and a vertex not in $Q$, there will be $r-1$ connected components of single vertex and one or more connected components in the remaining vertices. That means the set of all edges not in $S_Q$ is an $r$-way cut. Since the minimize size of an $r$-way cut is $k$, the number of edges not in $S_Q$ is no less than $k$, i.e, $|S_Q|\le m-k.$

Since $S$ is the disjoint union of all $S_e$, $e\in E$ as well as the disjoint union of all $S_Q$, $Q\in V^{r-1}$,
$$\binom{n-2}{r-1}m \le (m-k)\binom n{r-1},$$ which means, $$1-\frac k{m} \ge\frac{\binom{n-2}{r-1}}{\binom n{r-1}}=\frac{(n-r+1)(n-r)}{n(n-1)},$$ where the left side is exactly the probability that a randomly selected edge from $E$ is not in $C$, a set of $k$ edges. QED.

---

Now that we have the lemma above, we can proceed just as in the book to compute the probability that any given minimum $r$-way cut $C$ survives all $n − r$ random successive edge contractions.

---

Exercise. (One minute or less) Check that the lemma and its proof above specialize to the arguments given in the book in the case of $r=2$.