¨Ubungen zur Vorlesung Approximationsalgorithmen

Rolf Wanka
Erlangen, 16. April 2015
¨
Ubungen
zur Vorlesung
Approximationsalgorithmen
SS 2015
Blatt 2
Die Aufgabe 5 k¨onnen Sie schon jetzt u¨ bers Wochenende bearbeiten, die Aufgaben 5 und 6 werden wir dann
am Dienstag besprechen (neben Aufgabe 3). Die beiden restlichen Aufgaben stehen dann f¨ur die Zeit bis
zum 28. April an. ,
AUFGABE 5:
Das Optimierungsproblem C LIQUE (vgl. Aufgaben 1 und 2 von Blatt 1) besteht darin, zu einem ungerichteten
Graphen G = (V, E) einen vollst¨andigen Teilgraphen von G gr¨oßtm¨oglicher Kardinalit¨at zu bestimmen. Die
Anzahl der Knoten dieses Teilgraphen bezeichnet man als Cliquenzahl. Diese wird traditionell mit ω(G)
angegeben. In unserer Schreibweise ist OPT(hGi) = ω(G).
F¨ur k ∈ IN ist die kte Potenz von G der Graph G(k) = (V (k) , E (k) ) mit
k Mal
V
(k)
E (k)
z }| {
= V × · · · ×V ,
= {(v1 , . . . , vk ), (w1 , . . . , wk )} | ∀i, 1 ≤ i ≤ k : vi = wi ∨ {vi , wi } ∈ E .
(a) Die Abbildung zeigt G (aus drei Knoten und einer Kante). Berechnen (d. h. zeichnen) Sie G(2) .
(b) Beweisen Sie: F¨ur jeden ungerichteten Graphen G gilt: ω(G(k) ) = (ω(G))k .
AUFGABE 6:
Betrachten Sie den Algorithmus G REEDY E DGE C OL, der ganz analog zu G REEDY C OL aus der Vorlesung
die Kanten des Eingabegraphen G auf greedy“ Art und Weise f¨arbt.
”
(a) Bestimmen Sie f¨ur G REEDY E DGE C OL eine m¨oglichst kleine absolute G¨utegarantie κ in Abh¨angigkeit
vom Grad ∆(G).
(b) Zeigen Sie, daß mit dem κ aus (a) der in der nachstehend gezeigte Graph ein κ-Zeuge gegen G REE DY E DGE C OL ist.
⋅⋅⋅
⋅⋅⋅
⋅⋅⋅
⋅⋅⋅
⋅⋅⋅
AUFGABE 7:
In der Vorlesung haben wir gesehen, daß der Algorithmus G REEDY C OL zum Eingabegraphen G = (V, E)
h¨ochstens ∆(G) + 1 Farben vergibt. Da ∆(G) = |E| sein kann, ist damit also eine (ziemlich schlechte, beinahe
triviale) allgemeine Schranke von G REEDY C OL(G) ≤ |E| + 1 gezeigt, wenn wir G REEDY C OL(G) in bloßer
Abh¨angigkeit von |E| angeben wollen.
Ziel dieser
p
Aufgabe ist es, eine in |E| bessere Schranke zu bestimmen, n¨amlich zu zeigen, daß gilt: G REEDY C OL(G) ≤
2|E|
Sei G = (V, E) ein beliebiger ungerichteter Graph mit m = |E| Kanten, der bereits von G REEDY C OL gef¨arbt
worden ist. Somit sind die Knoten aufgeteilt in die Farbklassen Ui = {u ∈ V | u bekam Farbe i}. Sei außerdem
f (m) die maximale Zahl der
√Farben,
die G REEDY C OL u¨ ber alle Graphen mit m Kanten vergibt. Unser Ziel
ist also zu zeigen: f (m) ≤
2m
Wir schauen jetzt auf die Knoten, die die Farbe 1 bekommen haben. Sei
k=
∑ degG (u)
.
u∈U1
Benutzen Sie bei der Argumentaion im folgenden auch den Graphen G0 = (V 0 , E 0 ), der u¨ brig bleibt, wenn
aus G die Knoten aus U1 und die zu ihnen inzidenten Kanten entfernt werden.
(a) Warum gilt die folgende Rekursion f¨ur f (hier geht die Arbeitsweise von G REEDY C OL ein)?
f (0) = 1
f (m) ≤
f (m − k) + 1
√
(b) Warum gilt m − k ≤ 12 · k · (k − 1) ? Zeigen Sie damit: 2k + 1 ≥ 2 2m
√ (c) Nutzen Sie dies alles, um induktiv zu zeigen: f (m) ≤
2m
√
√
Hinweis: Bei der Rechnung kann vermutlich 2m + 1 − 2 2m = ( 2m − 1)2 genutzt werden.
AUFGABE 8:
Das unter dem Namen S ET C OVER bekannte Problem der Mengen¨uberdeckung minimaler Kardinalit¨at kann
folgendermaßen beschrieben werden:
Gegeben sei eine endliche Menge V = {u1 , . . . , un } von Objekten und eine Sammlung S = {S1 , . . . , Sm } von
S
Teilmengen von V mit mj=1 S j = V . Gesucht ist eine m¨oglichst kleine Teilmenge Scov = {Si1 , . . . , Si` } von S
S
mit `j=1 Si j = V . In Abbildung 2 sehen Sie ein Beispiel.
Das Enscheidungsproblem, bei dem zu der Sammlung S noch eine Zahl k mitgegeben wird und bei dem die
Frage Gibt es eine Mengen¨uberdeckung der Kardinalit¨at k ?“ zu beantworten ist, ist NP-vollst¨andig.
”
S3
S5
S4
u1
u5
u9
u2
u6
u 10
S1
S2
u3
u7
u8
u4
u 11
u 12
S6
¨
Abbildung 1: Eine Instanz S von S ET C OVER. Scov = {S3 , S4 , S5 } ist eine minimale Uberdeckung.
Zeigen Sie durch Selbstreduktion, daß, falls P 6= NP ist, S ET C OVER nicht mit konstanter absoluter G¨utegarantie approximierbar ist.

Download Report