Saat mencari Sistem informasi pada Kelas Grafik dan Inklusi mereka , saya menemukan beberapa kelas grafik yang masalah Siklus Hamiltonian adalah NP-lengkap sedangkan kompleksitas masalah Jalur Hamiltonian TIDAK diketahui. Beberapa kelas tersebut adalah grafik derajat 3 maksimum bipartit, grafik grid 3 derajat maksimum, dan grafik planar kubik 2 yang terhubung. Juga fenomena ini berlaku untuk grafik lingkaran dan grafik kotak segitiga.
Apakah ada pembaruan untuk kompleksitas masalah jalur Hamiltonian di kelas-kelas itu? Apakah ada penjelasan untuk fenomena ini?
EDIT : Saya menemukan dalam database kelas grafik kasus aneh dari grafik kotak padat di mana masalah siklus Hamiltonian berada di sementara masalah jalur Hamiltonian adalah kompleksitas yang tidak diketahui .
sumber
Jawaban:
Masalah jalur Hamiltonian pada grafik grid dengan derajat 3 maksimum adalah NP-lengkap. Buktinya ada di CH Papadimitriou dan UV Vazirani, Tentang dua masalah geometris yang berkaitan dengan masalah salesman keliling, Jurnal Algoritma, Volume 5, Edisi 2, Juni 1984, Halaman 231–246 (Teorema 2)
sumber
Telah ada pembaruan untuk Sistem informasi tentang Kelas Grafik dan Inklusi mereka. Sekarang, masalah siklus Hamiltonian dan masalah jalur Hamiltonian dinyatakan sebagai NP-lengkap pada grafik planar 2 kubik yang terhubung.
Namun, kompleksitas komputasi masalah HC dan HP terdaftar tidak diketahui untuk satu masalah dan NP-lengkap untuk yang lain pada grafik lingkaran , grafik kisi segitiga , dan grafik kisi padat .
sumber