13
$\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$
  • $\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$ – Yuval Filmus Apr 22 '15 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$ – Oliver Witt Apr 22 '15 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 '15 at 16:43
  • $\begingroup$ 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. $\endgroup$ – Oliver Witt Apr 22 '15 at 17:06
  • 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 '15 at 20:50
7
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – András Salamon May 7 '15 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$ – Oliver Witt May 7 '15 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$ – David Eppstein May 7 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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