I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.

But the question of efficient reduction from min cut to $st$-min cut is still interesting to me.

I know the following trivial reductions:

  1. Min cut is $st$-min cut for some $s,t$. So we can, for every pair $s,t$, solve $st$-min cut and return the minimum. This takes $O(n^2)$ calls to $st$-min cut algorithm.
  2. By the same reasoning, we can fix any vertex $s$, and return the minimum, among all $t$, of the $st$-min cut. That takes $O(n)$ calls.

Is there any more efficient (randomized) reduction ? What if we only want the size of the minimum cut, not the cut itself ?

  • $\begingroup$ If you looking for a randomized algorithm take a look at Karger's algorithm, maybe it's a good start point, it doesn't call the s-t cut algorithm as subroutine. $\endgroup$
    – Saeed
    Commented Oct 30, 2014 at 11:36
  • $\begingroup$ @Saeed This question asks about the connection between two problems, not the algorithm for min-cut itself. But thanks anyway. $\endgroup$ Commented Oct 30, 2014 at 16:06
  • $\begingroup$ I know. The reason that I suggested about randomized algorithm is it seems in the randomized case there is no real connection (I saw you are also interested in randomized case). $\endgroup$
    – Saeed
    Commented Oct 30, 2014 at 21:08
  • $\begingroup$ One more note. For your second question (if we just want the cut size not cut itself), it's not easier than finding the cut. We can suppose each min s-t cut is unique, in fact by setting edge weights as : $w(e_i)\rightarrow w(e_i)+2^{-i-1}$ (I supposed given edge weights at start are integers), one of original min s-t cuts is still a s-t min cut with new weights, so if we have an algorithm that finds the size of min cut it's trivial to find corresponding cut (in O($|E|+|V|$)). $\endgroup$
    – Saeed
    Commented Nov 2, 2014 at 22:51
  • $\begingroup$ @Saeed but then you are not working in Word RAM model where each word has O(logn) bits $\endgroup$ Commented Nov 3, 2014 at 9:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.