Diagrammfamilien mit polynomiellen Zeitalgorithmen zur Berechnung der chromatischen Zahl

Beitrag aktualisiert am 31. August : Ich habe eine Zusammenfassung der aktuellen Antworten unterhalb der ursprünglichen Frage hinzugefügt. Danke für all die interessanten Antworten! Natürlich kann jeder weiterhin neue Erkenntnisse veröffentlichen.

Für welche Graphenfamilien gibt es einen polynomiellen Zeitalgorithmus zur Berechnung der chromatischen Zahl ?$\chi(G)$

Das Problem ist in der Polynomzeit lösbar, wenn (zweigliedrige Graphen) ist. Wenn , ist die Berechnung der chromatischen Zahl im Allgemeinen NP-schwer, aber es gibt viele Graphenfamilien, in denen dies nicht der Fall ist. Zum Beispiel können Farbzyklen und perfekte Grafiken in Polynomzeit erstellt werden.$\chi(G) = 2$$\chi(G) \ge 3$

Außerdem können wir für viele Grafikklassen einfach das entsprechende chromatische Polynom auswerten. Einige Beispiele in Mathworld .

Ich nehme an, das meiste ist allgemein bekannt. Ich würde gerne erfahren, ob es andere (nicht-triviale) Graphenfamilien gibt, für die die minimale Graphenfärbung in Polynomzeit lösbar ist.

Insbesondere interessiere ich mich für exakte und deterministische Algorithmen, kann aber auch auf interessante randomisierte Algorithmen oder Approximationsalgorithmen hinweisen.

Update (31. August):

Vielen Dank an alle für die interessanten Antworten. Hier ist eine kurze Zusammenfassung der Antworten und Referenzen.

Perfekte und fast perfekte Grafiken

• Geometrische Algorithmen und kombinatorische Optimierung (1988), Kapitel 9 (Stabile Mengen in Graphen). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.

  Kapitel 9 des Buches zeigt, wie Sie das Farbproblem mithilfe des minimalen Clique-Covering-Problems lösen können. Da sie auf der Ellipsoidmethode beruhen, sind diese Algorithmen in der Praxis möglicherweise nicht sehr nützlich. Außerdem enthält das Kapitel eine schöne Referenzliste für verschiedene Klassen perfekter Grafiken.

• Combinatorial Optimization (2003), Band B, Abschnitt VI Alexander Schrijver.

  Dieses Buch enthält drei Kapitel, die sich mit perfekten Graphen und ihrer zeitlichen Färbbarkeit von Polynomen befassen. Ich habe nur einen kurzen Blick darauf geworfen, aber der grundlegende Ansatz scheint der gleiche zu sein wie im vorherigen Buch.

