14
$\begingroup$

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

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

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 7, 2015 at 8:36
  • $\begingroup$ 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. $\endgroup$ May 7, 2015 at 14:22
  • 1
    $\begingroup$ 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. $\endgroup$ May 7, 2015 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.