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.

Any hint would be helpful.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Oct 28 '15 at 11:32
  • $\begingroup$ Could you be more specific? Are the bad-case instances because of deleting edges between s and t? $\endgroup$
    – dash
    Oct 28 '15 at 16:40
  • $\begingroup$ That's your exercise and so you should come up with the example. $\endgroup$ 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.

Though, I don't know whether this one works.

  • $\begingroup$ What do you mean by "I don't know whether this one works"? You have given a proof. $\endgroup$ Oct 29 '15 at 22:10
  • $\begingroup$ I didn't know that it is a valid one. $\endgroup$
    – user41301
    Oct 29 '15 at 22:13
  • $\begingroup$ this was probably a copy-paste from the following website, therefore who answered this did not understand the answer itself, it just provided what was here coursehero.com/file/13001117/solution7-15 $\endgroup$ Nov 4 '17 at 22:23
  • $\begingroup$ Here is a video for Karger's algorithm for whoever whats more guidance youtube.com/watch?v=zX4enUrsvKg $\endgroup$ Nov 4 '17 at 22:25

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.