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

CC BY-SA 4.0
2021-04-17T22:28:42.980Z
Perhaps you can extend the analysis of Karger's algorithm to bound the probability of choosing the second-smallest cut?
D.W.
CC BY-SA 4.0
2021-04-17T23:07:28.737Z
Doesn't this previous question answer this, or at least the first part? https://cstheory.stackexchange.com/questions/31145/second-smallest-s-t-cut-in-a-network?rq=1
Jason Gaitonde
CC BY-SA 4.0
2021-04-18T05:55:04.953Z
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
CC BY-SA 4.0
2021-04-19T14:01:12.813Z
@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
CC BY-SA 4.0
2021-04-20T15:55:47.267Z
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](https://en.wikipedia.org/wiki/Karger%27s_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
<ds.algorithms><graph-theory><max-flow-min-cut>
How to find the second smallest cut in a graph?
Akash Agrawal
# How to find the second smallest cut in a graph?

(Asked by: username_0 on 2021-04-17)

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?

**Tags:** ds.algorithms, graph-theory, max-flow-min-cut

> **Comments:**
> **username_1**: Perhaps you can extend the analysis of Karger's algorithm to bound the probability of choosing the second-smallest cut?  
> **username_2**: Doesn't this previous question answer this, or at least the first part? https://cstheory.stackexchange.com/questions/31145/second-smallest-s-t-cut-in-a-network?rq=1  
> **username_3**: 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?  
> **username_4**: @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$?  
> **username_4**: Following up on @username_1's comment (which seems to apply to min cut, not min $s$-$t$ cut?): it seems a natural extension of [Karger's Algorithm](https://en.wikipedia.org/wiki/Karger%27s_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.  

---

## 0 answers

