22
Chromatische Zahl

Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Embed Size (px)

Citation preview

Page 1: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Chromatische Zahl

Page 2: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Graphfärben

Gegeben: Graph G=(V,E)

Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche Farben erhalten.

Notation: Chromatische Zahl c(G) … minimale Anzahl Farben

Beispiele:

Page 3: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Graphfärben (2)

Komplexitätsaussagen:

– Problem ist NP-schwer k ≥ 3: entscheiden ob ein gegebener Graph k-färbbar ist, ist NP-vollständig [ Beachte: 2-Färbbarkeit ist einfach! ]

Planare Graphen:

– Problem ist NP-schwer– k = 3: entscheiden ob ein gegebener planarer Graph 3-färbbar ist, ist NP-vollständig

Aber: 4-Farben-Satz impliziert, dass jeder planare Graph in Zeit O(n2) mit

vier Farben gefärbt werden kann.

Page 4: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Approximationsalgorithmen

Planare Graphen: Es gibt einen 4/3-Approximationalgorithmus – und

dies ist bestmöglich, ausser P=NP.

Allgemeine Graphen: ………..

3-färbbare Graphen: ………..

Page 5: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Allgemeine Graphen

Algorithmus von Johnson (1973)Eingabe: Graph G=(V,E)

k := 1;repeat Finde `geschickt´ eine stabile Menge S in G. Färbe alle Knoten in S mit Farbe k. k := k+1; G := G[V \ S];until (G is empty)

Page 6: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Finden von stabilen Mengen

Algorithmus StableSet

Eingabe: Graph G=(V,E)

Ausgabe: stabile Menge S in G

S := ? ;repeat

Wähle (beliebigen) Knoten v mit minimalem Grad.

S := S U {v};

G := G[V \ ( {v} U Γ(v) )];

until (G is empty)

Page 7: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Analyse

Lemma: G k-färbbar Þ |S| ³ log(n) / log(k)

Satz: Algorithmus von Johnson ist ein

(n/log(n)) – Approximationsalgorithmus für

die chromatische Zahl.

Page 8: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

State of the Art

Halldórsson (1993)

Es gibt einen (n · (loglog(n))2 / (log(n))3 ) – Approximationsalgorithmus.

Feige, Kilian (1998)

Nicht approximierbar bis auf n1-ε für jedes ε > 0, ausser ZPP=NP.

Page 9: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

3-färbbare Graphen

Algorithmus von Wigderson (1983)Eingabe: Graph G=(V,E)

k := 1;while ( maxdegree(G) ³ Ön ) do Wähle (beliebigen) Knoten v mit maximalem Grad. Färbe v mit Farbe k und Γ(v) mit Farben k+1 und k+2. k := k+3; G := G[V \ ( {v} U Γ(v) ];end doFärbe G mit Farben k,…,k+ Ön-1; [ → Satz von Brooks]

Page 10: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Analyse

Satz: Algorithmus von Wigderson ist ein O(Ön) – Approximationsalgorithmus für 3-färbbare Graphen. Beweis:• while-Schleife wird höchstens n/Ön = Ön oft

durchlaufen Þ für die while-Schleife werden höchstens 3Ön

Farben benötigt.• Färben des Restgraphens benötigt höchstens

Ön zusätzliche Farben.

Page 11: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

State of the Art: 3-färbbare Graphen

Arora, Chlamtac, Charitar (2006)

Es gibt einen n0.2111 – Approximationsalg.

Khanna, Linial, Safra (1993)

Nicht approximierbar bis auf 5/3-ε für jedes ε > 0, ausser P=NP.

[D.h., es gibt keinen Algorithmus der mit 4 Farben auskommt.]

Page 12: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

PTAS for TSP in weighted planar graphs

Page 13: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Kurze Wiederholung

TSP:

nicht in APX, ausser P=NP

Δ-TSP:

Christofides: 3/2-Approximationsalg.

Papadimitriou, Yannakakis: APX-vollständig

Hamiltonkreis in planaren Graphen:

NP-vollständig, sogar in 3-regulären planaren Gr.

Page 14: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

TSP in planaren Graphen

TSP in planaren Graphen:Gegeben: planarer Graph G=(V,E) Gewichtsfunktion w : E → N Gesucht: „Walk“ (v1,…,vk) mit v1=vk der alle Knoten enthält und minimale Länge hat

Alternativ: Bestimme minimalen Hamiltonkreis in vollständigem Graphen in dem das Gewicht der Kante {u,v} genau der Länge eines kürzesten u-v-Pfades in G entspricht

Page 15: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

h3

11

2

43

Vollständiger Graph:

h 31

1

2

2

3

6

4

36

minimaler Walk Länge: 14

minimaler H.K. Länge: 14

Page 16: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Heute

Arora, Grigni, Karger, Klein, Woloszyn (1998):

PTAS für TSP in gewichteten planaren Graphen.

Erweiterung:

Klein (2006):

PTAS für TSP in gewichteten planaren Graphen für vorgegebene Teilmenge S der Knotenmenge.

Page 17: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

PTAS für TSP in planaren Graphen

Grundlegende Konzepte für den Beweis:

• Spanner

• Separator

• Dynamische Programmierung

Page 18: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Ein r-Spanner von G ist ein Subgraph G` mit

Spanner

Gegeben: G=(V,E), w: E → N

Bemerkungen:• G ist ein 1-Spanner • gesucht werden Spanner G‘ mit w(G‘) « w(G)

Page 19: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Spanner

Althöfer, Das, Dopkin, Joseph, Soares (1993):

Einfacher Algorithmus der einen r-Spanner G´ berechnet, so dass

w(G‘) £ mst(G) · (1 + n/(r-1))

bzw.

w(G‘) £ mst(G) · (1 + 2/(r-1)), falls G planar.

Beachte: Für einen Spanner G´ gilt immer

w(G‘) ³ mst(G).

Page 20: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Algorithmus

Eingabe: G=(V,E), w:E→N,

Parameter r ε R+

Sortiere Kanten so, dass w(e1) £ … £ w(em);

E` := ? ;for i = 1 to m do

seien u und v die Knoten von ei;

if dG`(u,v) > r · w(ei) then

E` := E` + ei

Page 21: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Eigenschaften

Lemma 1: G` ist ein r-Spanner.

Lemma 2: girth(G`) > r+1.

[G` enthält keinen Kreis auf £ r+1 Knoten.]

Lemma 3: Sei C ein Kreis in G`. Dann gilt:

w(C - e) > r · w(e) für alle Kanten e in C.

Lemma 4: G` enthält einen minimalen Spannbaum von G.

Page 22: Chromatische Zahl. Graphfärben Gegeben: Graph G=(V,E) Aufgabe: Färbe die Knoten mit möglichst wenigen Farben so, dass benachbarte Knoten jeweils unterschiedliche

Beweis des Satzes (für planare Graphen)

G‘MST

P0 := Polygonzug um MSTT0 := ?

w(P0) = 2 · w(MST)w(T0) = 0

Für übrige Kanten: wähle sukzessive eine beliebige Kante ei, die mit Pi ein Gebiet einschliesst; Pi := Pi-1 – Pfadstück + ei; Ti := Ti-1 + ei;