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

<p>Leslie G. Valiant: <a href="http://epubs.siam.org/doi/abs/10.1137/0208032">The Complexity of Enumeration and Reliability Problems</a>. SIAM J. Comput. 8(3): 410-421 (1979)</p>

<p>From the paper:</p>

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

CC BY-SA 3.0
2014-09-07T22:17:01.597Z
2014-09-07T22:31:13.870Z
2014-09-07T22:31:13.870Z
Marzio De Biasi
<p>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 <em>simple</em> $s-t$ paths in $G$.  </p>

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

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

CC BY-SA 3.0
2014-09-08T07:01:41.677Z
The #P-completeness applies even for [undirected graphs](http://cstheory.stackexchange.com/questions/20246/counting-the-number-of-simple-paths-in-undirected-graph), and this was discussed before. Perhaps a more interesting question would be if this is known to be $APX$-hard.
R B
<ds.algorithms><reference-request><counting-complexity>
The complexity of counting simple paths in a directed graph
SamiD
# The complexity of counting simple paths in a directed graph

(Asked by: username_0 on 2014-09-07)

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

**Tags:** ds.algorithms, reference-request, counting-complexity

> **Comments:**
> **username_1**: The #P-completeness applies even for [undirected graphs](http://cstheory.stackexchange.com/questions/20246/counting-the-number-of-simple-paths-in-undirected-graph), and this was discussed before. Perhaps a more interesting question would be if this is known to be $APX$-hard.  

---

## 1 answers

### Answer by username_2 on 2014-09-07. Score: 19 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/0208032). 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.  
...


---

