Zusammenhang zwischen der Erkennungshärte einer Graphklasse und der verbotenen Untergraphcharakterisierung

Ich überlege mir Diagrammklassen, die durch verbotene Untergraphen gekennzeichnet werden können.

Wenn eine Graphenklasse eine endliche Menge verbotener Untergraphen enthält, gibt es einen Algorithmus zur Erkennung trivialer Polynomzeiten (man kann einfach rohe Gewalt anwenden). Eine unendliche Familie verbotener Untergraphen impliziert jedoch keine Härte: Es gibt einige Klassen mit einer unendlichen Liste verbotener Untergraphen, sodass die Erkennung auch in polynomieller Zeit getestet werden kann. Chordal- und Perfect-Diagramme sind Beispiele, aber in diesen Fällen gibt es eine "nette" Struktur für die verbotene Familie.

Gibt es einen bekannten Zusammenhang zwischen der Härte der Anerkennung einer Klasse und dem "schlechten Verhalten" der verbotenen Familie? Eine solche Beziehung sollte bestehen? Dieses "schlechte Benehmen" wurde irgendwo formalisiert?

Obwohl es intuitiv scheint , dass die Liste der verbotenen (induziert) Subgraphen für eine Klasse von Graphen , die NP-hard Anerkennung hat sollte eine „intrinsische“ Komplexität besitzen, fand ich vor kurzem einige auffallende negativen Beweise für diese Intuition in der Literatur.$\mathscr{C}$

Die vielleicht einfachste Beschreibung ist die folgende, die einem Artikel von B. Lévêque, D. Lin, F. Maffray und N. Trotignon entnommen ist .

Sei die Familie von Graphen, die aus einem Zyklus mit einer Länge von mindestens vier plus drei Eckpunkten zusammengesetzt sind: zwei neben demselben Eckpunkt des Zyklus und einer neben einem Eckpunkt des Zyklus, wobei und sind nicht aufeinanderfolgend im Zyklus (und keine anderen Kanten).$F$$u$$v$$u$$v$

Nun sei die Familie der Graphen, die genau so zusammengesetzt sind, mit der Ausnahme, dass Sie vier Eckpunkte hinzufügen : zwei neben demselben Eckpunkt des Zyklus (wie zuvor), aber jetzt zwei neben demselben Eckpunkt des Zyklus, wobei wiederum und nicht aufeinander folgen.$F'$$u$$v$$u$$v$

Dann hat die Klasse von Graphen, die als verbotene induzierte Untergraphen hat, eine Polynomzeiterkennung, wohingegen die Erkennung der Klasse, die als verbotene induzierte Untergraphen hat, NP-hart ist.$F$$F'$

Daher fällt es mir schwer, mir eine allgemeine Bedingung vorzustellen, die eine Liste verbotener induzierter Teilgraphen erfüllen muss, wenn sie zu einer Klasse mit (NP-) harter Anerkennung führt, wenn man bedenkt, dass eine solche Bedingung die "sehr ähnlichen" Bedingungen trennen muss. und F ' oben.$F$$F'$

Die Antwort von @Hugo ist wirklich nett, und hier möchte ich einige persönliche Meinungen hinzufügen.

Es gibt verwandte Familien, die den Diagrammen in der Familie F und F 'ähnlich sind. Die Graphen in der Familie B1 im Artikel werden normalerweise als Pyramiden bezeichnet. Und Graphen in Familie B2 werden normalerweise als Prismen bezeichnet. Siehe die Antwort hier für eine Illustration. In der Literatur zu induzierten Subgraphenerkennungsproblemen wurden sie zum Erkennen von geraden / ungeraden Löchern verwendet, die akkordlose Zyklen mit gerader / ungerader Länge sind. Nach dem bekannten starken perfekten Graphensatz ist ein Graph G perfekt, wenn sowohl G als auch das Komplement von G keine ungeraden Löcher enthalten.

Für die Familien der Pyramiden und Prismen gibt es tatsächlich Unterschiede zwischen ihnen - einer hat einen induzierten Teilbaum von drei Blättern und der andere nicht. Dies wird das "Drei-in-einem-Baum" -Problem genannt , das von Chudnovsky und Seymour untersucht wurde. Es ist überraschend, dass die Bestimmung, ob es einen induzierten Baum gibt, der drei gegebene Knoten enthält, nachvollziehbar ist, während das Problem "Vier in einem zentrierten Baum" NP-schwer ist . (Ein zentrierter Baum ist ein Baum mit höchstens einem Knoten mit einem Grad größer als 2.) Die Unterschiede zwischen F und F 'scheinen aus demselben Grund hervorgerufen zu werden.

Es scheint jedoch, dass eine vollständige Charakterisierung immer noch schwierig ist, da wir nicht einmal die Komplexität der Erkennung von Graphen in einigen der Familien kennen, die einfach genug aussieht, wie ungeradzahlige Graphen (!). Und für die Familien, von denen wir wissen, dass es einen Algorithmus für die Polynomzeit gibt, wie perfekte Graphen und Graphen ohne gerade Löcher, obwohl es allgemeine Strategien (basierend auf Zerlegungen) gibt, für die man einen spezifischen Struktursatz bereitstellen muss Sie. Dies ist in der Regel ein familienabhängiger Prozess, und die Beweise sind meist sehr lang. ( Hier ist ein Beispiel für das Diagramm ohne gerade Löcher, bei dem das Papier mehr als 90 Seiten umfasst.)

Dennoch wäre es interessant, einige Klassifikationen für induzierte Subgraphenerkennungsprobleme in dem Sinne zu haben, wie das Drei-in-einem-Baum-Problem.