5
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Is the complexity of counting minimum s,t-cuts also hard? $\endgroup$
    – someone
    Dec 13, 2011 at 19:49
  • $\begingroup$ Yes, that is also hard. $\endgroup$
    – Yoshio Okamoto
    Dec 13, 2011 at 22:23
  • $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    Dec 14, 2011 at 2:39
  • 2
    $\begingroup$ @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. $\endgroup$
    – Yoshio Okamoto
    Dec 14, 2011 at 5:32
  • 1
    $\begingroup$ @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) $\endgroup$
    – Saeed
    Dec 14, 2011 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.