Maksymalne klasy, dla których największy niezależny zbiór można znaleźć w czasie wielomianowym?

W ISGCI listy ponad 1100 klas grafów. W przypadku wielu z nich wiemy, czy można ustalić niezależny zestaw w czasie wielomianowym; nazywane są czasem klasami IS-easy . Chciałbym skompilować listę maksymalnych klas IS-easy. Klasy te razem tworzą granicę (znanej) podatności na rozwiązywanie tego problemu.

Ponieważ do dowolnej nieskończonej klasy IS-easy można po prostu dodać skończoną liczbę wykresów, nie wpływając na łatwość obsługi, pewne ograniczenia są w porządku. Ograniczmy klasy do tych, które są dziedziczne (zamknięte przy pobieraniu indukowanych podgrafów lub równoważnie, zdefiniowane przez zestaw wykluczonych indukowanych podgrafów). Co więcej, rozważmy tylko te rodziny, które nie zawierają X dla zestawu X z małym opisem. Nie może to również być nieskończone łańcuchy rosnące klas tractable (takie jak $(P,\text{star}_{1,2,k})$-bezpłatne i klasy opisane przez Davida Eppsteina poniżej), ale ograniczmy uwagę do klas, które faktycznie okazały się IS-łatwe.

Oto te, które znam:

• idealne wykresy
• -bezpłatnie$(P,\text{star}_{1,2,5})$
• -Darmowy$(K_{3,3}-e, P_5)$
• co-Meyniel
• prawie dwustronny
• bez fotela
• ( , krykiet) -bezpłatnie$P_5$
• -bezpłatnie$(P_5,K_{n,n})$(dla dowolnego ustalonego )$n$
• -Darmowy$(P_5, X_{82}, X_{83})$

Czy znane są inne takie maksymalne klasy?

Edycja: Zobacz także powiązane pytanie Jarosława Bułatowa dotyczące klas określonych przez wykluczonych nieletnich, co jest łatwe dla wykresów wykluczonych przez osoby niepełnoletnie? i zobacz Globalne właściwości klas dziedzicznych? na bardziej ogólne pytanie, które wcześniej zadałem na temat klas dziedzicznych.

Jak zauważa Jukka Suomela w komentarzach, sprawa pomniejszona o wykluczenie jest również interesująca (i zadałaby interesujące pytanie), ale nie na tym koncentruje się.

Aby uniknąć przykładu Davida, maksymalna klasa powinna być również definiowana jako grafy wolne od X, gdzie nie każdy wykres w X ma niezależny wierzchołek.

Klasy podane w odpowiedziach poniżej:

• bez jabłek (sugerowane przez Standa Živný)
• $P_5$
• $K_2 \cup$

Dodano 09.10.2013: niedawny wynik Lokshtanova, Vatshelle i Villanger, wspomniany w odpowiedzi przez Martina Vatshelle, zastępuje niektóre z wcześniej znanych maksymalnych klas.

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

Oznacza to, że wszystkie dziedziczne klasy grafów zdefiniowane przez pojedynczy zabroniony indukowany podgraph z maksymalnie pięcioma wierzchołkami można teraz ostatecznie zaklasyfikować jako IS-easy lub nie-IS-easy.

$P_5$$P_6$

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

Pytanie jest już trochę starsze, ale ISGCI może tu pomóc.

Po uruchomieniu aplikacji Java ISGCI i przejściu do menu Problemy -> Klasy brzegowe / Otwarte -> Zestaw niezależny, pojawia się okno dialogowe z 3 listami.

Lista Maksymalne P zawiera wszystkie klasy C (w ISGCI), w których IS można rozwiązać w czasie wielomianowym, tak że istnieje minimalna nadklasa C, w której IS nie jest znane z P (tj. NP-zupełne, otwarte lub nieznany ISGCI). Wybranie klasy i kliknięcie przycisku „Rysuj” spowoduje narysowanie klasy i nadklas, które zostaną znalezione po przejściu w stylu BFS w górę hierarchii włączania, o ile jest to konieczne, aby znaleźć klasę, w której IS nie jest znany z P.

Lista Minimalna NP-zupełna odwraca się: zawiera klasy, w których IS jest NP-zupełna, tak że nie wszystkie maksymalne podklasy są również NP-zupełne. Rysowanie przechodzi w hierarchii, dopóki nie zostanie znaleziona klasa niekompletna.

Otwarta lista zawiera klasy, dla których problem jest otwarty lub nieznany. Rysowanie przechodzi po superklasach / podklasach, dopóki nie zostanie osiągnięta klasa, która nie jest otwarta.

