La complexité du comptage de chemins simples dans un graphe orienté

Soit un digraphe (pas nécessairement un DAG) et soit s , t ∈ V ( G ) . Quelle est la complexité de compter le nombre de simples s - t chemins dans G . $G$$s,t \in V(G)$ $s-t$$G$

Je m'attendrais à ce que le problème soit # -complet, mais je n'ai pas pu trouver une référence exacte. ${\mathsf P}$

Notez également qu'un certain nombre de questions similaires ont été répondues correctement ici et ailleurs, mais pas cette question précise - pour souligner que je ne suis pas intéressé par le comptage des marches et / ou des graphiques non orientés (dans le premier cas, la variante est en et dans l'autre # P- dur).${\mathsf P}$${\mathsf P}$

La preuve d'exhaustivité # P du comptage des chemins st simples dans les graphiques non orientés et dirigés peut être trouvée dans:

Leslie G. Valiant: La complexité des problèmes de dénombrement et de fiabilité . SIAM J. Comput. 8 (3): 410-421 (1979)

Extrait du journal:

...
4. Quelques problèmes # P-complet
...
14. ST PATHS (c.-à-d. AUTO-ÉVITER LES PROMENADES) (dirigé ou non)
Entrée: Sortie V : nombre de chemins (dirigés) de s à t qui visitent chaque nœud au plus une fois. ...$G; s,t \in V$
$s$$t$