<p>The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:</p>

<p>H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. <em>Oper. Res. Lett.</em> 1(5):186–189, 1982, <a href="http://dx.doi.org/10.1016/0167-6377(82)90037-2">doi:10.1016/0167-6377(82)90037-2</a>.</p>

<p>H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ best cuts in a network. <em>Oper. Res. Lett.</em> 2(6):303–305, 1984, <a href="http://dx.doi.org/10.1016/0167-6377(84)90083-X">doi:10.1016/0167-6377(84)90083-X</a>.</p>

<p>H. W. Hamacher and M. Queyranne. $K$ best solutions to combinatorial optimization problems. <em>Ann. Oper. Res.</em> 4(1–4):123–143, 1985, <a href="http://dx.doi.org/10.1007/BF02022039">doi:10.1007/BF02022039</a>.</p>

CC BY-SA 3.0
2015-05-07T08:36:33.407Z
Don't these allow equal weights among the top $k$?  The question seems to be asking about the $k$-th smallest _weight_, which as Kaveh suggests smells more like a #P-complete problem.
András Salamon
CC BY-SA 3.0
2015-05-07T14:22:44.400Z
I understand it that way, too: equal weights are allowed. This seems not to answer the question. Nevertheless, I was unaware of these papers, thanks for that.
Oliver Witt
CC BY-SA 3.0
2015-05-07T18:31:51.640Z
The question is badly worded, because it asks for one thing (the $k$th smallest cut) and then later adds a restriction that turns the question into something else (the $k$th smallest distinct cut weight). I agree that the distinct weight version of the problem is likely to be $P-complete.
David Eppstein
CC BY-SA 3.0
2015-05-07T04:57:10.817Z
2015-05-07T04:57:10.817Z
David Eppstein
<p>Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem:</p>

<blockquote>
  <p>Input: A network $N$ and a number $k$, all in binary.<br>
  Output: A $k$th smallest $s$-$t$ cut.</p>
</blockquote>

<p>A $k$th smallest $s$-$t$ cut $(S,T)$ is any $s$-$t$ cut, such that there are exactly $k-1$ $s$-$t$ cuts whose capacities </p>

<ul>
<li>are pairwise different and </li>
<li>truly smaller than the capacity of $(S,T)$.</li>
</ul>

<p>I would like to know how it can be computed and whether this can be done efficiently as for the case $k=1$.</p>

CC BY-SA 3.0
2015-04-22T15:03:44.430Z
You can find the second smallest cut by adding $\epsilon$ weight to all edges in smallest cut and then computing the new smallest cut. This probably works as long as $k$ is encoded in unary (and certainly for $k$ constant).
Yuval Filmus
CC BY-SA 3.0
2015-04-22T15:40:30.430Z
I don't see how that helps. Imagine a path network consisting of the three nodes $s$, $v$, $t$ only with the two edges $(s,v)$ and $(v,t)$. Further, let the capacities be $c(s,v)=1$ and $c(v,t)=2$. Clearly, the min-cut cuts $(s,v)$ and the second smallest cut cuts $(v,t)$. Increasing the capacities as you described would again yield $(s,v)$ as min-cut with capacity $1+\epsilon$. How am I to infer the second smallest cut from that?
Oliver Witt
CC BY-SA 3.0
2015-04-22T16:43:42.630Z
Adding a lower bound on the cap of cut is a linear inequality, just add one epsilon larger than the cap of min and run LP. You can repeat it k times to get what you want. This probably can be recast as a modification on the network but I haven't worked it out.
Kaveh
CC BY-SA 3.0
2015-04-22T17:06:02.370Z
I see how it works if $k$ is in unary encoding. What, if it is binary? In this case, the network modification cannot be done in $k$ iterations.
Oliver Witt
CC BY-SA 3.0
2015-04-22T20:20:28.527Z
@Kaveh, do you still get an integral solution to the LP?
usul
CC BY-SA 3.0
2015-04-22T20:44:46.597Z
@usul, if we are interested in the cap of the cut being integer we can replace epsilon with 1 I think.
Kaveh
CC BY-SA 3.0
2015-04-22T20:50:23.317Z
I doubt there is an easy solution if k is binary. We can check if there is a cut of cap c as I described. It seems to me that is essentially counting the number of possible c, might be provide to relate to counting the number of matchings and probably #P-complete. (This is just my intuition, not an argument.)
Kaveh
<cc.complexity-theory><optimization><max-flow-min-cut><flow-problems>
Second Smallest $s$-$t$-Cut in a Network
Oliver Witt
# Second Smallest $s$-$t$-Cut in a Network

