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