# Counting the number of distinct s-t cuts in a oriented graph

I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs 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 at Stack Overflow and I have been pointed here.

• 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 Dec 14 '11 at 2:39
• @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 Dec 14 '11 at 5:32
• @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 Dec 14 '11 at 10:14