# How to find the second smallest cut in a graph?

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?

• Perhaps you can extend the analysis of Karger's algorithm to bound the probability of choosing the second-smallest cut? – D.W. Apr 17 at 22:28
• Doesn't this previous question answer this, or at least the first part? cstheory.stackexchange.com/questions/31145/… – J.G Apr 17 at 23:07
• 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? – Chandra Chekuri Apr 18 at 5:55
• @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$? – Neal Young Apr 19 at 14:01
• 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. – Neal Young Apr 20 at 15:55