Podczas tworzenia rysunku dobrym pomysłem jest ustawienie kolorystyki na problem zestawu niezależnego (Problemy -> Kolor problemu -> Zestaw niezależny).

Jeśli chodzi o pytanie Standy Zivny, w ISGCI wymienionych jest 20 klas o znanej złożoności dla nieważonego problemu IS, ale o nieznanej złożoności w przypadku ważonym (ISGCI nie może rozróżnić między „prostymi” i „skomplikowanymi” algorytmami wielomianowymi):

gc_11 rozszerzony P _4- obciążony
gc_128 EPT
gc_415 dobrze przykryty
gc_428 (K _3,3 -e, P ₅ , X ₉₈ ) -
wolny gc_648 (K _3,3 -e, P ₅ ) -
wolny gc_752 współ-dziedziczna klika-Helly
gc_756 (E, P) -
wolny gc_757 (P, T ₂ ) -
wolny gc_758 (P, P ₈ ) -
wolny gc_759 (K _3,3 -e, P ₅ , X ₉₉ ) -
wolny gc_808 (C ₆ , K _{3, 3} + e, P, P ₇ , X ₃₇ , X ₄₁ ) -
wolny gc_811 (P, gwiazda_1,2,5 ) -
wolny gc_812 (P ₅ , P ₂ ∪ P ₃ ) -
wolny gc_813 (P, P ₇ ) -
wolny gc_818 (P, gwiazda _1,2,3 ) -
wolny gc_819 (P, gwiazda _{1, 2,4} ) -
wolny 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, co-antena, co-domino, co-fish, co-twin-house, domino, fish, twin-house) - bez
gc_894 co-circular perfect
gc_895 silnie okrągły idealny
(3K ₂ , E, P ₂ ∪ P ₄ , netto) -bezpłatnie

Bez wątpienia wiele z nich będzie miało również znane algorytmy dla ważonego przypadku. Dodatki i poprawki są zawsze mile widziane pod adresem podanym na stronie internetowej ISGCI!

Ciekawym artykułem do obejrzenia może być:

A. Brandstadt, VV Lozin, R. Mosca: Niezależne zestawy maksymalnej masy w grafach bez Apple, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi: 10.1137 / 090750822

Nieskończoną klasę jabłek definiuje się jako cykle C_k, k> = 5, każde z łodygą.

Nie wspominasz, czy twoje pojęcie łatwości IS obejmuje ważony problem IS. Grafy bez fotela (inaczej grafy bez widelca) są znane jako IS-easy:

VE Alekseev, algorytm wielomianowy do znajdowania największych niezależnych zbiorów na wykresach bez widelców, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi: 10.1016 / S0166-218X (02) 00290-1

Możliwość przeważenia ważonego przypadku jest nietrywialnym rozszerzeniem, patrz:

VV Lozin, M. Milanic: Algorytm wielomianowy do znalezienia niezależnego zestawu ciężaru maksymalnego na wykresie bez widelca, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi: 10.1016 / j.jda.2008.04.001

Czy istnieją inne (interesujące) klasy, w których ważony problem IS jest znacznie trudniejszy / trudniejszy do rozwiązania / otwarty niż przypadek nieważony?

Według Vassilisa Giakoumakisa i Ireny Rusu, dysk. Appl. Matematyka 1997 , wykresy wolne od (P5, house) (inaczej wykresy wolne od (P5, coP5)) są łatwe w IS.

Kolejny, przypisany przez ISGCI V. Lozinowi, R. Mosca Disc. Appl. Matematyka 2005 , to rodzina grafów wolnych od (K2 u claw) .

Mogą istnieć również nieskończone łańcuchy rosnące klas możliwych do przełożenia

Zdecydowanie istnieją nieskończone łańcuchy rosnące. Jeśli H jest skończonym zestawem wykresów, dla których wykresy wolne od H są łatwe do IS, niech H 'będzie wykresami utworzonymi, dodając niezależny wierzchołek do każdego wykresu w H. Wówczas wykresy wolne od H's są również łatwe do IS: po prostu zastosuj algorytm wolny od H do zbiorów nie sąsiadów każdego wierzchołka. Na przykład, jak opisuje ISGCI, wykresy wolne od klejnotów są łatwe w IS, ponieważ klejnotem jest P4 plus niezależny wierzchołek, a wykresy wolne od IS są łatwe. Prawdopodobnie chcesz ograniczyć swoje pytanie do maksymalnych klas, w których nie wszystkie zabronione podgrupy mają niezależny wierzchołek.

$P_5$

Niech H będzie wykresem co najwyżej 5 wierzchołków, wtedy złożoność zbioru niezależnego jest znana w klasie grafów wolnych od H.

$P_5$$H = P_2 \cup P_3$