Upload
wilda-keilholtz
View
103
Download
0
Embed Size (px)
Citation preview
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 Farben erhalten.
Notation: Chromatische Zahl c(G) … minimale Anzahl Farben
Beispiele:
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.
Approximationsalgorithmen
Planare Graphen: Es gibt einen 4/3-Approximationalgorithmus – und
dies ist bestmöglich, ausser P=NP.
Allgemeine Graphen: ………..
3-färbbare Graphen: ………..
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)
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)
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.
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.
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]
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.
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.]
PTAS for TSP in weighted planar graphs
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.
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
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
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.
PTAS für TSP in planaren Graphen
Grundlegende Konzepte für den Beweis:
• Spanner
• Separator
• Dynamische Programmierung
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)
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).
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
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.
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;