Hubungan antara kekerasan pengakuan kelas grafik dan karakterisasi subgraph terlarang

Saya sedang mempertimbangkan kelas grafik yang dapat ditandai dengan subgraph terlarang.

Jika kelas grafik memiliki himpunan terbatas dari subgraf terlarang, maka ada algoritme pengenalan waktu polinomial yang sepele (satu hanya dapat menggunakan kekuatan kasar). Tetapi sebuah keluarga tak terbatas dari subgraph terlarang tidak menyiratkan kekerasan: ada beberapa kelas dengan daftar tak terbatas dari subgraph terlarang sehingga pengakuan itu juga dapat diuji dalam waktu polinomial. Grafik chordal dan Perfect adalah contoh tetapi, dalam kasus tersebut, ada struktur "bagus" pada keluarga terlarang.

Apakah ada hubungan antara kekerasan pengakuan kelas dan "perilaku buruk" keluarga terlarang? Seharusnya hubungan seperti itu ada? "Perilaku buruk" ini telah diresmikan di suatu tempat?

Meskipun tampaknya intuitif bahwa daftar subgraph terlarang (diinduksi) untuk kelas grafik yang memiliki NP-hard recognition harus memiliki beberapa kompleksitas "intrinsik", saya baru-baru ini menemukan beberapa bukti negatif yang mencolok untuk intuisi ini dalam literatur.$\mathscr{C}$

Mungkin yang paling sederhana untuk digambarkan adalah yang berikut, diambil dari artikel oleh B. Lévêque, D. Lin, F. Maffray dan N. Trotignon .

Misalkan adalah kumpulan grafik yang terdiri dari satu siklus dengan panjang setidaknya empat, ditambah tiga simpul: dua berdekatan dengan simpul u yang sama dari siklus, dan satu berdekatan dengan simpul v dari siklus, di mana u dan v adalah tidak berturut-turut dalam siklus (dan tidak ada tepi lainnya).$F$$u$$v$$u$$v$

Sekarang misalkan adalah kumpulan grafik yang disusun persis dengan cara yang sama, kecuali Anda menambahkan empat simpul: dua berdekatan dengan simpul u siklus yang sama (seperti sebelumnya), tetapi sekarang dua berdekatan dengan simpul v yang sama dari siklus, di mana lagi u dan v tidak berurutan.$F'$$u$$v$$u$$v$

Kemudian kelas grafik yang memiliki sebagai subgraph yang diinduksi terlarang memiliki pengenalan polinomial-waktu, sedangkan pengakuan kelas yang memiliki F sub sebagai subgraf yang diinduksi terlarang adalah NP-hard.$F$$F'$

Oleh karena itu, saya merasa sulit untuk memahami kondisi umum yang harus dipenuhi oleh daftar subgraph yang diinduksi terlarang ketika menghasilkan kelas dengan (NP-) pengakuan keras, mengingat kondisi seperti itu harus memisahkan "sangat mirip" dan F ′ di atas.$F$$F'$

Jawaban oleh @Hugo sangat bagus, dan di sini saya ingin menambahkan beberapa pendapat pribadi.

Ada keluarga terkait yang mirip dengan grafik di keluarga F dan F '. Grafik dalam keluarga B1 dalam artikel biasanya disebut piramida. Dan grafik dalam keluarga B2 biasanya disebut prisma. Lihat jawabannya di sini untuk ilustrasi. Dalam literatur masalah deteksi subgraph yang diinduksi, mereka digunakan untuk mendeteksi lubang genap / ganjil, yang merupakan siklus tanpa kabel dengan panjang genap / ganjil. Dengan teorema grafik kuat sempurna yang dirayakan, grafik G sempurna jika G dan komplemen G tidak mengandung lubang ganjil.

Untuk keluarga piramida dan prisma, sebenarnya ada perbedaan di antara mereka - satu memiliki subtree diinduksi dari tiga daun, dan yang lainnya tidak. Ini disebut masalah "tiga-dalam- pohon- " , yang telah dipelajari oleh Chudnovsky dan Seymour. Sangat mengejutkan bahwa menentukan apakah ada pohon terinduksi yang berisi tiga node yang diberikan dapat ditelusuri, sedangkan masalah "empat-in-a-centered-tree" adalah NP-hard . (Pohon terpusat adalah pohon dengan paling banyak satu simpul dengan derajat lebih besar dari 2.) Perbedaan antara F dan F 'tampaknya disebabkan oleh alasan yang sama.

Tetapi tampaknya karakterisasi lengkap masih sulit, karena kita bahkan tidak tahu kompleksitas mendeteksi grafik di beberapa keluarga yang terlihat cukup sederhana, seperti grafik bebas-lubang (!). Dan untuk keluarga yang kita tahu ada algoritma waktu polinomial, seperti grafik sempurna dan grafik bebas lubang, walaupun ada strategi umum (berdasarkan dekomposisi) untuk merancang algoritma, kita harus menyediakan teorema struktural spesifik untuk mereka. Ini biasanya merupakan proses yang bergantung pada keluarga, dan sebagian besar waktu buktinya sangat panjang. ( Ini contoh untuk grafik even-hole-free, di mana kertasnya lebih dari 90 halaman.)

Masih akan menarik untuk memiliki beberapa klasifikasi untuk masalah deteksi subgraph yang diinduksi, dalam arti seperti masalah three-in-a-tree.