Apakah masalah jalan terpanjang lebih mudah daripada masalah jalan terpanjang?

Masalah jalur terpanjang adalah NP-hard. Bukti (khas?) Bergantung pada pengurangan masalah jalur Hamiltonian (yang NP-lengkap). Perhatikan bahwa di sini jalan dianggap sederhana (node-). Artinya, tidak ada titik dapat terjadi lebih dari satu kali di jalan. Jelas itu juga edge-simple (tidak ada edge yang akan muncul lebih dari satu kali di path).

Jadi bagaimana jika kita menjatuhkan persyaratan untuk menemukan jalur (node-) sederhana dan tetap mencari jalur tepi-sederhana (trail). Pada pandangan pertama, karena menemukan jejak Euler jauh lebih mudah daripada menemukan jalur Hamilton, orang mungkin memiliki harapan bahwa menemukan jalur terpanjang akan lebih mudah daripada menemukan jalur terpanjang. Namun, saya tidak dapat menemukan referensi yang membuktikan ini, apalagi yang menyediakan algoritma.

Perhatikan bahwa saya mengetahui argumen yang dibuat di sini: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph Namun, argumen itu tampaknya cacat dalam bentuk saat ini, karena pada dasarnya menunjukkan Anda bisa menyelesaikan kasus tepi-sederhana dengan memecahkan kasus simpul-sederhana pada grafik yang berbeda (jadi pengurangannya adalah cara yang salah di sekitar). Tidak jelas bahwa pengurangan dapat dengan mudah diubah untuk bekerja dengan cara lain juga. (Namun, itu menunjukkan bahwa setidaknya masalah jalan terpanjang tidak lebih sulit daripada masalah jalur terpanjang.)

Jadi, adakah hasil yang diketahui untuk menemukan jalan terpanjang (jalur tepi-sederhana)? Kompleksitas (kelas)? Algoritma (efisien)?

graph-theory graph-algorithms hamiltonian-paths Jasper
sumber

Ini bukan masalah yang sama persis, tetapi lihatlah masalah Extension Euilerian Minimum yang sangat mirip.

Mungkin saya tidak mengerti dengan baik pertanyaannya, tetapi jalur Hamiltonian adalah NP-lengkap bahkan pada grafik kubik, karena setiap traversal dari sebuah node memerlukan dua sisi tidak ada cara untuk menggunakan kembali node dua kali bahkan jika kita mengendurkan kondisi dari node-simple jalur ke jalur tepi-sederhana; jadi masalah jalur Hamilton tetap NP-lengkap.

Marzio De Biasi

@ Bangye: ok tetapi dalam grafik kubik jika sebuah node dilalui satu kali, maka 2 edge harus digunakan ... dan node tersebut tidak dapat dilintasi lagi (karena hanya ada satu tepi yang tidak dilewati). Jadi dalam grafik kubik, node tidak dapat "diulang" (kecuali untuk tepi terakhir dari jejak yang dapat terjadi pada node yang sudah dilalui)

Marzio De Biasi

Berikut ini rujukannya: AA Bertossi, Masalah jalur hamiltonian tepi adalah NP-complete, Information Processing Letters, 13 (1981) 157-159.

Lamine

@Lamine: Terima kasih atas klarifikasi. Saya tidak berpikir Anda harus menghapus komentar Anda karena itu akan sangat alami untuk datang dengan ide yang sama terlebih dahulu dan melihatnya tidak berfungsi sangat membantu.

Yota Otachi

Jawaban:

Dari komentar di atas: masalah siklus Hamilton tetap NP-lengkap bahkan dalam grafik grid dengan derajat maksimal 3 [1], tetapi dalam grafik ini setiap traversal dari sebuah node memerlukan dua tepi dan paling banyak satu tepi tetap tidak digunakan, sehingga sebuah node tidak dapat dilalui dua kali oleh jalur Euler.

Jadi rupanya ada pengurangan langsung dari masalah siklus Hamiltonian ke masalah Anda: diberi grafik kotak dengan derajat maksimal 3 , cukup minta jejak panjang . $G = (V,E)$ $|V|$

Tetapi ketiga tepi simpul di ujung jalan dapat digunakan; untuk menghindari situasi ini Anda dapat memilih node kiri atas dari grafik grid (yang memiliki gelar dua) dan tambahkan dua node: dan tepi baru dan minta jejak panjang $u$ $V' = V \cup \{u',u''\}$ $E = E \cup \{(u,u'), (u,u'')\}$ : tepi yang ditambahkan secara tidak resmi memaksa menjadi titik akhir dari jejak. $|V'| = |V|+2$ $u',u''$

[1] Christos H Papadimitriou, Umesh V Vazirani, Tentang dua masalah geometrik yang berkaitan dengan masalah salesman keliling, Jurnal Algoritma, Volume 5, Edisi 2, Juni 1984, Halaman 231-246, ISSN 0196-6774

Marzio De Biasi
sumber

Saya mengalami sedikit kesulitan untuk menikahi ini, serta beberapa komentar lainnya, dengan kemudahan yang diketahui untuk menemukan jejak Euler. Atau apakah titik krusial yang (berpegang pada teladan Anda) memutuskan apakah ada jejak panjang "Euler"

lebih mudah daripada memutuskan apakah ada jejak panjang

? Ini tentu akan sedikit mengejutkan bagi saya, tapi pasti menarik.

| E |

$|E|$

| V |

$|V|$

Jasper

Dalam grafik kubik Anda yakin bahwa tidak ada jejak panjang

, memang semua tepi memiliki derajat ganjil 3 (

kompleksitas). Jadi masalah menemukan jejak panjang

(dengan trik tambahan

) lebih sulit (NPC); informal: untuk setiap node ada tiga pasang tepi yang dapat digunakan untuk membangun jejak, dan Anda tidak tahu "efek" dari pilihan sampai Anda membangun sisa jejak. Dalam grafik normal, jalur Euler mudah dihitung karena pada setiap langkah Anda dapat yakin bahwa Anda dapat "kembali" ke titik awal (lihat algoritma Fleury).

| E |

$|E|$

O (1)

$O(1)$

| V |

$|V|$

u^{'}, u^{″}

$u',u''$

Marzio De Biasi