# The complexity of counting simple paths in a directed graph

Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$.

I would expect the problem to be #${\mathsf P}$-complete but have not been able to locate an exact reference.

Also notice that a number of similar questions have been answered correctly here and elsewhere but not this precise question - to emphasise I am not interested in counting walks and/or undirected graphs (in the first case the variant is in ${\mathsf P}$ and in the other #${\mathsf P}$-hard).

• The #P-completeness applies even for undirected graphs, and this was discussed before. Perhaps a more interesting question would be if this is known to be $APX$-hard.
– R B
Sep 8, 2014 at 7:01

The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in:

Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421 (1979)

From the paper:

...
4. Some #P-complete problems
...
14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected)
Input: $G; s,t \in V$
Output: Number of (directed) paths from $s$ to $t$ that visit every node at most once.
...