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

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

<p>I know the following trivial reductions:</p>

<ol>
<li>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.</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2014-10-30T11:36:58.673Z
If you looking for a randomized algorithm take a look at [Karger's algorithm](http://en.wikipedia.org/wiki/Karger's_algorithm), maybe it's a good start point, it doesn't call the s-t cut algorithm as subroutine.
Saeed
CC BY-SA 3.0
2014-10-30T16:06:46.983Z
@Saeed This question asks about the connection between two problems, not the algorithm for min-cut itself. But thanks anyway.
Thatchaphol
CC BY-SA 3.0
2014-10-30T21:08:39.590Z
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
CC BY-SA 3.0
2014-11-02T22:51:28.333Z
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
CC BY-SA 3.0
2014-11-03T09:31:18.903Z
@Saeed but then you are not working in Word RAM model where each word has O(logn) bits
Thatchaphol
CC BY-SA 3.0
2014-11-03T11:08:43.120Z
In RAM model each word is not of size O(log n). We can set it arbitrary, while we do not violate poly size. See [this](http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time). We can first multiply each number to $2^{|E|+1}$ then add each weight with $2^i$ to avoid real RAM model and use the integer RAM model. The input size still is polynomial and is bigger than original one by factor of $n$ if $|E|=O(n)$. Anyhow my suggestion is very clear, change each weight by $\epsilon_i$ then every s-t pair admits a unique s-t cut ...
Saeed
<ds.algorithms><graph-algorithms><reductions><max-flow-min-cut>
Efficient Reduction from Min Cut to st-Min Cut
Thatchaphol
# Efficient Reduction from Min Cut to st-Min Cut

(Asked by: username_0 on 2014-10-16)

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 ?

**Tags:** ds.algorithms, graph-algorithms, reductions, max-flow-min-cut

> **Comments:**
> **username_1**: If you looking for a randomized algorithm take a look at [Karger's algorithm](http://en.wikipedia.org/wiki/Karger's_algorithm), maybe it's a good start point, it doesn't call the s-t cut algorithm as subroutine.  
> **username_0**: @username_1 This question asks about the connection between two problems, not the algorithm for min-cut itself. But thanks anyway.  
> **username_1**: 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).  
> **username_1**: 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|$)).  
> **username_0**: @username_1 but then you are not working in Word RAM model where each word has O(logn) bits  
> **username_1**: In RAM model each word is not of size O(log n). We can set it arbitrary, while we do not violate poly size. See [this](http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time). We can first multiply each number to $2^{|E|+1}$ then add each weight with $2^i$ to avoid real RAM model and use the integer RAM model. The input size still is polynomial and is bigger than original one by factor of $n$ if $|E|=O(n)$. Anyhow my suggestion is very clear, change each weight by $\epsilon_i$ then every s-t pair admits a unique s-t cut ...  

---

## 0 answers

