# Efficient Reduction from Min Cut to st-Min Cut

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 ?

• 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. Commented Oct 30, 2014 at 11:36
• @Saeed This question asks about the connection between two problems, not the algorithm for min-cut itself. But thanks anyway. Commented Oct 30, 2014 at 16:06
• 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). Commented Oct 30, 2014 at 21:08
• 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|$)). Commented Nov 2, 2014 at 22:51
• @Saeed but then you are not working in Word RAM model where each word has O(logn) bits Commented Nov 3, 2014 at 9:31