480 lines
30 KiB
Plaintext
480 lines
30 KiB
Plaintext
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen, B. Schumacher, C. Wambsganz
|
||
|
||
09.06.2025
|
||
|
||
Präsenzaufgaben zur Vorlesung »Analyse von Algorithmen und
|
||
Komplexität«
|
||
Blatt 9
|
||
|
||
|
||
Definition 1 (Knapsack (Entscheidungsvariante)). Gegeben ist eine Menge mit n Gegenständen
|
||
mit Gewichten w1 , . . . , wn ∈ N≥0 und Profiten p1 , . . . , pn ∈ N≥0 . Weiter sind eine Kapazität
|
||
K ∈ N≥0 und ein Zielprofit P ∈ N≥0 gegeben. Bei dem KNAPSACK Problem muss entschieden
|
||
werden, ob eine Teilmenge S ⊆ [n] existiert, sodass
|
||
|
||
∑ wi ≤ K und ∑ pi ≥ P
|
||
i∈S i∈S
|
||
|
||
gilt.
|
||
|
||
Präsenzaufgabe 9.1 (KNAPSACK in NP)
|
||
Zeigen Sie KNAPSACK ∈ NP auf zwei verschiedene Wege.
|
||
1. Geben Sie einen nicht deterministischen Algorithmus an, der das Problem in polynomi-
|
||
eller Zeit löst.
|
||
2. Geben Sie einen polynomiellen Verifizierer für das Problem an.
|
||
Wie hängen diese beiden Methoden zusammen?
|
||
|
||
Lösung. 1. Der Algorithmus arbeitet wie folgt: Für jeden Gegenstand entscheiden wir nicht-
|
||
deterministisch, ob er in den Rucksack soll. Anschließend akzeptieren wir, falls die Kapazitäts-
|
||
und Profitbedingung erfüllt sind.
|
||
Existiert eine valide Rucksackfüllung mit genügend Profit, dann gibt es auch eine Reihe
|
||
von nichtdeterministischen Entscheidungen, die diese Füllung findet. Diese wird dann
|
||
auch vom Algorithmus akzeptiert.
|
||
Der Algorithmus macht polynomiell viele nichtdeterministische Entscheidungen und die
|
||
Überprüfung der Eigenschaften ist ebenfalls in Polynomialzeit möglich, also ist dies ein
|
||
polynomieller, nichtdeterministischer Algorithmus, der KNAPSACK löst.
|
||
2. Unser Zertifikat ist eine Teilmenge S ⊆ [n], die die Auswahl für den Rucksack darstellen
|
||
soll. Dies kann zum Beispiel über ein Bit pro Gegenstand realisiert werden. Um dieses
|
||
Zertifikat zu verifizieren, berechnen wir ∑i∈S wi und ∑i∈S pi und vergleichen die Werte
|
||
mit K und P und akzeptieren entsprechend.
|
||
Existiert eine valide Rucksackfüllung mit genügend Profit, dann gibt es auch ein Zertifi-
|
||
kat, das diese Füllung beschreibt. Dieses wird dann auch vom Verifizierer akzeptiert.
|
||
Das Ausrechnen der Summen und das Überprüfen ist in polynomieller Zeit möglich, also
|
||
ist dies ein polynomieller Verifizierer.
|
||
In beiden Wegen wird die extra Ressource, die wir zur Verfügung haben, genutzt, um eine
|
||
Teilmenge (einen möglichen Rucksack) zu bestimmen und zu überprüfen. In der Vorlesung
|
||
wird noch genau gezeigt, dass diese beiden Wege tatsächlich äquivalent sind.
|
||
|
||
Präsenzaufgabe 9.2 (Transitivität von Polynomialzeitreduktionen)
|
||
Zeigen Sie, dass Polynomialzeitreduktionen transitiv sind, d.h., dass für alle Entscheidungspro-
|
||
bleme L1 , L2 , L3 ⊆ Σ∗ gilt, dass
|
||
|
||
L1 ⪯ L2 ∧ L2 ⪯ L3 =⇒ L1 ⪯ L3 .
|
||
|
||
Lösung. Seien L1 , L2 , L3 Sprachen. Zudem sei R1 ein Algorithmus, der L1 nach L2 in O(na )
|
||
reduziert, und R2 ein Algorithmus, der L2 nach L3 in O(nb ) reduziert.
|
||
Sei x eine Instanz von L1 der Größe n. Dann benötigt der Aufruf von R1 auf x höchstens O(na )
|
||
Zeit.
|
||
Sei x′ die Ausgabe von R1 . Dann hat x′ eine Größe von höchstens O(na ). Diese Schranke für
|
||
die Ausgabe ergibt sich aus der Laufzeit der Reduktion. Der Aufruf von R2 auf x′ benötigt nun
|
||
höchstens O((na )b ) = O(nab ) Zeit. Damit ist die Reduktion von L1 auf L3 in polynomieller Zeit
|
||
möglich.
|
||
Die Korrektheit ergibt sich aus der Transitivität der Äquivalenz: Sei x′′ die Ausgabe von R2 auf
|
||
x′ , dann gilt
|
||
x ∈ L1 ⇐⇒ x′ ∈ L2 und x′ ∈ L2 ⇐⇒ x′′ ∈ L3 ,
|
||
also auch x ∈ L1 ⇐⇒ x′′ ∈ L3 .
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen, B. Schumacher, C. Wambsganz
|
||
|
||
16.06.2025
|
||
|
||
Präsenzaufgaben zur Vorlesung »Analyse von Algorithmen und
|
||
Komplexität«
|
||
Blatt 10
|
||
|
||
|
||
Präsenzaufgabe 10.1 (Fragen über Fragen)
|
||
Diskutieren Sie die folgenden Aussagen (Gelten sie allgemein? Gelten sie nicht? Gelten sie
|
||
unter bestimmten Bedingungen? Welche?):
|
||
(i) Für jede Sprache, die von einer NDTM in polynomieller Zeit akzeptiert werden kann,
|
||
existiert eine DTM, die ebenfalls die Sprache in polynomieller Zeit akzeptiert.
|
||
(ii) A ist NP-schwer =⇒ A ∈ P
|
||
|
||
Lösung. (i) Die Aussage gilt nur, wenn P = NP. Dann liegen alle Probleme in NP (von
|
||
NDTM in polynomieller Zeit lösbar) auch in P (von DTM in polynomieller Zeit lösbar).
|
||
Falls P ̸= NP, dann nein, weil sonst folgender Widerspruch auftritt: ein Problem in NP \ P
|
||
ist von einer NDTM, nicht aber von einer DTM in polynomieller Zeit lösbar. Könnte eine
|
||
DTM die NDTM in polynomieller Zeit simulieren, wäre das Problem auch in P.
|
||
(ii) Falsch. Es gibt NP-schwere Probleme, die nicht in NP liegen, z.B. das HALTE-Problem.
|
||
Diese liegen folglich auch definitiv nicht in P. NP-schwer ist eine untere Schranke, ∈ NP
|
||
eine obere, und wenn beide erfüllt sind, ist ein Problem NP-vollständig.
|
||
|
||
|
||
|
||
Definition 1 (Vertex Cover (VC)). Für einen (ungerichteten) Graphen G = (V, E) ist ein Vertex
|
||
Cover eine Menge von Knoten C ⊆ V , sodass u ∈ C oder v ∈ C für alle { u, v } ∈ E gilt, also ist
|
||
für alle Kanten mindestens ein Endpunkt in C.
|
||
Für das VERTEX COVER Problem ist neben einem Graphen G eine Zahl k ∈ N≥0 gegeben und
|
||
es wird gefragt, ob ein Vertex Cover mit Größe (Anzahl der Knoten) höchstens k in G existiert.
|
||
|
||
Präsenzaufgabe 10.2 (VERTEX COVER ist NP-vollständig)
|
||
Zeigen Sie, dass VERTEX COVER NP-vollständig ist.
|
||
Hinweis: Reduzieren Sie CLIQUE auf VERTEX COVER.
|
||
|
||
Lösung. VERTEX COVER ∈ NP ist bekannt aus der letzten Hausaufgabe.
|
||
Vorüberlegung zur Reduktion von CLIQUE auf VERTEX COVER: Sei eine Instanz mit G =
|
||
(V, E) und k ∈ N≥0 von CLIQUE gegeben. Wir invertieren zunächst den Graphen G und erhal-
|
||
ten damit G′ . Nun enthält G′ genau dann eine unabhängige Menge der Größe ℓ, wenn G eine
|
||
Clique der Größe ℓ enthält. Wenn ein Graph mit n Knoten eine unabhängige Menge mit min-
|
||
destens k Knoten hat, dann hat der Graph auch ein Vertex Cover mit maximal n − k Knoten
|
||
(das Komplement zur unabhängigen Menge). Unsere Instanz für VERTEX COVER ist also G′
|
||
und n − k. (k ≤ n können wir annehmen)
|
||
Betrachte nun folgende Reduktion:
|
||
Sei eine Instanz mit G = (V, E) und k ∈ N≥0 von CLIQUE gegeben. Invertiere den Graphen G
|
||
und erhalte damit G′ . Gebe nun G′ und n − k als Instanz von VERTEX COVER zurück.
|
||
Korrektheit:
|
||
⇒ (Falls (G, k) eine Ja-Instanz von CLIQUE ist, dann ist (G′ , n − k) eine Ja-Instanz von VER -
|
||
TEX COVER .):
|
||
|
||
G enthalte eine Clique C der Größe ≥ k. Dann ist V ′ := V \C ein Vertex Cover von G′ der Größe
|
||
≤ n − k. Da |C| ≥ k, gilt |V ′ | ≤ n − k. Da C eine Clique ist, also alle Knoten aus C mit allen
|
||
anderen Knoten aus C verbunden sind, gibt es im invertierten Graphen G′ keine Kante zwischen
|
||
Knoten aus C. Also gilt für jede Kante {u, v} ∈ E ′ , dass u ∈ / C und somit u ∈ V ′ oder
|
||
/ C oder v ∈
|
||
v ∈ V ′.
|
||
⇐ (Falls (G′ , n − k) eine Ja-Instanz von VERTEX COVER ist, dann ist (G, k) eine Ja-Instanz von
|
||
CLIQUE.):
|
||
G′ enthalte ein Vertex Cover V ′ der Größe ≤ n−k. Dann ist C := V \V ′ eine Clique der Größe ≥
|
||
k in G. Da |V ′ | ≤ n − k, gilt |C| ≥ k. Für jede Menge {u, v} ⊆ C gilt, dass {u, v} ∈
|
||
/ E ′ . Ansonsten
|
||
wäre V ′ kein korrektes Vertex Cover. Da G′ der invertierte Graph von G ist, gilt somit {u, v} ∈ E
|
||
für jede Menge {u, v} ⊆ C.
|
||
Laufzeit: Das Invertieren des Graphen kann naiv in O(|V |2 · |E|) Zeit, also in polynomieller
|
||
Zeit, erledigt werden.
|
||
Also existiert eine polynomielle Reduktion von CLIQUE auf VERTEX COVER. Da CLIQUE
|
||
NP-vollständig ist und VERTEX COVER ∈ NP gilt, ist somit VERTEX COVER NP-vollständig.
|
||
|
||
|
||
Präsenzaufgabe 10.3 (Turingmaschinen)
|
||
n
|
||
Entwerfen Sie eine Turingmaschine für die Sprache L = { 02 | n ∈ N } über dem Alphabet
|
||
Σ = {0} und geben Sie die Laufzeit Ihrer Turingmaschine an. Begründen Sie die Korrektheit
|
||
und die Laufzeit Ihrer Turingmaschine. Diskutieren Sie die Laufzeit Ihrer Turingmaschine im
|
||
Vergleich zu einem Algorithmus (mit RAM) für diese Sprache.
|
||
|
||
Lösung. Die Turingmaschine sieht folgendermaßen aus:
|
||
(1) Falls genau eine 0 auf dem Band steht, akzeptiere.
|
||
(2) Bewege den Kopf von links nach rechts über die Eingabe und ersetze jede zweite 0 durch
|
||
ein neues Symbol x.
|
||
(3) Falls das letzte Symbol der Eingabe nun eine 0 ist, verwerfe.
|
||
(4) Gehe zu Schritt (1).
|
||
Korrektheit: Die Sprache L besteht aus allen Wörtern, die nur Nullen enthalten und deren Länge
|
||
eine Zweierpotenz ist. Eine Zahl ist genau dann eine Zweierpotenz, wenn sie nach wiederholtem
|
||
Teilen durch 2 irgendwann eine 1 ergibt. Genau das überprüft die Turingmaschine. Wenn bei
|
||
diesem wiederholten Teilen eine ungerade Zahl auftritt, ist die Zahl keine Zweierpotenz. In
|
||
diesem Fall verwirft die Turingmaschine die Eingabe (siehe Schritt (3)).
|
||
Laufzeit: Die angegebene Turingmaschine hat eine Laufzeit von O(n log(n)), wobei n hier die
|
||
Länge der Eingabe bezeichnet. Schritt (1) und Schritt (2) benötigen jeweils eine Laufzeit von
|
||
O(n). Schritt (3) geht in konstanter Laufzeit O(1). Schritt (4) wiederholt die Schritte (1) bis (3)
|
||
bis nur noch eine 0 auf dem Band steht oder vorher abgebrochen wird. Da in jedem Durchlauf
|
||
der Schritte (1) bis (3) die Hälfte der Nullen (abgerundet) durch x Symbole ersetzt wird, steht
|
||
nach log n Durchläufen nur noch eine Null auf dem Band und es wird nach Schritt (1) akzeptiert
|
||
oder es steht nach ⌊log n⌋ − 1 Durchläufen eine ungerade Anzahl von Nullen auf dem Band und
|
||
es wird nach Schritt (3) verworfen. Also gibt es maximal log n + 1 Durchläufe.
|
||
Diskussion: Ein Algorithmus mit RAM könnte folgendermaßen aussehen:
|
||
1. Zähle die Buchstaben und erhalte Anzahl m.
|
||
2. Falls log m ganzzahlig ist, akzeptiere. Sonst verwerfe.
|
||
Dieser Algorithmus hat eine Laufzeit von O(n), wobei n hier die Länge der Eingabe bezeichnet.
|
||
Ein Algorithmus mit RAM kann also den zusätzlichen Speicher nutzen, um wesentlich schneller
|
||
eine Aufgabe zu erledigen, im Vergleich zu einem Algorithmus, der auf einer Turingmaschine
|
||
läuft.
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen, B. Schumacher, C. Wambsganz
|
||
|
||
23.06.2025
|
||
|
||
Präsenzaufgaben zur Vorlesung »Analyse von Algorithmen und
|
||
Komplexität«
|
||
Blatt 11
|
||
|
||
|
||
Präsenzaufgabe 11.1 (Fragen über Fragen)
|
||
Diskutieren Sie nachfolgende Aussagen. Sind diese wahr oder falsch?
|
||
(a) Für L ∈ NP gilt, aus L ⪯ 3-SAT folgt, dass L NP-vollständig ist.
|
||
(b) Gilt für eine Sprache L, dass sowohl L ⪯ 3-SAT als auch 3-SAT ⪯ L, dann ist L NP-vollständig.
|
||
(c) Sei L NP-vollständig. Dann gilt L ∈ P genau dann, wenn P = NP.
|
||
(d) Es ist möglich, dass 3-SAT ∈ P und CLIQUE ∈
|
||
/ P.
|
||
|
||
Lösung.
|
||
/ Offensichtlich gilt L ∈ NP. Aus L ⪯ 3-SAT folgt nur,
|
||
(a) Nein, ein Gegenbeispiel ist L = 0.
|
||
dass sich L auf 3-SAT reduzieren lässt, nicht anders herum.
|
||
(b) Das ist die Definition von NP-vollständig.
|
||
(c) Korrekt, da sich jedes Problem auf L reduzieren lässt nach Def. NP-vollständig (und offen-
|
||
sichtlich P ⊆ NP).
|
||
(d) Nein, weil 3-SAT NP-vollständig ist, lässt sich CLIQUE (liegt bekannterweise in NP, ist
|
||
sogar NP-vollständig) auf 3-SAT reduzieren.
|
||
|
||
|
||
|
||
Präsenzaufgabe 11.2 (NP-Vollständigkeit)
|
||
In dem Problem CLIQUE -NOMEMBER ist ein Graph G = (V, E), ein Knoten v ∈ V sowie eine
|
||
Zahl k ∈ N gegeben und es soll entschieden werden, ob es eine Clique mit k Knoten gibt, die
|
||
den Knoten v nicht enthält.
|
||
Zeigen Sie, dass CLIQUE -NOMEMBER NP-vollständig ist, indem Sie eine Reduktion von CLI -
|
||
QUE auf CLIQUE -NOMEMBER angeben. Sie können davon ausgehen, dass CLIQUE -NOMEMBER ∈
|
||
NP ist.
|
||
|
||
Lösung. Clique-Nomember ist NP-schwer:
|
||
Sei (G = (V, E), k) eine Eingabe für das Clique Problem.
|
||
Idee: Füge einen neuen isolierten Knoten v zu G hinzu.
|
||
Wir geben zuerst die Abbildung an: Sei v ̸∈ V . Wir definieren die Eingabe für das Problem
|
||
CLIQUE -NOMEMBER als den Graphen G′ := (V ∪ {v}, E), den Knoten v als Knoten, der nicht
|
||
benutzt werden darf, und k als gesuchte Cliquengröße. (G′ , v, k) ist eine gültige Eingabe für
|
||
CLIQUE -NOMEMBER und in polynomieller Zeit berechenbar.
|
||
Wir zeigen nun: G hat eine k-Clique genau dann, wenn G′ eine k-Clique ohne v beinhaltet.
|
||
⇒:
|
||
Sei (G, k) eine Ja-Instanz des CLIQUE Problems. Dann enthält G eine k-Clique C. Dann ist C
|
||
auch eine k-Clique in G′ , da bei der Abbildung keine Kanten entfernt wurden. Da v ̸∈ V , enthält
|
||
C den Knoten v nicht. Damit ist C eine k-Clique in G ohne den Knoten v. (G′ , v, k) ist also eine
|
||
Ja-Instanz des CLIQUE -NOMEMBER Problems.
|
||
⇐:
|
||
Sei (G′ , v, k) eine Ja-Instanz des CLIQUE -NOMEMBER Problems. Dann enthält G′ eine k-Clique
|
||
C mit v ̸∈ C. Da bei der Abbildung an dem Graphen nichts geändert wurde, außer der Knoten v
|
||
hinzugefügt, muss C auch eine k-Clique in G sein. Damit ist (G, k) eine Ja-Instanz des CLIQUE
|
||
Problems.
|
||
Also existiert eine polynomielle Reduktion von CLIQUE auf CLIQUE -NOMEMBER. Da CLI -
|
||
QUE NP-vollständig ist und CLIQUE -NOMEMBER ∈ NP nach Aufgabenstellung gilt, ist somit
|
||
CLIQUE -NOMEMBER NP-vollständig.
|
||
|
||
|
||
|
||
Präsenzaufgabe 11.3 (NP-Vollständigkeit)
|
||
Für das Problem SUBSET SUM CARDINALITY seien n ganze Zahlen c1 , . . . , cn ∈ N>0 (wobei n
|
||
gerade sei) sowie eine Zahl K ∈ N gegeben. Es soll entschieden werden, ob es eine Teilmenge
|
||
S ⊂ {1, . . . , n} gibt mit |S| = n/2 und ∑i∈S ci = K.
|
||
Zeigen Sie, dass das Problem SUBSET SUM CARDINALITY NP-vollständig ist. Sie können
|
||
davon ausgehen, dass SUBSET SUM CARDINALITY ∈ NP ist.
|
||
|
||
Lösung. Subset Sum Cardinality ist NP-schwer:
|
||
SUBSET SUM Problem: Gegeben: n ganze Zahlen c1 , . . . , cn ∈ N>0 und Zahl K ∈ N. Frage: Gibt
|
||
es eine Teilmenge S ⊆ {0, . . . , n} mit ∑i∈S ci = K?
|
||
Reduktion: Sei I = (c1 , . . . , cn , K) eine Eingabe für das SUBSET SUM Problem. Definiere c′i :=
|
||
ci + 1 für i ≤ n und c′i := 1 für i ∈ {n + 1, . . . , 2n}. Wir definieren die Eingabe für das Problem
|
||
SUBSET SUM CARDINALITY als I ′ = (c′1 , . . . , c′2n , K + n).
|
||
Wir zeigen nun: Es gibt eine Lösung für I genau dann, wenn es eine Lösung für I ′ gibt.
|
||
⇒:
|
||
Sei I eine Ja-Instanz des SUBSET SUM Problems. Dann gibt es eine Menge S ⊆ {1, . . . , n} mit
|
||
∑i∈S ci = K. Es gilt also ∑i∈S c′i = ∑i∈S (ci + 1) = K + |S|. Sei nun S′ = {n + 1, . . . , 2n − |S|}. Es
|
||
gilt |S ∪ S′ | = n und ∑i∈S∪S′ c′i = ∑i∈S c′i + ∑i∈S′ c′i = ∑i∈S (ci + 1) + ∑i∈S′ 1 = K + |S| + (n − |S|) =
|
||
K + n. S ∪ S′ ist also eine Lösung für I ′ und I ′ damit eine Ja-Instanz.
|
||
⇐:
|
||
Es sei I ′ eine Ja-Instanz. Dann gibt es also eine Menge S′ ⊆ {1, . . . , 2n} mit ∑i∈S′ c′i = K + n und
|
||
|S′ | = n. Sei S := S′ ∩{1, . . . , n}. Es gilt ∑i∈S′ c′i − ∑i∈S c′i = n−|S|, da die Items in {n+1, . . . , 2n}
|
||
das Gewicht 1 haben, und genau n − |S| Items übrig sind. Damit gilt ∑i∈S (ci + 1) = ∑i∈S c′i =
|
||
K + n − (n − |S|) = K + |S|, woraus folgt, dass ∑i∈S ci = K. Damit ist S eine Lösung für I und
|
||
somit I eine Ja-Instanz.
|
||
Laufzeit: Die Reduktion kann naiv in einer Zeit von O(n) implementiert werden. Das ist eine
|
||
polynomielle Laufzeit.
|
||
Also existiert eine polynomielle Reduktion von SUBSET SUM auf SUBSET SUM CARDINALI -
|
||
TY . Da nach Skript SUBSET SUM NP-vollständig ist und SUBSET SUM CARDINALITY ∈ NP
|
||
nach Aufgabenstellung gilt, ist somit SUBSET SUM CARDINALITY NP-vollständig.
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen, B. Schumacher, C. Wambsganz
|
||
|
||
30.06.2025
|
||
|
||
Präsenzaufgaben zur Vorlesung »Analyse von Algorithmen und
|
||
Komplexität«
|
||
Blatt 12
|
||
|
||
|
||
Präsenzaufgabe 12.1
|
||
Im Folgenden sollen Sie herausfinden (und begründen), welche Lower Bounds sich über ETH
|
||
und die Reduktionen aus der Vorlesung ergeben. Nutzen Sie hierfür auch das Sparsification
|
||
Lemma.
|
||
Welche Schranken für die Laufzeit in Abhängigkeit von den natürlichen Parametern (Anzahl
|
||
Knoten, Anzahl Kanten, Anzahl Items, Anzahl unterschiedlicher Items, Anzahl Tripel, Kardi-
|
||
nalität der Grundmenge, Anzahl unterschiedlicher Tripel, Anzahl unterschiedlicher auftretender
|
||
Zahlen, größte auftretende Zahl, . . . ) ergeben sich jeweils aus folgenden (zum Großteil aus der
|
||
Vorlesung bekannten) Reduktionen (Laufzeitfaktoren, die polynomiell in der Eingabekodierung
|
||
sind, dürfen vernachlässigt werden)?
|
||
Schätzen Sie dazu zunächst die verschiedenen Parameter der resultierenden Instanz mithilfe der
|
||
Parameter der eingegebenen Instanz geeignet ab.
|
||
1. 3-SAT ⪯ k-CLIQUE
|
||
2. k-CLIQUE ⪯ k-INDEPENDENT SET (Problemdefinition für die Antwort nicht relevant; in
|
||
der Reduktion wird der Graph G = (V, E) auf den Komplementgraph (V, E) abgebildet)
|
||
3. SAT ⪯ 3-DIMENSIONAL MATCHING (Hinweis: 3-SAT ⊆ SAT)
|
||
4. 3-DIMENSIONAL MATCHING ⪯ 3-EXACT COVER
|
||
5. 3-EXACT COVER ⪯ SUBSET SUM
|
||
|
||
Lösung. Angenommen ETH gilt. Das Sparsification Lemma impliziert, dass man 3-SAT nicht
|
||
in 2o(m) · |I|O(1) lösen kann.
|
||
|
||
1. In der Reduktion werden |V | = O(m) Knoten und |E| = O(m2 ) Kanten erstellt und k = m.
|
||
Außerdem gilt n ≤ 3m ∈ O(m).
|
||
• Lower bound bzgl. der Anzahl an Knoten: 2o(|V |) · |I|O(1)
|
||
Angenommen, es existiert ein Algorithmus, der k-Clique in 2o(|V |) ·|I|O(1) löst. Dann
|
||
gibt es auch einen Algorithmus, der 3-SAT in 2o(m) · |I|O(1) löst (Reduktion auf k-
|
||
Clique + k-Cliquen Algorithmus). Nach dem Sparsification Lemma gibt es dies nur,
|
||
wenn die ETH nicht gilt.
|
||
√
|
||
• Lower bound bzgl. der Anzahl an Kanten: 2o( |E|) · |I|O(1) √
|
||
Angenommen, es existiert ein Algorithmus, der k-Clique in 2o( |E|) · |I|O(1) löst.
|
||
Da |E| ∈ O(m2 ), gibt es dann auch einen Algorithmus, der 3-SAT in 2o(m) · |I|O(1)
|
||
löst (Reduktion auf k-Clique + k-Cliquen Algorithmus). Nach dem Sparsification
|
||
Lemma gibt es dies nur, wenn die ETH nicht gilt.
|
||
• Lower bound bzgl. k: 2o(k) · |I|O(1)
|
||
Angenommen, es existiert ein Algorithmus, der k-Clique in 2o(k) · |I|O(1) löst. Dann
|
||
gibt es auch einen Algorithmus, der 3-SAT in 2o(m) · |I|O(1) löst (Reduktion auf k-
|
||
Clique + k-Cliquen Algorithmus). Nach dem Sparsification Lemma gibt es dies nur,
|
||
wenn die ETH nicht gilt.
|
||
2. In der Reduktion werden genau |V | Knoten und maximal |E| = O(|V |2 ) Kanten erstellt.
|
||
• Lower bound bzgl. der Anzahl an Knoten: 2o(|V |) · |I|O(1)
|
||
Angenommen, es existiert ein Algorithmus, der k-Independent-Set in 2o(|V |) · |I|O(1)
|
||
löst. Dann gibt es auch einen Algorithmus, der k-Clique in 2o(|V |) · |I|O(1) löst (Re-
|
||
duktion auf k-Independent-Set + k-Independent-Set Algorithmus). Nach Aufgaben-
|
||
teil 1, gibt es diesen nur, wenn die ETH nicht gilt.
|
||
√
|
||
o( |E|)
|
||
• Lower bound bzgl. der Anzahl an Kanten: 2 · |I|O(1) √
|
||
Angenommen, es existiert ein Algorithmus, der k-Independen-Set in 2o( |E|) ·|I|O(1)
|
||
löst. Da |E| ≤ |V |2 , gibt es dann auch einen Algorithmus, der k-Clique in 2o(|V |) ·
|
||
|I|O(1) löst (Reduktion auf k-Independent-Set + k-Independent-Set Algorithmus).
|
||
Nach Aufgabenteil 1, gibt es diesen nur, wenn die ETH nicht gilt.
|
||
3. In der Reduktion werden Mengen mit |U| = |V | = |W | = O(mn) Elementen erstellt und
|
||
|T | = O(m2 n2 ) Tupel. Es gilt n ≤ 3m ∈ O(m) für 3-SAT.
|
||
√
|
||
• Lower bound bzgl. der Anzahl an Elementen: 2o( |V |) · |I|O(1) √
|
||
Angenommen, es existiert ein Algorithmus, der 3-Dimensional-Matching in 2o( |V |) ·
|
||
|I|O(1) löst. Da |V | ∈ O(mn) ≤ O(m2 ), gibt es dann auch einen Algorithmus, der
|
||
3-SAT in 2o(m) · |I|O(1) löst (Reduktion von SAT auf 3-Dimensional-Matching an-
|
||
gewandt auf 3-SAT Instanzen + 3-Dimensional-Matching Algorithmus). Nach dem
|
||
Sparsification Lemma geht dies nur, wenn die ETH nicht gilt.
|
||
√
|
||
4
|
||
• Lower bound bzgl. der Kardinalität von T : 2o( |T |) · |I|O(1) √
|
||
4
|
||
Angenommen, es existiert ein Algorithmus, der 3-Dimensional-Matching in 2o( |T |) ·
|
||
|I|O(1) löst. Da |T | ∈ O(m2 n2 ) ≤ O(m4 ), gibt es dann auch einen Algorithmus, der
|
||
3-SAT in 2o(m) · |I|O(1) löst (Reduktion von SAT auf 3-Dimensional-Matching an-
|
||
gewandt auf 3-SAT Instanzen + 3-Dimensional-Matching Algorithmus). Nach dem
|
||
Sparsification Lemma geht dies nur, wenn die ETH nicht gilt.
|
||
4. Das 3-dimensionale Matching ist ein Spezialfall vom 3-Exact Cover. Daher gelten die
|
||
Lower Bounds von 3-dimensionalem Matching auch für 3-Exact Cover. Da |U| = 3m ∈
|
||
O(|V |), ergibt sich, dass es für 3-Exact Cover unter der ETH keinen Algorithmus √ mit
|
||
√
|
||
o( m) O(1) o( |V |)
|
||
Laufzeit 2 · |I| geben kann, da sonst 3-dimensionales Matching in 2 ·
|
||
|I|O(1) lösbar wäre. Und da |F| = |T |, √ ergibt sich, dass es für 3-Exact Cover unter der ETH
|
||
o( 4 |F|)
|
||
keinen Algorithmus
|
||
√ mit Laufzeit 2 · |I|O(1) geben kann, da sonst 3-dimensionales
|
||
4
|
||
Matching in 2o( |T |) · |I|O(1) lösbar wäre.
|
||
√
|
||
4
|
||
5. In der Reduktion wird n = |F| gesetzt. Lower bound bzgl. n: 2o( n)√· |I|O(1)
|
||
4
|
||
Angenommen, es existiert ein Algorithmus, der SubsetSum in 2o( n) · |I|O(1) löst. Dann
|
||
√
|
||
4
|
||
|F|)
|
||
gibt es auch einen Algorithmus, der 3-Exact Cover in 2o( · |I|O(1) löst. Nach Aufga-
|
||
benteil 4, gibt es diesen nur, wenn die ETH nicht gilt.
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen, B. Schumacher, C. Wambsganz
|
||
|
||
07.07.2025
|
||
|
||
Präsenzaufgaben zur Vorlesung »Analyse von Algorithmen und
|
||
Komplexität«
|
||
Blatt 13
|
||
|
||
|
||
Präsenzaufgabe 13.1 (Vertex Cover)
|
||
Ein Vertex Cover in einem Graphen G = (V, E) ist eine Menge von Knoten C ⊆ V , so dass für
|
||
jede Kante {v, w} ∈ E gilt, dass v ∈ C oder w ∈ C. Beim Optimierungsproblem Minimum Vertex
|
||
Cover soll die kardinalitätskleinste Menge C ⊆ V gefunden werden, die ein Vertex Cover von
|
||
G ist.
|
||
Gegeben ist der folgende approximative Algorithmus mit Güte 2 für VertexCover:
|
||
Idee: Wähle eine beliebige Kante. Wenn einer der beiden Endknoten bereits in C ist, verwirf
|
||
diese Kante. Sonst, füge beide Endknoten zur Menge C hinzu. Mache dies für jede Kante.
|
||
|
||
Algorithmus 2APPROX CV(G = (V, E))
|
||
|
||
1 C = {}
|
||
2 foreach {u, v} ∈ E do
|
||
3 if u ̸∈ C and v ̸∈ C then
|
||
4 C = C ∪ {u, v}
|
||
5 fi
|
||
6 od
|
||
7 return C
|
||
|
||
Beweisen Sie die Güte.
|
||
|
||
Lösung. Beweis: Sei C∗ ein minimales Vertex Cover. Wir zeigen |C| ≤ 2|C∗ |.
|
||
Sei A die Menge der Kanten, für die beide Endknoten zu C hinzugefügt wurden. Es gilt |C| =
|
||
2|A|, da beide Knoten jeder ausgewählten Kante zu C hinzugefügt wurden und alle anderen
|
||
Kanten nicht weiter betrachtet werden. Damit folgt auch, dass keine zwei Kanten aus A einen
|
||
Knoten gemeinsam haben können. Sei nun C∗ ein minimales Vertex Cover. C∗ enthält nach
|
||
Definition mindestens einen Knoten jeder Kante, also insbesondere einen Knoten jeder Kante
|
||
aus A. Da keine zwei Kanten aus A vom gleichen Knoten aus C∗ überdeckt werden können, gilt
|
||
|C∗ | ≥ |A|. Es folgt |C| = 2|A| ≤ 2|C∗ |. Die Lösung C von 2ApproxCV ist also maximal doppelt
|
||
so groß wie die optimale Lösung C∗ . Damit berechnet der Algorithmus eine 2-Approximation.
|
||
Präsenzaufgabe 13.2 (TSP)
|
||
In der Vorlesung haben Sie zwei approximative Algorithmen für das TSP-Problem kennen ge-
|
||
lernt. Der erste Algorithmus ∆TSP1 hat eine Approximationsrate von 2, während der zweite
|
||
Algorithmus ∆TSP2 von Christofides eine Approximationsrate von 3/2 besitzt. In dieser Übung
|
||
soll gezeigt werden, dass die zweite Rate scharf ist. D.h., dass es eine Folge von Instanzen gibt,
|
||
auf denen der Algorithmus immer näher an diese Rate heran kommt.
|
||
Wir betrachten den vollständigen Graphen Kn = (V, E) für ein n ∈ N≥6 mit n mod 4 = 2 und
|
||
die nachfolgende Gewichtsfunktion d2 : E → R+ . Zeigen Sie, dass
|
||
(a) OPT((Kn , d2 )) = n gilt und
|
||
(b) eine mögliche Ausführung von ∆TSP2 existiert, die auf Eingabe (Kn , d2 ) eine Tour der
|
||
Länge (n − 1) + n/2 berechnet.
|
||
|
||
|
||
1 1 1 1
|
||
1 3 5 7 9 n−1
|
||
|
||
|
||
1 1 1 1 1 1
|
||
|
||
1 1 1 1
|
||
2 4 6 8 10 n
|
||
|
||
|
||
|
||
Wir definieren E2 := {{i, i + 2}|i ∈ {1, . . . , n − 2}} ∪ {{2i + 1, 2i + 2}|i ∈ {0, . . . , n/2 − 1}} und
|
||
d2 , so dass alle Kanten aus E2 auf 1 abgebildet werden und alle Kanten aus E \ E2 auf den Wert
|
||
des kürzesten Wegs zwischen diesen Knoten in dem oben abgebildeten Graphen abgebildet
|
||
werden.
|
||
|
||
Lösung. Wichtig bei dieser Aufgabe ist der folgende Fakt: Bei beiden Algorithmen wird ir-
|
||
gendein MST genommen und dann irgendeine Reihenfolge der Knoten. Typischerweise wird
|
||
diese Reihenfolge durch bestimmte Knoten- oder Kanten-Labels festgelegt (wird zum Beispiel
|
||
der Kruskal-Algorithmus zur Konstruktion des MST genutzt, so werden dort die Kanten nach
|
||
Gewicht sortiert. Kanten gleichen Gewichts müssen also auch noch durch irgendeine Reihen-
|
||
folge festgelegt werden.) Wir gehen also davon aus, dass wir diese Reihenfolge auch wählen
|
||
können. Sollte der Algorithmus also einen “besseren” MST oder eine “bessere” Knotenreihen-
|
||
folge nutzen, passen wir die Labels dementsprechend an.
|
||
Ein möglicher MST ist durch die unten angegebene Zick-Zack-Tour gegeben oder formal durch
|
||
h [ i
|
||
ET = {{ j, j + 1}, { j + 1, j + 3}, { j + 3, j + 2}, { j + 2, j + 4}}} ∪ {{n − 1, n}}.
|
||
1≤ j≤n−5
|
||
j mod 4=1
|
||
|
||
|
||
1 1 1 1
|
||
1 3 5 7 n−3 n−1
|
||
|
||
|
||
1 1 1 1 1 1
|
||
|
||
1 1 1 1
|
||
2 4 6 8 n−2 n
|
||
Es gilt d(T ) = n − 1 für die Kosten d(T ) des MST T , da nur Kanten mit Kosten 1 gewählt
|
||
werden und n − 1 Kanten gewählt werden müssen, um den Zusammenhang sicher zu stellen.
|
||
Da jeder Knoten im MST außer 1 und n geraden Grad hat, ist das Matching K sehr simpel,
|
||
nämlich K = {{1, n}}. Die Kosten der Kante {1, n} sind n/2 (der kürzeste Pfad von 1 zu n)
|
||
und somit gilt d(K) = n/2 für die Kosten von K. Die Rundreise R entspricht einfach dem MST
|
||
vereinigt mit der Matchingkante und hat somit Kosten: d(R) = n − 1 + n/2.
|
||
Die optimale Tour würde erst “oben” und dann “unten” entlang laufen, also von Knoten 1 zu
|
||
Knoten 3 gehen, dann zu Knoten 5 und so weiter, bis Knoten n − 1 erreicht wurde. Danach
|
||
folgen Knoten n, n − 2, n − 4 und so weiter. Diese Tour hat offensichtlich Kosten n, da wir n
|
||
Kanten mit Gewicht 1 nutzen. Somit gilt OPT((Kn , d2 )) = n und wir haben eine Rate von
|
||
|
||
∆TSP2 ((Kn , d2 )) n − 1 + n/2 1
|
||
= = 3/2 − ≤ 3/2.
|
||
OPT((Kn , d2 )) n n
|
||
|
||
Da limn→∞ 3/2 − n1 = 3/2, kommen wir der Rate von 3/2 also beliebig nahe.
|
||
|