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?

  • $\begingroup$ "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$. $\endgroup$ – 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}$$

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

| cite | improve this answer | |

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.