Diagrammfamilien mit polynomiellen Zeitalgorithmen zur Berechnung der chromatischen Zahl

23

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 ?χ(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.χ(G)=2χ(G)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

Grafiken, die keine bestimmten Untergraphen enthalten

Quadtrees färben

Joel Rybicki
quelle
1
Vergleichsgraphen. Dies ist wahrscheinlich eine der unbedeutenden Familien, aber ich denke immer noch, dass sie erwähnt werden sollten, weshalb ich einen Kommentar anstelle einer Antwort verwende.
Radu GRIGore
Meinten Sie Vergleichbarkeitsdiagramme oder sind Vergleichsdiagramme eine andere Klasse?
Joel Rybicki
Ich meinte Vergleichbarkeitsgraphen, die perfekt sind.
Radu GRIGore
Beachten Sie, dass b-perfect-Graphen nahezu perfekt sind, dies jedoch nicht so ist, da sie möglicherweise 5 Zyklen enthalten.
András Salamon
Ihr Link für Cais Artikel ist falsch.
Jeremy Kun

Antworten:

14

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).

David Eppstein
quelle
8

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.)

András Salamon
quelle
In Bezug auf ISGCI: Wenn unabhängige Sets einfach sind, könnte dies ein Hinweis darauf sein, dass auch das Färben einfach sein könnte. Daher könnte das Durchsuchen von ISGCI einige neue Ideen für weiteres Googeln liefern.
Jukka Suomela
Darüber hinaus berücksichtigen viele der auf der ISGCI zitierten Papiere sowohl die Färbung als auch CLIQUE / INDEPENDENT SET. Aber es gibt über 1000 Verweise, durch die man waten kann ...
András Salamon
Vielen Dank. ISGCI sieht vielversprechend aus, also werde ich vielleicht dort stöbern.
Joel Rybicki
8

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

nf(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

Magnus Wahlström
quelle
8

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

Jaroslaw Bulatow
quelle
6

P5C5P5

2P3

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 ).

Bart Jansen
quelle
Vielen Dank! Diese Referenzen scheinen ziemlich interessant zu sein (insbesondere das Papier "Entscheidung über die k-Färbbarkeit von P5-freien Graphen im Polynom").
Joel Rybicki
4

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.

Aryabhata
quelle