A complexidade de contar caminhos simples em um gráfico direcionado

Seja um dígrafo (não necessariamente um DAG) e deixe . O que é a complexidade da contagem do número de simples caminhos em . $G$$s,t \in V(G)$ $s-t$$G$

Eu esperaria que o problema fosse # completo, mas não consegui localizar uma referência exata. ${\mathsf P}$

Observe também que várias perguntas semelhantes foram respondidas corretamente aqui e em outros lugares, mas não essa pergunta precisa - para enfatizar que não estou interessado em contar caminhadas e / ou gráficos não direcionados (no primeiro caso, a variante está em e no outro # -hard).${\mathsf P}$${\mathsf P}$

A prova # P-completeness de contar caminhos st simples em gráficos não direcionados e direcionados pode ser encontrada em:

Leslie G. Valiant: A complexidade dos problemas de enumeração e confiabilidade . SIAM J. Comput. 8 (3): 410-421 (1979)

Do artigo:

...
4. Alguns problemas no P-completo
...
14. CAMINHOS DE ST (ie AUTO EVITANDO CAMINHADAS) (direcionados ou não direcionados)
Entrada: saída: Número de (dirigida) caminhos de s a t que visita a cada nó no máximo uma vez. ...$G; s,t \in V$
$s$$t$