# Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum

I'm stuck with one of my homework exercises:

Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t:

As in the original algorithm, edges are iteratively contracted. In any iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To ensure that s and t do not get contracted, at each iteration any edges connecting s and t are deleted, and a random edge to contract is selected from the remaining edges.

Give an example showing that the probability that this method finds a minimum s-t cut can be exponentially small.

I know how Karger's algorithm works, but I'm not sure why the probability is exponentially small and how can I show that by giving an example.

• Try to come up with a family of bad-case instances. A good way towards that can be to try and prove that the probability to find an optimal solution is better, and observe where the proof fails. – Raphael Oct 28 '15 at 11:32
• Could you be more specific? Are the bad-case instances because of deleting edges between s and t? – dash Oct 28 '15 at 16:40
• That's your exercise and so you should come up with the example. – Yuval Filmus Oct 28 '15 at 22:01

Consider a graph $G$ with nodes $s$ and $t$, and $n-2$ other nodes $v_1, ..., v_{n-2}$. There are two parallel edges from $s$ to $v_i$, and one edge from $v_i$ to $t$. The minimum $s-t$ cut is to separate $t$ by itself.
If we run the version of the contraction algorithm described in the problem, it will independently contract each of the length-2 paths from $s$ to $t$ in some order. In order for it to find the minimum $s-t$ cut, it must contract $v_i$ into $s$, not into $t$. There is a $\frac{2}{3}$ chance of this happening for each $i$, so the probability that the minimum $s-t$ cut is found is $(\frac{2}{3})^{n-2}$, an exponentially small quantity.