• Eine Charakterisierung von b-perfect Graphen (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Grafiken mit begrenzter Baumbreite oder Cliquebreite

• Randdominierende Menge und Färbungen bei Graphen mit fester Cliquenbreite (2001). Daniel Kobler, Udi Rotics

  Die Algorithmen benötigen hier einen k-Ausdruck (eine algebraische Formel zum Konstruieren eines Graphen mit einer begrenzten Cliquenbreite) als Parameter. Für einige Diagramme kann dieser Ausdruck in linearer Zeit berechnet werden.

• Jaroslaw wies in Methoden zur Zählung von Färbungen in beschränkten Baumbreitengraphen. Siehe seine Antwort unten.

Diese beiden Studiendiagrammfamilien, in denen Eckpunkte oder Kanten hinzugefügt oder gelöscht werden können.$k$

• Parametrisierte Komplexität der Vertexfärbung (2003). Leizhen Cai.

  Die Färbung kann in Polynomzeit gelöst werden, wenn Kanten (für festes ) in geteilten Diagrammen hinzugefügt oder gelöscht werden .$k$$k$

• Parametrisierte Farbprobleme auf Akkorddiagrammen (2006). Dániel Marx.

  Für festes können Akkorddiagramme, zu denen Kanten hinzugefügt werden, in Polynomzeit gefärbt werden.$k$$k$

Grafiken, die keine bestimmten Untergraphen enthalten

• Entscheidung über die k-Färbbarkeit von P5-freien Graphen in der Polynomialzeit (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada und Xiao Shu.

• 3-farbige AT-freie Graphen in Polynomzeit (2010). Juraj Stacho.

Quadtrees färben

• Algorithmen zum Färben von Quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.

Wie Sie sehen, können alle perfekten Graphen in Polynomialzeit gefärbt werden, aber ich denke, der Beweis umfasst Ellipsoidalgorithmen für die lineare Programmierung (siehe das Buch von Grötschel, Lovász und Schrijver) und nicht alles, was direkt und kombinatorisch ist. Es gibt viele verschiedene Klassen von Diagrammen, die Unterklassen von perfekten Diagrammen sind und einfachere Farbalgorithmen haben. Beispielsweise können Akkordgraphen mit einer perfekten Eliminierungsreihenfolge gierig eingefärbt werden.

Alle lokal verbundenen Graphen (Graphen, in denen jeder Scheitelpunkt eine verbundene Nachbarschaft hat) können in der Polynomzeit dreifarbig sein, wenn eine Färbung vorliegt: Erweitern Sie einfach das Färbungsdreieck um Dreieck.

Graphen mit maximal drei Graden können in Polynomzeit gefärbt werden: Es ist einfach zu testen, ob sie zweigeteilt sind, und wenn nicht, benötigen sie entweder nur drei Farben oder sie haben K4 als verbundene Komponente und benötigen vier Farben (Brooks-Theorem).

Dreieckfreie planare Graphen können aus demselben Grund in Polynomzeit gefärbt werden: Sie sind höchstens 3-chromatisch (Satz von Grötzsch).

b-perfect Graphen Sie 5-Zyklen induzierte ( im Gegensatz zu perfekten Graphen) und wurde einen Polynom-Algorithmus zum Einfärben von Hoàng, Maffray und Mechebbek, gezeigt haben , eine Charakterisierung von B-perfect Graphen , arXiv: 1004,5306 , 2010 , .

(Es ist schade, dass das wunderbare Kompendium der Grafikklassen am ISGCI nur die Gruppenbreite, die unabhängige Menge und die Dominanz abdeckt. Es enthält keine Informationen über die Färbung.)

Auch für Diagramme mit begrenzter Cliquenbreite (die allgemeiner als die Baumbreite ist): Kobler und Rotics .

$n^{f(k)}$

Auch die Cliquenbreite ist schwer zu berechnen, aber es gibt einen Näherungsalgorithmus von Oum und Seymour, der "Cliquenbreite und Zweigbreite annähert" (mit exponentieller Näherung).

$k$

Jede Familie von Graphen mit begrenzter Baumbreite verfügt über einen polynomiellen Zeitalgorithmus zur Berechnung der chromatischen Zahl. Gamarnik reduziert das Problem des Zählens von Färbungen auf das des Berechnens von Rändern bestimmter Markov-Zufallsfelder, die in demselben Diagramm definiert sind. Das Ergebnis folgt, weil mit dem Junction-Tree- Algorithmus die Ränder von MRFs in Diagrammen mit begrenzter Baumbreite in Polynomzeit berechnet werden können .

Update 8/26 : Hier ist ein Beispiel für die Reduzierung der "Anzahl der Farbtöne" <-> der Ränder. Es muss mit einer korrekten Färbung begonnen werden, die in Polynomzeit für Diagramme mit begrenzter Baumbreite mit der Max-Plus-Version des Junction-Tree-Algorithmus gefunden werden kann. Nun, um es sich vorzustellen ... Sie brauchen nicht wirklich eine Anzahl von Farben für die chromatische Zahl, sondern nur eine einzige richtige Farbe

$P_5$$C_5$$P_5$

$2P_3$

Es gibt auch Ergebnisse von Daniel Marx bezüglich der Komplexität des Problems der chromatischen Zahlen in Graphen, die durch höchstens k Vertex-Deletionen akkordisch gemacht werden können; Für jedes feste k ist dieses Problem polynomisch ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Algorithmen zum Färben von Quadtrees .
M. Bern, D. Eppstein und B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87 & ndash; 94, 2002.

Wir betrachten verschiedene Variationen des Problems der Färbung der Quadrate eines Quadtrees, so dass keine zwei benachbarten Quadrate gleich gefärbt sind. Wir geben einfache lineare Zeitalgorithmen für 3-farbige ausgeglichene Quadtrees mit Kantenanpassung, 4-farbige unausgeglichene Quadtrees mit Kantenanpassung und 6-farbige ausgeglichene oder unausgeglichene Quadtrees mit Eckenanpassung. Die Anzahl der von den ersten beiden Algorithmen verwendeten Farben ist optimal. Für den dritten Algorithmus werden manchmal 5 Farben benötigt.