Second Smallest $s$-$t$-Cut in a Network

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$.

• 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). Apr 22 '15 at 15:03
• 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? Apr 22 '15 at 15:40
• 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. Apr 22 '15 at 16:43
• @Kaveh, do you still get an integral solution to the LP?
– usul
Apr 22 '15 at 20:20
• 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.) Apr 22 '15 at 20:50

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.
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.
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.
• 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. May 7 '15 at 8:36
• 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. May 7 '15 at 18:31