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