Maximale Klassen für welche größte unabhängige Menge kann in der Polynomzeit gefunden werden?

Die ISGCI listet über 1100 Klassen von Graphen auf. Für viele von diesen wissen wir, ob INDEPENDENT SET in polynomialer Zeit entschieden werden kann; Diese werden manchmal als IS-easy-Klassen bezeichnet . Ich möchte eine Liste von maximal IS-easy Klassen zusammenstellen. Diese Klassen bilden zusammen die Grenze der (bekannten) Handhabbarkeit für dieses Problem.

Da jeder unendlichen IS-easy-Klasse nur eine endliche Anzahl von Diagrammen hinzugefügt werden kann, ohne die Traktierbarkeit zu beeinträchtigen, sind einige Einschränkungen angebracht. Beschränken wir die Klassen auf diejenigen, die erblich bedingt sind (abgeschlossen unter Verwendung induzierter Subgraphen oder äquivalent definiert durch eine Menge ausgeschlossener induzierter Subgraphen). Betrachten wir außerdem nur die Familien, die für eine Menge X mit einer kleinen Beschreibung X-frei sind. Es könnten sind auch seine unendlichen aufsteigende Ketten lenkbar Klassen (wie $(P,\text{star}_{1,2,k})$-free und die von David Eppstein unten beschriebenen Klassen), aber beschränken wir uns auf Klassen, die sich tatsächlich als IS-leicht erwiesen haben.

Hier sind die, die ich kenne:

• perfekte Grafiken
• -frei$(P,\text{star}_{1,2,5})$
• -frei$(K_{3,3}-e, P_5)$
• Co-Meyniel
• fast zweiteilig
• Stuhl frei
• ( , Cricket) -frei$P_5$
• -frei$(P_5,K_{n,n})$(für ein beliebiges festes )$n$
• -frei$(P_5, X_{82}, X_{83})$

Sind andere solche Maximalklassen bekannt?

Bearbeiten: Siehe auch eine verwandte Frage von Jaroslaw Bulatow, die sich mit Klassen befasst, die von ausgeschlossenen Minderjährigen definiert wurden. Was ist für Diagramme mit Ausschluss von Minderjährigen einfach? und Globale Eigenschaften von Erbklassen sehen? für eine allgemeinere frage habe ich vorher nach erblichen klassen gefragt.

Wie Jukka Suomela in den Kommentaren ausführt, ist der Fall des Ausschlusses von Minderjährigen ebenfalls interessant (und würde eine interessante Frage aufwerfen), aber dies steht hier nicht im Mittelpunkt.

Um Davids Beispiel zu vermeiden, sollte eine maximale Klasse auch als X-freie Diagramme definierbar sein, wobei nicht jedes Diagramm in X einen unabhängigen Scheitelpunkt hat.

Klassen in Antworten unten angegeben:

• apfelfrei (vorgeschlagen von Standa Živný)
• ( , Haus) -frei$P_5$ (vorgeschlagen von David Eppstein)
• ( Klaue) -frei$K_2 \cup$ (vorgeschlagen von David Eppstein)

Hinzugefügt am 09.10.2013: Das jüngste Ergebnis von Lokshtanov, Vatshelle und Villanger, das von Martin Vatshelle in einer Antwort erwähnt wurde, ersetzt einige der zuvor bekannten Maximalklassen.

Insbesondere ist -frei, wenn es IS-leicht ist, unterstellt ( P 5 , Cricket) -frei, ( P 5 , K n , n ) -frei, ( P 5 , X 82 , X 83 ) -frei und ( P 5 , Haus) -frei alles ist IS-leicht.$P_5$$P_5$$P_5$$K_{n,n}$$P_5$$X_{82}$$X_{83}$$P_5$

Dies bedeutet, dass alle erblichen Graphenklassen, die durch einen einzelnen verbotenen induzierten Subgraphen mit bis zu fünf Eckpunkten definiert sind, nun endgültig als IS-leicht oder nicht-IS-leicht klassifiziert werden können.

Leider scheint der Beweis, dass -freie Graphen eine IS-easy-Klasse bilden, für P 6 -freie Graphen nicht zu funktionieren , daher besteht die nächste Grenze darin, alle erblichen Graphenklassen zu klassifizieren, die durch einen einzelnen Sechs-Vertex-Graphen definiert sind.$P_5$$P_6$

Ich interessiere mich weiterhin besonders für IS-easy-Klassen der Form für einige Sammlung X von Graphen mit unendlich vielen Isomorphismusklassen, wobei Y -frei für kein Y ⊂ X IS-leicht ist .$X$$X$$Y$$Y \subset X$

Die Frage ist schon etwas älter, aber ISGCI kann hier hilfreich sein.

Wenn Sie die ISGCI Java-Anwendung starten und das Menü Probleme -> Grenze / Offene Klassen -> Unabhängiger Satz aufrufen, erhalten Sie einen Dialog mit 3 Listen.

Die Liste Maximal P enthält alle Klassen C (in ISGCI), für die IS in Polynomzeit gelöst werden kann, so dass es eine minimale Superklasse von C gibt, für die nicht bekannt ist, dass IS in P ist (dh NP-vollständig, offen oder ISGCI unbekannt). Wenn Sie eine Klasse auswählen und auf "Zeichnen" klicken, werden die Klasse und die Superklassen gezeichnet, die gefunden werden, indem Sie die Einschlusshierarchie im BFS-Stil so weit nach oben schieben, wie es erforderlich ist, um eine Klasse zu finden, für die IS in P nicht bekannt ist.

