In einem Diagramm ist eine unabhängige Menge eine Scheitelpunktuntermenge, die keine Kante als induzierten Untergraphen enthält. Das Problem, die größten unabhängigen Mengen in einem Graphen zu finden, ist eine grundlegende algorithmische Frage, und zwar eine schwierige. Betrachten wir die allgemeinere Frage des Findens (der Größe) einer größten H-freien Menge in einem Graphen, wobei H-frei bedeutet, dass kein Untergraph induziert wird, der eine Kopie des festen Graphen H als induzierten Untergraphen enthält.
Ist es für den festen Graphen H bei gegebenem Eingangsgraphen G NP-schwierig, die Größe eines größten H-freien Satzes in G zu bestimmen?
Gibt es eine sinnvolle Möglichkeit, eine "Tabelle" von Graphen H (oder Klassen von H) zu erstellen, um die Einträge mit korrekten Ja- oder "Nein" -Antworten auf die obige Frage auszufüllen? (Stellen wir uns vor, dass "no" = P ist und sogar, dass ein "no" -Eintrag bedeutet, dass es einen Polytime-Algorithmus gibt, um eine größte H-freie Menge zu erzeugen.)
Andernfalls gibt es nicht triviale Klassen von H, für die die Antwort Ja lautet? ... Nein?
Ich habe mich umgesehen und zwei Fragen zu verallgemeinerten / H-freien chromatischen Zahlen untersucht - hier und hier -, als mir der Gedanke kam, dass das (scheinbar einfachere) "duale" Problem eines H-freien Analogons der Unabhängigkeitszahl könnte auch offen sein. Mir sind klassische Arbeiten zu einem verwandten Problem für Zufallsgraphen bekannt, vgl. zB Erdos, Suen und Winkler (1995) oder Bollobas und Thomason (2000), die sich noch in einer sehr aktiven Forschungsrichtung befinden. Vielleicht gibt es bereits einige Arbeiten, die ich noch nicht gesehen habe, um diese grundlegendere Frage zu beantworten, und die eine grobe Internetsuche nicht aufgedeckt hat (daher das Referenzanforderungs-Tag).
Antworten:
[1] John M. Lewis, Mihalis Yannakakis: Das Problem der Knotenlöschung für erbliche Eigenschaften ist NP-vollständig. J. Comput. Syst. Sci. 20 (2): 219 & ndash; 230 (1980)
quelle