Diagramme, bei denen die Scheitelpunktfärbung in P ist, die unabhängige Menge jedoch NP vollständig ist

Antworten:

21

Eine vielleicht allgemeinere Aussage (mit einem einfachen Beweis) ist, dass das folgende Problem bereits NP-vollständig ist:

Eingabe: Ein Graph G, eine 3-Färbung von G, eine ganze Zahl k.

Frage: Hat G eine unabhängige Menge der Größe k?

Dies kann durch eine Reduktion von Independent Set nachgewiesen werden. Beachten Sie, dass, wenn wir einen Graphen G nehmen, eine Kante auswählen und zweimal unterteilen (dh die Kante {u, v} durch einen Pfad u, x, y, v ersetzen, wobei x und y Grad zwei haben), dann die Unabhängigkeitszahl von G ist erhöht sich um genau eins. (Sie können zu jeder Menge, die in G unabhängig war, genau x oder y hinzufügen, und die Umkehrung ist auch nicht schwierig.) Die Frage, ob Graph G mit m Kanten eine unabhängige Menge der Größe k hat, ist also äquivalent zu der Frage ob G ', das das Ergebnis der zweimaligen Unterteilung aller Kanten in G ist, eine unabhängige Menge der Größe k + m hat. Beachten Sie jedoch, dass es einfach ist, G 'dreifarbig zu machen, indem Sie G' wie folgt in drei unabhängige Mengen unterteilen: Eine enthält die Scheitelpunkte, die sich ebenfalls in G befanden, und die anderen beiden Klassen enthalten jeweils genau einen der beiden. " Unterteiler " Eckpunkte für jede Kante. Daher konstruiert diese Prozedur einen Graphen G 'mit einer dreifarbigen Darstellung, so dass die Berechnung seiner Unabhängigkeitszahl die Unabhängigkeitszahl des ursprünglichen Graphen G ergibt.

Bart Jansen
quelle
4
Diese Reduktion belegt auch sofort die Härte einer unabhängigen Menge in dreieckfreien planaren Graphen, aus meiner Antwort, ohne Bezugnahme auf schwer zu beschaffende Papiere.
David Eppstein
22

Angeblich beweist die Referenz "NP-vollständige Probleme auf einem 3-zusammenhängenden kubischen planaren Graphen und ihre Anwendungen" von Uehara (eine Arbeit, die ich noch nicht gesehen habe), dass die unabhängige Menge auch für dreieckfreie planare Graphen NP-vollständig ist. Aber nach Grötzschs Theorem sind sie immer dreifarbig, und das Prüfen auf eine kleinere Anzahl von Farben als 3 ist in jedem Diagramm einfach, sodass sie in P optimal eingefärbt werden können.

Kreisgraphen haben die entgegengesetzte Eigenschaft: Für sie ist die Färbung NP-vollständig, aber das Problem der unabhängigen Menge ist einfach.

David Eppstein
quelle
2
Sind Sie sich bei Kreisdiagrammen sicher? Auf der Wiki- Seite heißt es: "Die chromatische Zahl eines Kreisgraphen kann beliebig groß sein, und die Bestimmung der chromatischen Zahl eines Kreisgraphen ist NP-vollständig."
Ankur
Hoppla, ich habe es falsch verstanden. Wird reparieren.
David Eppstein
Vielen Dank. Es wäre toll, andere Beispiele zu bekommen. Das Papier von Uehara scheint etwas isoliert; Es gibt nicht zu viele andere Zeitungen, die es zitieren. Ich bin mir nicht mal sicher, ob es von Fachleuten begutachtet und veröffentlicht wurde.
Ankur
11

Dies ist keine neue Antwort, sondern eine Verdeutlichung der ersten und leicht zu beschaffenden Referenz für die Härte von INDEPENDENT SET in dreieckfreien kubischen ebenen Graphen: Die Anmerkung von Owen Murphy, Computing independent sets in graphs with large girth , Discrete Applied Mathematics 35 (1992) 167-170 beweist dies

ncnkc>0k,0k<1

cc>0

Die von @BartJansen angegebene Reduktion ist ein Sonderfall in Murphys Beweis für seinen Satz.

Für die entgegengesetzte Eigenschaft scheinen Liniendiagramme natürlicher zu sein als Kreisdiagramme, wie sie von @DavidEppstein angesprochen werden. Für Liniendiagramme ist FARBEN NP-vollständig, aber UNABHÄNGIGES SET ist einfach.

user13136
quelle
6
Ein weiteres interessantes Beispiel für die entgegengesetzte Eigenschaft ist die Klasse der gut abgedeckten Graphen (siehe hier und hier ). Für sie ist das Färben schwierig, aber das Independent-Set ist ganz einfach.
vb le