How hard is counting the number of simple paths between two nodes in a directed graph?

Question

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?**

Answer 1

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)