Referensi untuk kekerasan NP 3 warna?

Saya punya pertanyaan historis.

Saya mencoba menentukan referensi untuk fakta bahwa 3-colourability dari grafik (atau colourability untuk ) adalah NP-hard. $k$ $k\geq 3$

Jawaban yang menggoda adalah "kertas asli Karp", tetapi itu salah. Berikut ini pemindaian: Reducibilitas di antara Masalah Kombinatorial, Karp (1972) . Ini membuktikan bahwa nomor Chromatic (Input: grafik. Output: ) sulit. Itu masalah yang lebih sulit, dan pengurangannya berbeda dari konstruksi gadget standar (dengan 3 warna, True, False, dan Ground) yang menyiratkan kekerasan 3-colourability. $\chi(G)$

Garey dan Johnson, Komputer dan intraktabilitas , memiliki -warna sebagai [GT4] dan merujuk ke Karp (1972). $k$

np-hardness ho.history-overview Thore Husfeldt
sumber

Pada halaman 84, Garey dan Johnson mengklaim bahwa 3-colorability adalah NP-lengkap dengan mengutip makalah Stockmeyer yang disediakan dalam jawaban Yury. Dalam Teorema 4.2, mereka juga memberikan bukti yang lebih sederhana dari hasil Stockmeyer.

Tyson Williams

Jawaban:

László Lovász , Penutup dan pewarnaan hypergraph , Prosiding Konferensi Tenggara Keempat tentang Combinatorics, Teori Grafik, dan Komputasi, Utilitas Math., Winnipeg, Man., 1973, hlm. 3--12, membuktikan bahwa nomor Chromatic berkurang menjadi 3- kesegaran.

Saya pikir, itu adalah bukti pertama untuk NP-kelengkapan 3-colourability.

Ini adalah kertas Lovász; lihat juga sangat baik Vasek Chvátal ini penjelasan untuk pengurangan Lovasz ini.

vb le
sumber

Ini adalah kertas lain dari tahun 1973 yang membuktikan bahwa 3-colorability adalah NP-hard.

Larry J. Stockmeyer. "Planar 3-colorability adalah polinomial selesai." ACM SIGACT News, vol. 5, tidak. 3, 1973.

(Tampaknya Lovász dan Stockmeyer memperoleh hasil mereka secara mandiri.)

Perbarui: lihat komentar di bawah.

Yury
sumber

Jika saya tidak salah, Stockmeyer tidak membuktikan NP-hardness 3-Coloring dalam makalah itu. Di sana, ia mengurangi 3-Coloring ke Planar 3-Coloring dan merujuk kekerasan 3-Coloring ke Karp (1972). Ini salah seperti yang ditunjukkan oleh Thore Husfeldt.

user13136

Saya melihat. Terima kasih user13136! Sayangnya, saya tidak memiliki akses ke makalah ini sekarang. Saya hanya melihat abstrak dari makalah ini dan referensi untuk itu.

Yuri

Saya sekarang telah melihat kertas Stockmeyer melalui perpustakaan digital ACM, dan itu termasuk bukti lengkap dari kekerasan 3-warna. (Pengurangan dari 3-Satisfiability.) Jadi, seolah-olah pernyataan awal Yury benar, dan Stockmeyer dan Lovász memperoleh hasilnya secara independen (dan menggunakan pengurangan yang berbeda.)

Thore Husfeldt

Aduh! Saya tidak menyadari bahwa hanya satu tanda centang yang dapat ditetapkan. Jawaban Stockmeyer benar, jadi saya mengklik tanda centang secara mekanis. Apa yang harus saya lakukan, terbelah karena saya berada di antara dua versi kebenaran yang saling eksklusif?

Thore Husfeldt

Oh, saya hanya ingin tahu karena saya menemukan kertas Lovasz cukup cantik. Saya tidak ingin mendepresiasikan jawaban Yury dan tidak berpikir vb le sangat sedih tentang hal itu;)

user13136