Die Liste Minimal NP-complete ist umgekehrt: Sie enthält Klassen, bei denen IS NP-complete ist, so dass nicht alle maximalen Unterklassen auch NP-complete sind. Das Zeichnen erfolgt in der Hierarchie, bis eine nicht NP-vollständige Klasse gefunden wird.

Die offene Liste enthält Klassen, für die das Problem entweder offen oder unbekannt ist. Das Zeichnen geht über Super- / Unterklassen, bis eine Klasse erreicht ist, die nicht geöffnet ist.

Wenn Sie eine Zeichnung erstellen, ist es empfehlenswert, die Farbe auf das Independent Set-Problem einzustellen (Probleme -> Farbe für Problem -> Independent Set).

In Bezug auf die Frage von Standa Zivny sind die folgenden 20 Klassen in ISGCI mit bekannter Komplexität für das ungewichtete IS-Problem, aber mit unbekannter Komplexität für den gewichteten Fall aufgelistet (ISGCI kann nicht zwischen "einfachen" und "komplizierten" Polynomalgorithmen unterscheiden):

gc_11 verlängert P ₄ -beladen
gc_128 EPT
gc_415 gut bedeckt
gc_428 (K _3,3 -e, P ₅ , X ₉₈ ) -frei
gc_648 (K _3,3 -e, P ₅ ) -frei
gc_752 co-erbliche Clique-Helly
gc_756 (E, P) -frei
gc_757 (P, T ₂ ) -frei
gc_758 (P, P ₈ ) -frei
gc_759 (K _3,3 -e, P ₅ , X ₉₉ ) -frei
gc_808 (C ₆ , K _{3, 3} + e, P, P ₇ , X ₃₇ , X ₄₁ )
-freies gc_811 (P, Stern_1,2,5 )
-freies gc_812 (P ₅ , P ₂ ∪ P ₃ )
-freies gc_813 (P, P ₇ )
-freies gc_818 (P, Stern _1,2,3 )
-freies gc_819 (P, Stern _{1, 2,4} )
-freies 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 ₉₈ , Antenne, Co-Antenne, Co-Domino, Co-Fisch, Co-Doppelhaus, Domino, Fisch, Doppelhaus) -frei
gc_894 co-kreisförmig perfekt
gc_895 stark kreisförmig perfekt
(3K ₂ , E, P ₂ ∪ P ₄ , netto) -frei

Zweifellos wird eine Reihe dieser Algorithmen auch für den gewichteten Fall bekannt sein. Ergänzungen und Korrekturen sind jederzeit unter der auf der ISGCI-Webseite angegebenen Adresse willkommen!

Ein interessantes Papier zum Anschauen könnte sein:

A. Brandstadt, V. V. Lozin, R. Mosca: Unabhängige Mengen von Maximalgewichten in apfelfreien Diagrammen, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi: 10.1137 / 090750822

Die unendliche Klasse der Äpfel ist definiert als Zyklen C_k, k> = 5 mit jeweils einem Stiel.

Sie erwähnen nicht, ob Ihr Begriff der IS-Leichtigkeit das gewichtete IS-Problem beinhaltet. Stuhlfreie Grafiken (auch als gabelfreie Grafiken bezeichnet) sind bekanntermaßen IS-easy:

VE Alekseev, Polynomalgorithmus zum Auffinden der größten unabhängigen Mengen in Diagrammen ohne Gabeln, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi: 10.1016 / S0166-218X (02) 00290-1

Die Nachvollziehbarkeit des gewichteten Falls ist eine nicht triviale Erweiterung, siehe:

VV Lozin, M. Milanic: Ein Polynomalgorithmus zur Ermittlung eines unabhängigen Satzes von Maximalgewichten in einem gabelfreien Graphen, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi: 10.1016 / j.jda.2008.04.001

Gibt es andere (interessante) Klassen, in denen das gewichtete IS-Problem wesentlich schwieriger / nicht lösbar / offener als der ungewichtete Fall ist?

Nach Vassilis Giakoumakis und Irena Rusu, Disc. Appl. Mathematik. 1997 sind die (P5, house) -freien Graphen (aka (P5, coP5) -freie Graphen) IS-easy.

Eine weitere, die ISGCI V. Lozin, R. Mosca Disc gutgeschrieben hat . Appl. Mathematik. 2005 ist die Familie der (K2 u claw) -freien Graphen .

Es kann auch unendlich aufsteigende Ketten von handhabbaren Klassen geben

Es gibt definitiv unendlich viele aufsteigende Ketten. Wenn H eine endliche Menge von Graphen ist, für die die H-freien Graphen IS-leicht sind, sei H 'die gebildeten Graphen, die jedem Graphen in H einen unabhängigen Scheitelpunkt hinzufügen. Dann sind die H'-freien Graphen auch IS-leicht: Wenden Sie einfach den H-freien Algorithmus auf die Mengen von Nichtnachbarn jedes Scheitelpunkts an. Zum Beispiel, wie ISGCI beschreibt, sind die Co- Gem -freien Graphen IS-easy, weil ein Co-Gem ein P4 plus ein unabhängiger Vertex ist und die P4-freien Graphen IS-easy sind. Sie möchten Ihre Frage wahrscheinlich auf maximale Klassen beschränken, in denen nicht alle verbotenen Untergraphen einen unabhängigen Scheitelpunkt haben.

$P_5$

Sei H ein Graph auf höchstens 5 Eckpunkten, dann ist die Komplexität der unabhängigen Menge in der Klasse der H-freien Graphen bekannt.

$P_5$$H = P_2 \cup P_3$