<p>Counting the number of s,t-cuts is #P-complete.  This is a result by Provan and Ball.</p>

<ul>
<li>J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)</li>
</ul>

<p>Therefore, unless some complexity-theoretic collapse happens, you cannot get essentially faster algorithm than listing all of them.</p>

CC BY-SA 3.0
2011-12-13T19:49:27.587Z
Is the complexity of counting _minimum_ s,t-cuts also hard?
someone
CC BY-SA 3.0
2011-12-13T22:23:09.267Z
Yes, that is also hard.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-14T02:39:08.863Z
That's interesting, as there are only $n^{2\alpha}$ (not s-t) cuts that are within $\alpha$ of the minimum. Is the exact number of minimum cuts easy to compute?
Sasho Nikolov
CC BY-SA 3.0
2011-12-14T05:32:09.817Z
@Sasho Nikolov: The number of min-cuts in an $n$-vertex undirected graph is at most $\binom{n}{2}$, and they can be listed in polynomial time.  So, the number of min-cuts can be computed in polynomial time.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-14T06:22:59.103Z
is the same true for $\alpha$-approximate min cuts?
Sasho Nikolov
CC BY-SA 3.0
2011-12-14T10:05:41.463Z
There is no need to complexity collapse to solve problem in better than listing all of them for example may be there is some sub exponential algorithm for counting this, it doesn't cause to P=NP.
Saeed
CC BY-SA 3.0
2011-12-14T10:07:09.917Z
@Saeed: Right, and that's why I put "essentially" in the sentence.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-14T10:08:27.573Z
@SashoNikolov: For the approximation, I don't know.  But, I guess it's also possible as long as $\alpha$ is constant.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-14T10:14:44.290Z
@YoshioOkamoto, I thought about your "essentially" (at first) I guess you mean some polynomial time difference, but IMHO $2^n \gt\gt 2^{sqrt(n)}$ or something similar, this can be a good results and solvable in many cases. (if exists)
Saeed
CC BY-SA 3.0
2011-12-14T10:27:52.090Z
@Saeed: I agree.
Yoshio Okamoto
CC BY-SA 3.0
2014-05-01T18:26:27.623Z
@YoshiOkamoto, How many s-t minimal cuts will be there in a graph of size $n$. Is it exponential or polynomial ?
Kumar
CC BY-SA 3.0
2014-05-01T23:10:00.800Z
@Kumar: It is an exercise to show the number of minimum s-t cuts can be exponential.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-13T09:28:17.050Z
2011-12-13T09:28:17.050Z
Yoshio Okamoto
<p>I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article <a href="http://www.cs.uu.nl/research/techreps/repo/CS-1987/1987-07.pdf" rel="nofollow noreferrer">Enumeration in Graphs</a> p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a faster or simpler algorithm I can use if I am interested only in the number of such cuts and I do not actually need to enumerate it?</p>

<p>The definition of a s-t cut I am using is following. We have a directed graph where two vertices are labelled <strong>S</strong> and <strong>T</strong>. Cut is a <em>minimal</em> set of edges of a graph such that by removing those edges there will no longer exist a path from vertex <strong>S</strong> to vertex <strong>T</strong>.</p>

<p>I tried to <a href="https://stackoverflow.com/questions/8343263">ask this</a> at Stack Overflow and I have been pointed here.</p>

CC BY-SA 3.0
2012-12-17T05:59:08.390Z
If your graph is planar, then you can do this in $O(n^2)$ time. See http://dx.doi.org/10.1016/j.tcs.2011.05.017.
Zach Langley
<ds.algorithms><graph-algorithms><counting-complexity>
Counting the number of distinct s-t cuts in a oriented graph
user7610
# Counting the number of distinct s-t cuts in a oriented graph

(Asked by: username_0 on 2011-12-13)

I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article [Enumeration in Graphs](http://www.cs.uu.nl/research/techreps/repo/CS-1987/1987-07.pdf) p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a faster or simpler algorithm I can use if I am interested only in the number of such cuts and I do not actually need to enumerate it?

The definition of a s-t cut I am using is following. We have a directed graph where two vertices are labelled **S** and **T**. Cut is a *minimal* set of edges of a graph such that by removing those edges there will no longer exist a path from vertex **S** to vertex **T**.

I tried to [ask this](https://stackoverflow.com/questions/8343263) at Stack Overflow and I have been pointed here.

**Tags:** ds.algorithms, graph-algorithms, counting-complexity

> **Comments:**
> **username_1**: If your graph is planar, then you can do this in $O(n^2)$ time. See http://dx.doi.org/10.1016/j.tcs.2011.05.017.  

---

## 1 answers

### Answer by username_2 on 2011-12-13. Score: 18 | Accepted answer

Counting the number of s,t-cuts is #P-complete. This is a result by Provan and Ball.

* J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

Therefore, unless some complexity-theoretic collapse happens, you cannot get essentially faster algorithm than listing all of them.

> **Comments:**
> **username_3**: Is the complexity of counting _minimum_ s,t-cuts also hard?  
> **username_2**: Yes, that is also hard.  
> **username_4**: That's interesting, as there are only $n^{2\alpha}$ (not s-t) cuts that are within $\alpha$ of the minimum. Is the exact number of minimum cuts easy to compute?  
> **username_2**: @username_4: The number of min-cuts in an $n$-vertex undirected graph is at most $\binom{n}{2}$, and they can be listed in polynomial time.  So, the number of min-cuts can be computed in polynomial time.  
> **username_4**: is the same true for $\alpha$-approximate min cuts?  
> **username_5**: There is no need to complexity collapse to solve problem in better than listing all of them for example may be there is some sub exponential algorithm for counting this, it doesn't cause to P=NP.  
> **username_2**: @username_5: Right, and that's why I put "essentially" in the sentence.  
> **username_2**: @SashoNikolov: For the approximation, I don't know.  But, I guess it's also possible as long as $\alpha$ is constant.  
> **username_5**: @YoshioOkamoto, I thought about your "essentially" (at first) I guess you mean some polynomial time difference, but IMHO $2^n \gt\gt 2^{sqrt(n)}$ or something similar, this can be a good results and solvable in many cases. (if exists)  
> **username_2**: @username_5: I agree.  
> **username_6**: @YoshiOkamoto, How many s-t minimal cuts will be there in a graph of size $n$. Is it exponential or polynomial ?  
> **username_2**: @username_6: It is an exercise to show the number of minimum s-t cuts can be exponential.  

---

