For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, where $p$ is the size of the smallest cut?

  • 1
    $\begingroup$ Perhaps you can extend the analysis of Karger's algorithm to bound the probability of choosing the second-smallest cut? $\endgroup$
    – D.W.
    Commented Apr 17, 2021 at 22:28
  • 2
    $\begingroup$ Doesn't this previous question answer this, or at least the first part? cstheory.stackexchange.com/questions/31145/… $\endgroup$ Commented Apr 17, 2021 at 23:07
  • 1
    $\begingroup$ In general there can be many cuts which have the same s-t mincut value. In that case the definition of the second smallest cut is not so clean. For instance if you wanted a cut of size p+1 where p is the size of the smallest cut, why not remove p edges in some mincut and another arbitrary edge? $\endgroup$ Commented Apr 18, 2021 at 5:55
  • $\begingroup$ @ChandraChekuri Perhaps by "cut" OP means a minimal cut, that is, obtainable as $E\cap (S\times (V\setminus S))$ for some 2-partition $(S, V\setminus S)$ of the vertex set $V$? Does anybody know whether finding an $s$-$t$ cut of size min plus one is in $P$? $\endgroup$
    – Neal Young
    Commented Apr 19, 2021 at 14:01
  • $\begingroup$ Following up on @D.W.'s comment (which seems to apply to min cut, not min $s$-$t$ cut?): it seems a natural extension of Karger's Algorithm produces a random cut $C$ such that, for any given cut $C'$ of size $p+d$, the probability that $C=C'$ is at least $1/n^{O(d)}$. I assume this is already known. But I don't see how to apply it to $s$-$t$ cuts. $\endgroup$
    – Neal Young
    Commented Apr 20, 2021 at 15:55


Your Answer

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