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.

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ Is the complexity of counting minimum s,t-cuts also hard? $\endgroup$ – someone Dec 13 '11 at 19:49
  • $\begingroup$ Yes, that is also hard. $\endgroup$ – Yoshio Okamoto Dec 13 '11 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 '11 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 '11 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 '11 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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