(Asked by: username_0 on 2015-04-15)

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem:

> Input: A network $N$ and a number $k$, all in binary.  
> Output: A $k$th smallest $s$-$t$ cut.

A $k$th smallest $s$-$t$ cut $(S,T)$ is any $s$-$t$ cut, such that there are exactly $k-1$ $s$-$t$ cuts whose capacities

* are pairwise different and
* truly smaller than the capacity of $(S,T)$.

I would like to know how it can be computed and whether this can be done efficiently as for the case $k=1$.

**Tags:** cc.complexity-theory, optimization, max-flow-min-cut, flow-problems

> **Comments:**
> **username_1**: You can find the second smallest cut by adding $\epsilon$ weight to all edges in smallest cut and then computing the new smallest cut. This probably works as long as $k$ is encoded in unary (and certainly for $k$ constant).  
> **username_0**: I don't see how that helps. Imagine a path network consisting of the three nodes $s$, $v$, $t$ only with the two edges $(s,v)$ and $(v,t)$. Further, let the capacities be $c(s,v)=1$ and $c(v,t)=2$. Clearly, the min-cut cuts $(s,v)$ and the second smallest cut cuts $(v,t)$. Increasing the capacities as you described would again yield $(s,v)$ as min-cut with capacity $1+\epsilon$. How am I to infer the second smallest cut from that?  
> **username_2**: Adding a lower bound on the cap of cut is a linear inequality, just add one epsilon larger than the cap of min and run LP. You can repeat it k times to get what you want. This probably can be recast as a modification on the network but I haven't worked it out.  
> **username_0**: I see how it works if $k$ is in unary encoding. What, if it is binary? In this case, the network modification cannot be done in $k$ iterations.  
> **username_3**: @username_2, do you still get an integral solution to the LP?  
> **username_2**: @username_3, if we are interested in the cap of the cut being integer we can replace epsilon with 1 I think.  
> **username_2**: I doubt there is an easy solution if k is binary. We can check if there is a cut of cap c as I described. It seems to me that is essentially counting the number of possible c, might be provide to relate to counting the number of matchings and probably #P-complete. (This is just my intuition, not an argument.)  

---

## 1 answers

### Answer by username_4 on 2015-05-07. Score: 8

The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:

H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. *Oper. Res. Lett.* 1(5):186–189, 1982, [doi:10.1016/0167-6377(82)90037-2](http://dx.doi.org/10.1016/0167-6377(82)90037-2).

H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ best cuts in a network. *Oper. Res. Lett.* 2(6):303–305, 1984, [doi:10.1016/0167-6377(84)90083-X](http://dx.doi.org/10.1016/0167-6377(84)90083-X).

H. W. Hamacher and M. Queyranne. $K$ best solutions to combinatorial optimization problems. *Ann. Oper. Res.* 4(1–4):123–143, 1985, [doi:10.1007/BF02022039](http://dx.doi.org/10.1007/BF02022039).

> **Comments:**
> **username_5**: Don't these allow equal weights among the top $k$?  The question seems to be asking about the $k$-th smallest _weight_, which as username_2 suggests smells more like a #P-complete problem.  
> **username_0**: I understand it that way, too: equal weights are allowed. This seems not to answer the question. Nevertheless, I was unaware of these papers, thanks for that.  
> **username_4**: The question is badly worded, because it asks for one thing (the $k$th smallest cut) and then later adds a restriction that turns the question into something else (the $k$th smallest distinct cut weight). I agree that the distinct weight version of the problem is likely to be $P-complete.  

---

