Dalam grafik, himpunan bebas adalah himpunan bagian verteks yang tidak mengandung tepi sebagai subgraf yang diinduksi. Masalah menemukan set independen terbesar dalam grafik adalah pertanyaan algoritmik yang mendasar, dan yang sulit pada saat itu. Mari kita pertimbangkan pertanyaan yang lebih umum untuk menemukan (ukuran) set bebas-H terbesar dalam sebuah grafik, di mana bebas-H berarti bahwa ia tidak menginduksi subgraf yang berisi salinan grafik tetap H sebagai subgraf yang diinduksi.
Untuk grafik tetap H, diberikan grafik input G, apakah NP-sulit untuk menentukan ukuran set bebas-H terbesar di G?
Apakah ada cara yang masuk akal untuk membangun "tabel" grafik H (atau kelas H), sehingga untuk mengisi entri dengan jawaban ya atau "tidak" yang benar untuk pertanyaan di atas? (Mari kita berpura-pura bahwa "tidak" = P, dan bahkan entri "tidak" berarti ada algoritma polytime untuk menghasilkan set bebas-H terbesar.)
Gagal itu, apakah ada kelas H non-sepele yang jawabannya adalah ya? ... tidak?
Saya sedang mencari-cari, mencari dua pertanyaan tentang bilangan kromatis umum / bebas-H --- di sini dan di sini --- ketika terpikir oleh saya bahwa masalah "ganda" (yang tampaknya lebih sederhana) dari analog bebas-kemerdekaan nomor H mungkin juga terbuka. Saya mengetahui makalah klasik tentang masalah terkait untuk grafik acak, lih. misalnya Erdos, Suen dan Winkler (1995) atau Bollobas dan Thomason (2000), yang masih dalam jalur penelitian yang masih sangat aktif. Jadi mungkin sudah ada beberapa pekerjaan yang belum saya lihat menjawab pertanyaan yang lebih mendasar ini dan pencarian internet yang kasar tidak terungkap (karenanya tag referensi-permintaan).
Jawaban:
Misalkan memiliki setidaknya dua simpul. Keluarga semua HH H grafik -free adalah turun temurun pada subgraph yang diinduksi dan properti menjadi -gratis adalah non-sepele, di mana properti adalah non-sepele jika benar untuk banyak grafik yang tak terhingga dan itu palsu untuk banyak grafik yang tak terhingga. Dengan demikian, hasil dari Lewis dan Yannakakis [1] berlaku, menunjukkan bahwa untuk semua H dengan setidaknya dua simpul, masalahnya adalah NP-lengkap.H H
[1] John M. Lewis, Mihalis Yannakakis: Masalah Penghapusan Node untuk Properti Turunan adalah NP-Lengkap. J. Comput. Syst. Sci. 20 (2): 219-230 (1980)
sumber