30
$\begingroup$

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).

However it seems that, surprisingly, the problem gets much harder if instead of testing for the existence we want want to count the number of paths.

If we allow paths to reuse vertices then there is a dynamic programming solution to find the number of paths from s to t with n edges. However, if we only allow simple paths, that don't reuse vertices, the only solution I can think of is brute force enumeration of the paths, something that has exponential time complexity.

So I ask,

  • Is counting the number of simple paths between two vertices hard?
  • If so, is it kind of NP-complete? (I say kind of because it is technically not a decision problem...)
  • Are there other problems in P that have a hard counting versions like that too?**
Improve this question
$\endgroup$
3
  • $\begingroup$ BTW, I actually know the answer to this question now but I am curious about what kind of answer I would get if I asked it back when I first came up with it. $\endgroup$
    – hugomg
    Commented Mar 15, 2012 at 18:25
  • 1
    $\begingroup$ stackoverflow.com/questions/713508/… $\endgroup$
    – Suresh
    Commented Mar 15, 2012 at 19:43
  • 1
    $\begingroup$ @Suresh: I know how to code the brute force search. My question if whether there is a more efficient algorithm. In any case, this SO question would be more similar, and even includes an answer of mine, if you are interested in spoilers. $\endgroup$
    – hugomg
    Commented Mar 15, 2012 at 19:58

1 Answer 1

Reset to default
18
$\begingroup$

The most common complexity class associated to counting problems is #P. Deciding if there a simple path from a given node to another is clearly in NP. Counting them is then in #P.

About the NP-completeness: even if that's not a decision problem, it would hardly fit in NP: there may be $n!$ paths, and non-determinism does not help you about that (you'd still need to check them all)

The answer to your two first two question is: yes, it is hard, it is #P-complete (ref).

The Wikipedia article gives pertinent facts: 1) probabilistic algorithms are useful to approximate #P-complete functions, and that's the kind of algorithm used for the approximation in the previous article. 2) There are other easy problems with hard (#P-complete) counting versions:

  • finding (linear) vs. counting all assignments satisfying a DNF formula or an instance of 2-SAT
  • finding (linear) vs. counting topological sortings
  • finding (O(VE)) vs. counting perfect matching in bipartite graphs

You already know that if you remove the constraint "simple path" the problem falls into P (well you have to bound the length of the paths by a polynomial of the size of the graph or give the bound in unary)

Improve this answer
$\endgroup$

Your Answer

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

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