This exercise taken from the textbook "Randomized Algorithm" by Motwani and Raghavan. P.9, they give the following exercise to modify the min-cut algorithm:
Exercise 1.2 Suppose that at each step of our min-cut algorithm, instead of choosing a random edge for contraction we choose two vertices at random and coalesce them into a single vertex. Show that there are inputs on which the probability that this modified algorithm finds a min-cut is exponentially small.
See the an example of min-cut algorithm and analysing it in page 7-8 here
Suppose we have connected, undirected multigraph with n vertices. A cut in G is a set of edges whose removal results in G being broken into two or more components. A min-cut is a cut of minimum cardinality.
The algorithm works as following: pick an edge at random and merge two vertices at its end-points (see example here) and keep their edges so you could have multigraph. Only edges between vertices that are merged is removed, this process is called "contraction". The algorithm is terminated when we have two vertices.
The analyzing goes as following: number of edges is at least kn/2 (where k is min-cut size of graph, you can check this using equality of minimum degree and average degree of graph; because minimum degree of graph must be k or greater). We will estimate the probability that we don't contract the min-cut edges. Let $E_i$ denote the event of not picking an edge of C (C is the edges of min-cut) at the ith step, for i between 1 and n-2 (n-2 because the algorithm stop when we have only two edges). The probability that the edge randomly chosen in the first step is in C is at most k/(nk/2)=2/n. So, $Pr[E_1] \geq 1-2/n$. the next one is: $Pr[E_1|E_2] \geq 1- 2/(n-1)$. So, at final the probability that no edge of C is ever chosen in the process is: (1-2/n).(1-2/(n-1)).(1-2/(n-2)). ... 7/9.6/8/.5/7.4/6.3/5.2/4.1/3 = 2/(n(n-1)) (because everything is cancel each other except these values).
Now, back to the exercise: in the modified algorithm we can choose any vertices while in original algorithm we must choose one edge at each step. So, first thing comes to my mind is that I have two cases: one case when we choose u and v that they have an edge between them. The second case when we choose u and v that they don't have an edge between them. Now, Pr[first case to choose edge of min-cut] $\leq k/(2k/n)=2/n$; and Pr[second case to choose edge of min-cut] = 0; because there is no edge between them. Now, I get the same calculation as first original problem. I realized that I should find an instance where these two algorithm gives different and the different must be exponentially small using modified algorithm. Can you try to give hints about this problem or advice! Another thing is my calculation is wrong or it really gives the same probabilities as in the original problem except with different instance of the problem. So, there is two ways to attack this exercise: one from finding estimating the probabilities of modified algorithm and one is to find an instance of graph where results is exponentially different from the first one (in other words, it should give us something like $1/2 . 1/2 . 1/2 .... = 1/2^n$ so I'm assuming that the product of probabilities should be constant to get exponential)
Thank you!
Consider a graph $G$ with $n$ vertices $\{v_1, v_2, v_3, \cdots, v_n\}$ such that the first $\lceil n / 2\rceil$ vertices constitute a clique (that is, there is an edge between any two of $\{v_1, v_2, \cdots, v_{\lceil n / 2 \rceil}\}$) and the remaining $\lfloor n / 2\rfloor$ vertices constitute a clique. Moreover, there is an edge between $v_1$ and $v_n$. It is easy to observe that the edge $(v_1, v_n)$ is the unique min-cut of $G$.
For this input, the modified algorithm returns the min-cut if and only if the algorithm never merges vertices from the first clique with vertices from the second clique. Let $E_i$ be the event that vertices from the first clique are not merged with vertices from the second clique in the $i$-th step. We have $$ \Pr(E_i \mid E_{i-1}, \cdots, E_1) = \frac{\binom{s_i}{2} + \binom{r_i}{2}}{\binom{r_i + s_i}{2}} = 1 - \frac{2s_ir_i}{(s_i + r_i)^2 - (s_i + r_i)} \leq 1 - \frac{2s_ir_i}{n^2} $$ where $r_i$ (resp. $s_i$) is the # of vertices remained in the first (resp. second) clique and $$ s_i + r_i = n - i + 1 $$ For $1 \leq i \leq \frac{n}{5}$, we have $$ s_i, r_i \geq \frac{n}{5} $$ and therefore, $$ \Pr(E_i \mid E_{i-1}, \cdots, E_1) \leq 1 - \frac{2 \cdot (n / 5) \cdot (n / 5)}{n^2} = \frac{23}{25} $$ Consequently, $$ \Pr(E_1, E_2, \cdots, E_{n-1}) \leq \Pr(E_1, E_2, \cdots, E_{\lceil n / 5\rceil}) \leq \left(\frac{23}{25}\right)^{\lceil n / 5 \rceil} $$