Kelas maksimal yang set independen terbesarnya dapat ditemukan dalam waktu polinomial?

The ISGCI daftar lebih dari 1100 kelas graf. Untuk banyak dari ini kita tahu apakah SET INDEPENDEN dapat diputuskan dalam waktu polinomial; ini kadang-kadang disebut kelas IS-easy . Saya ingin mengkompilasi daftar kelas IS-easy maksimal . Kelas-kelas ini bersama-sama membentuk batas traktabilitas (dikenal) untuk masalah ini.

Karena seseorang hanya dapat menambahkan jumlah grafik hingga ke kelas IS-easy tanpa batas tanpa mempengaruhi traktabilitas, ada beberapa batasan. Mari kita batasi kelas-kelas untuk mereka yang turun-temurun (ditutup dengan mengambil subgraf yang diinduksi, atau yang setara, didefinisikan oleh satu set subgraf yang diinduksi yang dikecualikan). Selain itu, mari kita pertimbangkan hanya keluarga-keluarga yang bebas X untuk satu set X dengan deskripsi kecil. Ada mungkin yang juga menjadi rantai naik tak terbatas kelas penurut (seperti $(P,\text{star}_{1,2,k})$-gratis dan kelas-kelas yang dijelaskan oleh David Eppstein di bawah), tetapi mari kita batasi perhatian pada kelas yang sebenarnya terbukti IS-mudah.

Inilah yang saya tahu:

• grafik yang sempurna
• -gratis$(P,\text{star}_{1,2,5})$
• -gratis$(K_{3,3}-e, P_5)$
• co-Meyniel
• hampir bipartit
• bebas kursi
• ( , kriket) -gratis$P_5$
• -gratis$(P_5,K_{n,n})$(untuk tetap apa pun)$n$
• -gratis$(P_5, X_{82}, X_{83})$

Apakah kelas maksimal lainnya diketahui?

Sunting: Lihat juga pertanyaan terkait yang diajukan oleh Yaroslav Bulatov berkaitan dengan kelas-kelas yang ditentukan oleh anak di bawah umur yang dikecualikan, apa yang mudah untuk grafik yang tidak termasuk dalam kategori kecil? dan lihat properti Global dari kelas herediter? untuk pertanyaan yang lebih umum saya bertanya sebelumnya tentang kelas keturunan.

Seperti yang Jukka Suomela tunjukkan dalam komentar, kasus kecil yang dikecualikan juga menarik (dan akan membuat pertanyaan menarik), tetapi ini bukan fokus di sini.

Untuk menghindari contoh David, kelas maksimal juga harus dapat didefinisikan sebagai grafik bebas-X, di mana tidak setiap grafik di X memiliki simpul independen.

Kelas yang diberikan dalam jawaban di bawah ini:

• bebas apel (disarankan oleh Standa Živný)
• $P_5$
• $K_2 \cup$

Ditambahkan 2013-10-09: hasil terbaru oleh Lokshtanov, Vatshelle dan Villanger, disebutkan oleh Martin Vatshelle dalam sebuah jawaban, menggantikan beberapa kelas maksimal yang sebelumnya dikenal.

$P_5$$P_5$$P_5$$K_{n,n}$$P_5$$X_{82}$$X_{83}$$P_5$

Ini berarti bahwa semua kelas grafik herediter yang didefinisikan oleh satu subgraph tunggal yang diinduksi terlarang hingga lima simpul sekarang dapat secara definitif diklasifikasikan sebagai IS-mudah atau tidak-mudah IS.

$P_5$$P_6$

$X$$X$$Y$$Y \subset X$

Pertanyaannya sudah sedikit lebih tua, tetapi ISGCI dapat membantu di sini.

Ketika Anda memulai aplikasi Java ISGCI dan pergi ke menu Masalah -> Batas / Kelas Terbuka -> Kumpulan independen, Anda mendapatkan dialog dengan 3 daftar.

Daftar Maximal P berisi semua kelas C (dalam ISGCI) di mana IS dapat diselesaikan dalam waktu polinomial, sedemikian sehingga ada superclass minimal C yang IS tidak diketahui berada di P (yaitu NP-complete, open, atau tidak diketahui oleh ISGCI). Memilih kelas dan mengeklik 'Gambar' akan menggambar kelas dan kacamata super yang ditemukan dengan berjalan dengan gaya BFS ke atas hierarki inklusi sejauh diperlukan untuk menemukan kelas di mana IS tidak diketahui berada di P.

Daftar Minimal NP-complete berlaku sebaliknya: Ini berisi kelas-kelas di mana IS adalah NP-complete, sehingga tidak semua subclass maksimal juga NP-complete. Menggambar turun dalam hierarki sampai kelas yang tidak lengkap NP ditemukan.

Daftar terbuka berisi kelas yang masalahnya terbuka atau tidak diketahui. Menggambar berjalan super / subclass sampai kelas tercapai yang tidak terbuka.

Saat membuat gambar, merupakan ide bagus untuk mengatur pewarnaan ke masalah Set Independen (Masalah -> Warna untuk masalah -> set Independen).

