17

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).

SamiD
  • 2,309
  • 17
  • 28
  • 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 08 '14 at 07:01

1 Answers1

19

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.
...

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127