8
$\begingroup$

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 ?

Improve this question
$\endgroup$
6
  • $\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
    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$
    – Thatchaphol
    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
    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
    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$
    – Thatchaphol
    Nov 3, 2014 at 9:31

0

Reset to default

Your Answer

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