Siklus Hamiltonian pada grafik tanpa siklus kecil

Saat menjawab pertanyaan ini di cstheory , saya (secara informal) membuktikan teorema berikut ini dengan segera:

Teorema : Untuk setiap tetap masalah siklus Hamilton tetap NP-lengkap bahkan jika terbatas pada planar bipartit grafik tidak berarah tingkat maksimum 3 yang tidak mengandung siklus panjang . $l \geq 3$ $\leq l$

Tampaknya sangat tidak mungkin bahwa itu belum muncul di suatu tempat.
Tetapi memungkinkan untuk menyelesaikan banyak masalah siklus Hamiltonian / jalur di graphclasses.org yang ditandai sebagai "Tidak Diketahui untuk ISGCI" (lihat misalnya yang ini ); memang wajar langsung adalah bahwa Hamiltonian siklus dan jalur masalah masih NP-lengkap jika terbatas grafik, di mana masing-masing berisi setidaknya satu siklus. $(H_1,...,H_k)\text{-free}$ $H_i$

Bisakah Anda memberi saya referensi kertas / buku di mana ia muncul?

(maka saya akan menghubungi orang-orang di graphclasses.org)

reference-request np-hardness Marzio De Biasi
sumber

Setidaknya diskusi ini membantu untuk hasil baru di graphclasses.org jadi tolong informasikan graphclasses tentang hasil yang tidak diketahui untuk mereka - Tautan Kontak memberikan formulir, alamat email adalah opsional.

joro

@ joro: Saya sudah menghubungi mereka, kemarin (saya juga memberi mereka email saya). Saya akan menunggu beberapa hari dan melihat apakah mereka memperbarui status masalah tersebut.

Marzio De Biasi

Saya mendengar mereka tidak terlalu sering memperbarui database dan membalas dengan "terima kasih" setelah memperbarui DB dan mereka cukup responsif.

joro

@ joro: Saya pikir mereka memperbarui basis data (mereka sangat kolaboratif dan sopan)

Marzio De Biasi

Jawaban:

Hasilnya dinyatakan dalam makalah Dua Kelas Baru Grafik Hamilton oleh Arkin, Mitchell dan Polinshchuk.

Kristoffer Arnsfelt Hansen
sumber

Naskah yang tidak diterbitkan oleh Hougardy, Emden-Weinert dan Kreuter pada tahun 1997 ini memberikan bukti sederhana untuk hasil berikut yang jauh lebih kuat daripada hasil yang ditunjukkan dalam jawaban Kristoffer Arnsfelt Hansen:

$0\le r <1/2$ $n$ $\ge n^r$

Naskah juga berisi hasil yang serupa untuk masalah lain seperti set Mendominasi, Max cut, VFS, dll.

vb le
sumber

Ok terima kasih! Saya lupa menyebutkan bahwa bukti saya berfungsi untuk grafik bipartit planar tidak berarah max-degree 3 ... jadi Hourgardy et al. kertas lebih kuat ... tapi tidak jauh lebih kuat :-) :-). Saya mungkin akan menerima jawaban Kristoffer karena dia mempostingnya terlebih dahulu.

Marzio De Biasi

@ MarszioDeBiasi, saya pikir kekuatannya adalah tentang ukuran ketebalan. bukti Anda adalah tentang nomor tetap, jawaban yang diterima untuk beberapa f (n) yang kurang dari sqrt dan jawaban ini lebih umum daripada semuanya. (Pembatasan IMHO pada grafik tidak terlalu penting di sini)

Saeed

Makalah ini berisi masalah NP-hard lainnya, itu akan menjadi jawaban untuk pertanyaan terkait tentang grafik siklik.

Joro