Referensi untuk (ganjil-lubang, antihole) grafik -gratis?

Grafik bebas-X adalah grafik yang tidak mengandung grafik dari X sebagai subgraf yang diinduksi. Sebuah lubang adalah siklus dengan setidaknya 4 simpul. Sebuah aneh-lubang lubang dengan jumlah ganjil simpul. Sebuah antihole adalah komplemen dari lubang.

Grafik (ganjil-lubang, ganjil-antihole) -gratis adalah grafik sempurna; ini adalah Teorema Grafik Sempurna yang Kuat . Dimungkinkan untuk menemukan set independen terbesar (dan klik terbesar) dalam grafik sempurna dalam waktu polinomial, tetapi satu-satunya metode yang diketahui untuk melakukannya memerlukan pembangunan program semi-pasti untuk menghitung nomor theta Lovász .

Grafik (lubang, antihole) -gratis disebut chordal lemah , dan merupakan kelas yang agak mudah untuk banyak masalah (termasuk SET INDEPENDEN dan CLIQUE ).

Apakah ada yang tahu jika (ganjil-lubang, antihole) grafik -gratis telah dipelajari atau ditulis?

Grafik ini muncul secara alami dalam masalah kepuasan kendala di mana grafik variabel terkait membentuk pohon. Masalah seperti itu agak mudah, jadi alangkah baiknya jika ada cara untuk menemukan set kelompok independen terbesar untuk grafik dalam keluarga ini tanpa harus menghitung theta Lovász.

Setara, orang ingin menemukan set independen terbesar untuk grafik bebas (hole, odd-antihole). Hsien-Chih Chang menunjukkan di bawah mengapa ini adalah kelas yang lebih menarik untuk SET INDEPENDEN daripada grafik ganjil (lubang ganjil, antihole).

Padahal, itu relatif mudah. Alih-alih untuk mempelajari masalah set independen dalam grafik-bebas (lubang ganjil, antihole) -gratis, kami mengambil komplemen dari grafik dan mencoba untuk menemukan klik maksimum di dalamnya. Dengan demikian itu menjadi masalah klik maksimum dalam grafik (hole, anti-odd-hole) -gratis.

Dalam bagian 2 dari makalah " Triangulasi Lingkungan dalam Grafik bebas lubang " oleh da Silva dan Vuskovic, mereka menyatakan bahwa Farber pertama kali menunjukkan

$O(n^2)$

Kemudian teorema utama mereka menyatakan itu

$O(n + m)$$O(n^2m)$

$O(n^2m)$

$\overline{K_{2,m}}$

Edit:

Oh, pikiran lain muncul. (hole, anti-odd-hole) -gratis grafik hampir lemah chordal dalam arti berikut: karena 4-hole-free menyiratkan hanya ada anti-hole dengan ukuran 4 ~ 7 tetap (setiap k-anti-hole dengan ukuran> 7 berisi 4-hole), dan juga anti-odd-hole-free yang membatasi ukuran anti-hole hingga 4 dan 6, hampir tidak ada hole / antiholes dalam grafik! Jadi algoritma waktu-poli tampaknya masuk akal untuk grafik semacam itu.