Menghitung Jumlah Jalur Sederhana dalam Grafik Tidak Terarah

18

Bagaimana saya bisa menentukan jumlah jalur sederhana yang unik dalam grafik yang tidak diarahkan? Baik untuk panjang tertentu, atau rentang panjang yang dapat diterima.

Ingat bahwa jalur sederhana adalah jalur tanpa siklus, jadi saya berbicara tentang menghitung jumlah jalur tanpa siklus.

Ryan
sumber
2
Ini sudah ditanyakan pada mathoverflow: mathoverflow.net/questions/18603/…
Listing
5
Sebenarnya, pertanyaan di mathoverflow adalah tentang menemukan semua jalur, dan tidak menghitungnya. Menemukan mereka bisa jauh lebih sulit.
DCTLib
1
Selain referensi yang diberikan dalam jawaban, satu pengamatan sepele adalah bahwa jika seseorang dapat menghitung jumlah jalur dengan panjang maka dapat menjawab pertanyaan tentang keberadaan jalur hamiltonian. Jadi kemungkinan besar itu bukan P.n1
Saeed

Jawaban:

20

Ada beberapa algoritma yang menghitung jalur sederhana panjang dalam waktu f ( k ) n k / 2 + O ( 1 ) , yang jauh lebih baik daripada waktu brute force ( O ( n k ) ). Lihat misalnya Vassilevska dan Williams, 2009 .kf(k)nk/2+O(1)O(nk)

Andreas Björklund
sumber
18

Ini # P-complete (Valiant, 1979) sehingga Anda tidak mungkin melakukan jauh lebih baik daripada brute force, jika Anda menginginkan jawaban yang tepat. Perkiraan didiskusikan oleh Roberts dan Kroese (2007).


B. Roberts dan DP Kroese, " Memperkirakan jumlah jalur - t dalam grafikst ". Jurnal Grafik Algoritma dan Aplikasi , 11 (1): 195-214, 2007.

LG Valiant, " Kompleksitas masalah enumerasi dan keandalan ". Jurnal SIAM tentang Komputasi 8 (3): 410-421, 1979.

David Richerby
sumber
4
Makalah Roberts dan Kroese tampaknya tidak memberikan jaminan perkiraan. Apakah ada PTAS yang dikenal untuk masalah ini?
Sasho Nikolov
3
@SashoNikolov, tampaknya tidak mungkin ada algoritma perkiraan yang masuk akal. Diberikan dapatkan G dari G dengan mengganti setiap node dengan klik ukuran N = n c di mana n = | V | dan c 1 . Untuk setiap jalur sederhana panjang di G ada kira-kira ( N ! ) jalur di G . Jadi, jika G memilikiG=(V,E)GGN=ncn=|V|c1G(N!)GG jalur Hamilton, setidaknya akan ada ( N ! ) n atau lebih sederhana s - t jalur di G , dan sebaliknya paling tidak seperti ( n - 1 ) ! ( N ! ) N - 1 jalur s - t sederhana. Jadi seharusnya sulit untuk memperkirakan dalam faktor sekitar N ! / ( n - 1 ) ! n c -st(N!)nstG(n1)!(N!)n1st. N!/(n1)!nc1!
Neal Young
6

Saya ingin menambahkan algoritma aproksimasi lain, yang parametrize: Untuk tetap > 0 (atau lebih tepatnya, δ = Ω ( 1δ>0), Anda dapat menghitungsebuah(1+δ)-approximation dari jumlah jalur sederhana, baik dalam grafik diarahkan atau diarahkan, panjangkdalam waktuO*(2O(k)).δ=Ω(1poly(k))(1+δ)kO(2O(k))

BPR
sumber