Odniesienia do wykresów wolnych od (nieparzystych, dziurawych)?

Wykresy wolne od X to te, które nie zawierają wykresu z X jako indukowanego podgrupy. Otwór jest cykl co najmniej 4 wierzchołków. Odd-dziura jest dziura z nieparzystej liczby wierzchołków. Antihole jest dopełnieniem otworem.

Wykresy wolne od (nieparzystej dziury, nieparzystej antihole) są dokładnie idealnymi grafami; to jest twierdzenie Strong Perfect Graph . Możliwe jest znalezienie największego niezależnego zestawu (i największej kliki) na idealnym wykresie w czasie wielomianowym, ale jedyna znana metoda tego wymaga zbudowania półokreślonego programu do obliczenia liczby Lovásza theta .

Grafiki wolne od (dziurki, dziurki i dziury) nazywane są słabo akordowymi i stanowią dość łatwą klasę dla wielu problemów (w tym INDEPENDENT SET i CLIQUE ).

Czy ktoś wie, czy przestudiowano lub napisano o grafach wolnych od nieparzystej dziury, antihole?

Te wykresy występują dość naturalnie w problemach satysfakcji z ograniczeń, gdzie wykres powiązanych zmiennych tworzy drzewo. Takie problemy są raczej łatwe, więc byłoby miło, gdyby istniał sposób znalezienia największej niezależnej kliki zestawów grafów w tej rodzinie bez konieczności obliczania Lovásza theta.

Równolegle chce się znaleźć największy niezależny zestaw dla wykresów wolnych od (dziurki, nieparzyste-dziury). Hsien-Chih Chang wyjaśnia poniżej, dlaczego jest to bardziej interesująca klasa dla INDEPENDENT SET niż wykresy wolne od nieparzystych otworów i antihole.

W rzeczywistości jest to stosunkowo łatwe. Zamiast tego, aby zbadać problem z niezależnym zestawem w grafach wolnych od (nieparzystej dziury, antihole), bierzemy uzupełnienie wykresów i staramy się znaleźć w nim maksymalną klikę. W ten sposób staje się maksymalnym problemem kliki w grafikach wolnych od (dziurki, nieparzystych dziur).

W sekcji 2 artykułu „ Trójkątne sąsiedztwa w grafach bez dziur ” autorstwa Silvy i Vuskovica stwierdzili, że Farber po raz pierwszy pokazuje

Istnieje $O(n^2)$

Następnie ich główne twierdzenie to stwierdziło

Na wykresach bez dziur równych są maksymalne kliky , a wszystkie maksymalne kliky można znaleźć w czasie O ( n 2$O(n + m)$$O(n^2m)$

Ponieważ mamy do czynienia z wykresami wolnymi od (dziur, nieparzystych), które są wyraźnie pozbawione dziur, znalezienie maksymalnej kliki zajmuje najwyżej $O(n^2m)$

Brak 4 otworów ma kluczowe znaczenie dla tego rodzaju wyników, takich jak algorytm wieloczasowy dla $\overline{K_{2,m}}$ grafów , więc prawdziwym wyzwaniem może być badanie niezależnego zestawu problemów w (bez dziur, przeciw nieparzystym) zamiast tego wykresy, które stają się maksymalnym problemem kliki w grafikach wolnych od (nieparzystych, przeciw-dziurkowych).

Edytować:

Och, pojawiła się kolejna myśl. Wykresy wolne od (dziury, nieparzystej dziury) są prawie słabo akordowe w tym sensie: ponieważ brak 4 dziur oznacza, że ​​istnieją tylko anty-dziury o rozmiarze 4 ~ 7 (dowolna k-dziura o rozmiarze> 7 zawiera 4-dołkowe), i jest również wolne od nieparzystych otworów, które ograniczają rozmiar anty-dziur do 4 i 6, to prawie nie ma dziur / antiholes na wykresie! Dlatego algorytm wieloczasowy wydaje się wiarygodny dla takich wykresów.