Kompleksitas penghitungan jalur sederhana dalam grafik terarah

Biarkan menjadi digraf (tidak harus DAG) dan biarkan . Apa kompleksitas menghitung jumlah sederhana jalan di . $G$$s,t \in V(G)$ $s-t$$G$

Saya berharap masalahnya menjadi # -lengkap tetapi belum dapat menemukan referensi yang tepat. ${\mathsf P}$

Juga perhatikan bahwa sejumlah pertanyaan serupa telah dijawab dengan benar di sini dan di tempat lain tetapi bukan pertanyaan yang tepat ini - untuk menekankan saya tidak tertarik menghitung jalan-jalan dan / atau grafik yang tidak terarah (dalam kasus pertama variannya ada di dan di yang lain # -hard).${\mathsf P}$${\mathsf P}$

Bukti kelengkapan P # menghitung jalur st sederhana di grafik tidak langsung dan terarah dapat ditemukan di:

Leslie G. Valiant: Kompleksitas Masalah Pencacahan dan Keandalan . SIAM J. Comput. 8 (3): 410-421 (1979)

Dari kertas:

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