Perkiraan untuk menghitung jumlah jalur - sederhana dalam grafik umum

Saya telah diberitahu bahwa ada beberapa waktu algoritma polinomial baik untuk mendekati jumlah jalur sederhana dalam grafik diarahkan dari yang diberikan mulai vertex untuk diberikan berakhir vertex . Adakah yang tahu referensi yang bagus tentang hal ini? $s$ $t$

Latar belakang: menghitung jumlah persis jalur dalam grafik umum adalah # P-complete tetapi mungkin ada perkiraan waktu polinomial untuk masalah tersebut. Saya terutama tertarik pada perkiraan acak.

Terima kasih sebelumnya.

ds.algorithms reference-request graph-algorithms approximation-algorithms counting-complexity bbejot
sumber

Saya memiliki masalah yang sama dan diselesaikan dengan menggunakan Random Walk.

@ bbbot: Lihat Seberapa sulit menghitung jumlah jalur sederhana antara dua node dalam grafik yang diarahkan? Satu-satunya jawaban, oleh jmad, memberikan tautan ke sebuah makalah yang memang memberikan perkiraan acak

Carlos Linares López

Jawaban:

Masalah ini harus NP-keras dengan mengurangi dari panjang jalur maksimum.

Pengurangan hanya mengganti setiap tepi dengan, katakanlah, tepi paralel. (Jika Anda merasa tidak nyaman dengan multi-grafik, gantilah setiap tepi dengan lintasan panjang 2.) Efeknya adalah bahwa angka lintasan panjang menjadi . Dengan demikian, jika cukup besar, istilah yang sesuai dengan jalur terpanjang dalam grafik asli akan mendominasi yang lainnya (bahkan jika ). Dari sana Anda dapat dengan mudah memulihkan panjang jalur jalan terpanjang. $k$ $C_{\ell}$ $\ell$ $k^\ell C_{\ell}$ $k$ $C_{\ell_{max}}=1$

Heng Guo
sumber