Sehubungan dengan pertanyaan Standa Zivny, 20 kelas berikut terdaftar di ISGCI dengan kompleksitas yang diketahui untuk masalah IS yang tidak diperhitungkan, tetapi dengan kompleksitas yang tidak diketahui untuk kasus berbobot (ISGCI tidak dapat membedakan antara algoritma polinomial "sederhana" dan "rumit"):

gc_11 diperpanjang P ₄ -laden
gc_128 EPT
gc_415 baik tertutup
gc_428 (K _3,3 -e, P ₅ , X ₉₈ ) -gratis
gc_648 (K _3,3 -e, P ₅ ) -gratis
gc_752 co-turun-temurun clique-Helly
gc_756 (E, P) -gratis
gc_757 (P, T ₂ ) -gratis
gc_758 (P, P ₈ ) -gratis
gc_759 (K _3,3 -e, P ₅ , X ₉₉ ) -gratis
gc_808 (C ₆ , K _{3, 3} + e, P, P ₇ , X ₃₇ , X ₄₁ ) -gratis
gc_811 (P, bintang_1,2,5 ) -gratis
gc_812 (P ₅ , P ₂ ∪ P ₃ ) -gratis
gc_813 (P, P ₇ ) -gratis
gc_818 (P, bintang _1,2,3 ) -gratis
gc_819 (P, bintang _{1, 2,4} ) -gratis
gc_841 (2K ₃ + e, A, C ₆ , E, K _3,3 -e, P ₆ , R, X ₁₆₆ , X ₁₆₇ , X ₁₆₉ , X ₁₇₀ , X ₁₇₁ , X ₁₇₂ , X ₁₈ , X ₄₅ , X ₅ , X ₅₈ , X ₈₄ , X ₉₅ , X₉₈ , A, C ₆ , E, P ₆ , R, X ₁₆₆ , X ₁₆₇ , X ₁₆₉ , X ₁₇₀ , X ₁₇₁ , X ₁₇₂ , X ₁₈ , X ₄₅ , X ₅ , X ₅₈ , X ₈₄ , X ₉₅ , X ₉₈ , antena, ko-antena, co-domino, co-fish, co-twin-house, domino, fish, twin-house) -gratis
gc_894 sempurna melingkar
gc_895 sangat sempurna melingkar
(3K ₂ , E, P ₂ ∪ P ₄ , bersih) -gratis

Tidak diragukan lagi sejumlah algoritma ini akan diketahui untuk kasus berbobot juga. Penambahan dan koreksi selalu diterima di alamat yang diberikan di halaman web ISGCI!

Makalah yang menarik untuk dilihat mungkin:

A. Brandstadt, VV Lozin, R. Mosca: Set Independen dari Berat Maksimum dalam Grafik Bebas Apple, Jurnal SIAM pada Matematika Diskrit 24 (1) (2010) 239–254. doi: 10.1137 / 090750822

Kelas apel yang tak terbatas didefinisikan sebagai siklus C_k, k> = 5, masing-masing dengan tangkai.

Anda tidak menyebutkan apakah gagasan Anda tentang kemudahan-IS mencakup masalah IS tertimbang. Grafik bebas kursi (alias grafik bebas garpu) dikenal IS-mudah:

VE Alekseev, algoritma Polinomial untuk menemukan set independen terbesar dalam grafik tanpa garpu, Matematika Terapan Diskret 135 (1-3) (2004) 3-16. doi: 10.1016 / S0166-218X (02) 00290-1

Traktabilitas case tertimbang adalah ekstensi non-sepele, lihat:

VV Lozin, M. Milanic: Algoritma polinomial untuk menemukan set independen berat maksimum dalam grafik bebas garpu, Journal of Discrete Algorithms 6 (4) (2008) 595-604. doi: 10.1016 / j.jda.2008.04.001

Apakah ada kelas lain (menarik) di mana masalah IS tertimbang secara signifikan lebih sulit / tidak dapat dipecahkan / terbuka daripada kasus tanpa bobot?

Menurut Vassilis Giakoumakis dan Irena Rusu, Disc. Appl. Matematika 1997 , grafik -gratis (P5, rumah) -gratis (alias (P5, coP5)) mudah-IS.

Satu lagi, dikreditkan oleh ISGCI ke V. Lozin, R. Mosca Disc. Appl. Matematika 2005 , adalah keluarga dari (K2 u claw) -gratis grafik .

Mungkin juga ada rantai tak terbatas dari kelas-kelas traktat

Pasti ada rantai naik yang tak terbatas. Jika H adalah himpunan grafik berhingga yang grafik H-bebasnya IS-mudah, misalkan H 'adalah grafik yang dibentuk dengan menambahkan simpul independen ke setiap grafik dalam H. Kemudian grafik bebas-H juga mudah-IS: cukup terapkan algoritma H-free ke set non-tetangga dari setiap simpul Misalnya, seperti yang dijelaskan ISGCI, grafik co-gem-free adalah IS-easy karena co-gem adalah P4 plus vertex independen dan grafik P4-free adalah IS-easy. Jadi, Anda mungkin ingin membatasi pertanyaan Anda ke kelas maksimal di mana tidak semua subgraph terlarang memiliki simpul independen.

$P_5$

Misalkan H adalah grafik pada paling banyak 5 simpul, maka kerumitan himpunan Independen diketahui pada kelas grafik H-bebas.

$P_5$$H = P_2 \cup P_3$