# Probabilistic r-way cut set algorithm

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?

• "I define $|C|=k$, and based on that, $d(v)\ge k-r+2$, $\forall v \in V$." If you have tried with a few simple nontrivial examples, you should have found the above is not correct. For example, for the complete graph of 4 vertices, we need to remove all 6 edges to have 4 components. $r=4$, $k=6$, $d(v)=3\lt 4 =k-r+2$. – John L. Mar 29 '19 at 22:18

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$$.