Kelas grafik dengan siklus Hamilton mudah tetapi NP-hard TSP

13

The Hamiltonian Cycle Masalah (HC) terdiri dalam menemukan suatu siklus yang melewati semua simpul dalam grafik diarahkan diberikan. Masalah Travelling Salesman (TSP) terdiri dalam menemukan suatu siklus yang melewati semua simpul dalam grafik tepi-tertimbang yang diberikan dan meminimalkan total jarak yang diukur oleh jumlah dari bobot dari tepi dalam siklus. HC adalah kasus khusus TSP, dan keduanya dikenal sebagai NP-lengkap [Garey & Johnson]. (Lihat tautan di atas untuk detail lebih lanjut dan varian masalah ini.)

Apakah ada kelas grafik yang dipelajari di mana Hamiltonian Cycle Problem dipecahkan dalam waktu polinomial melalui algoritma non-sepele , tetapi Traveling Salesman Problem adalah NP-hard?

Non-sepele adalah untuk mengecualikan kelas-kelas seperti kelas grafik lengkap, di mana siklus Hamiltonian dijamin ada dan dapat ditemukan dengan mudah, atau umumnya kelas grafik di mana HC selalu dijamin ada.

cc.complexity-theory np-hardness hamiltonian-paths tsp graph-classes Standa Zivny
sumber

Jawaban:

20

Gambar tidak selalu Hamiltonian, memiliki tes waktu polinomial untuk Hamiltonisitas, dan NP-sulit untuk memecahkan masalah salesman keliling.

Secara lebih umum masalah siklus Hamilton dapat diselesaikan dalam waktu polinomial (tetapi tidak dapat diperbaiki parameter parameternya) pada grafik lebar klik terikat ; lihat, misalnya, Fomin dkk., "Lebar klik: pada harga generalitas", SODA'09. Tetapi sekali lagi karena keluarga grafik ini termasuk grafik lengkap, TSP sulit pada grafik ini.

David Eppstein
sumber
Saya ingin tahu tentang pernyataan terakhir Anda. Apakah itu karena tur TSP akan secara efektif mengidentifikasi klik-klik dengan membuat semua simpul klik berdekatan dalam tur?
Suresh Venkat
1
Tidak, maksud saya sederhana bahwa TSP sulit bahkan dalam grafik lengkap, dan grafik lengkap adalah di antara grafik dengan lebar klik terikat. Grafik lengkap sendiri tidak memberikan jawaban yang baik untuk pertanyaan karena Hamiltonicity sepele bagi mereka, tetapi superclasses dari klik-klik (seperti cographs) mungkin memiliki tes Hamiltonisitas nontrivial tetapi polinomial.
David Eppstein
11

Bagaimana dengan grafik lengkap ? Karena TSP selalu dapat direduksi menjadi instance pada grafik lengkap (dengan menambahkan jarak yang tepat antara non-edge), masih sulit untuk menyelesaikan TSP pada grafik lengkap. Tetapi setiap grafik lengkap adalah Hamiltonian.

Hsien-Chih Chang 張顯 之
sumber
Ya tentu saja terima kasih! Lupa untuk mengecualikan grafik lengkap, dan dalam hal ini semua kelas grafik di mana HC dapat dipecahkan secara sepele.
Standa Zivny
3
@Standa Zivny: Saya tidak yakin apakah Anda akan mengedit pertanyaan atau tidak, tetapi jika Anda ingin mengecualikan "semua kelas grafik di mana HC dapat dipecahkan secara sepele," Anda harus mengedit pertanyaan. Namun, saya ragu bahwa adalah mungkin untuk merumuskan perbedaan antara kasus di mana HC dapat diselesaikan "dengan mudah" dan kasus di mana HC dapat diselesaikan "sepele."
Tsuyoshi Ito
@ Tsuyoshi Ito: Poin yang bagus, saya sudah mengedit pertanyaan.
Standa Zivny
@StandaZivny - Tidak semua grafik yang sepele untuk HC sulit untuk TSP, misalnya grafik jalur.
RB
3

Ada banyak kelas grafik tanpa batas yang diketahui memiliki sirkuit hamiltonian. Dua kelas yang sangat menarik adalah n-cubes dan grafik Halin. Salah satu cara berpikir grafik Halin adalah dengan menanamkan pohon dengan setidaknya 3 simpul dan yang tidak memiliki simpul valensi dua di pesawat, dan kemudian melewati sirkuit sederhana melalui simpul 1-valen pohon.

http://en.wikipedia.org/wiki/Halin_graph

Grafik ini diketahui memiliki HC dan sebenarnya panklik (sirkuit semua panjang) atau kurang tepat satu panjang sirkuit yang panjangnya harus sama.

Joseph Malkevitch
sumber