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:
- 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.
- 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 ?