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