Сложность подсчета простых путей в ориентированном графе

Пусть орграф (не обязательно DAG) и . Что является сложность подсчета количества простой путей в . $G$$s,t \in V(G)$ $s-t$$G$

Я ожидал бы, что проблема будет # -полной, но не смог найти точную ссылку. ${\mathsf P}$

Также обратите внимание, что на ряд похожих вопросов были даны правильные ответы здесь и в других местах, но не на этот точный вопрос - чтобы подчеркнуть, что я не заинтересован в подсчете прогулок и / или неориентированных графов (в первом случае вариант находится в и в другой # -hard).${\mathsf P}$${\mathsf P}$

Доказательство # P-полноты подсчета простых st-путей в неориентированных и ориентированных графах можно найти в:

Лесли Г. Валиант: Сложность перечисления и проблемы надежности . SIAM J. Comput. 8 (3): 410-421 (1979)

Из бумаги:

$G; s,t \in V$
$s$$t$