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?
5
-
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.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$– Jason GaitondeApr 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$– Chandra ChekuriApr 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 YoungApr 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 YoungApr 20, 2021 at 15:55
Add a comment
|