1159 lines
53 KiB
TeX
1159 lines
53 KiB
TeX
\documentclass[11pt]{article}
|
|
\input{style.tex}
|
|
|
|
\title{\textbf{AAK -- Übung}\\[0.4em]
|
|
\large Beweistechniken und Klausurtraining\\[0.2em]
|
|
\normalsize Aufgabentypen, Musterbeweise und Selbsttests zu Serie 9--13}
|
|
\author{Klausurvorbereitung \glqq Analyse von Algorithmen und Komplexität\grqq{} (CAU Kiel)}
|
|
\date{Sommersemester 2026}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\noindent\textbf{Wie du dieses Dokument benutzt.}
|
|
Voraussetzung ist \textbf{Fundament.pdf} -- alle Begriffe und Problemdefinitionen
|
|
werden hier als bekannt vorausgesetzt. Dieses PDF trainiert die
|
|
\emph{Aufgabentypen der Klausur}: Pro Kapitel bekommst du ein Rezept, komplett
|
|
ausformulierte Musterbeweise (aus Musterlösungen der Serien und dem Skript)
|
|
und 1--2 \emph{Selbsttest-Aufgaben} aus echten Altklausuren. Löse die
|
|
Selbsttests schriftlich unter Zeitdruck, bevor du die Lösungen im
|
|
Anhang~\ref{sec:loesungen} liest.
|
|
|
|
\medskip
|
|
\noindent\textbf{Der Klausur-Bauplan.} Alle vier Altklausuren (SS23/SS24, je
|
|
Haupt- und Nachklausur) folgen demselben Skelett -- 5--6 Aufgaben, 120 Minuten,
|
|
ein handbeschriebenes Blatt erlaubt:
|
|
|
|
\begin{center}
|
|
\small
|
|
\begin{tabular}{clcc}
|
|
\toprule
|
|
\# & Aufgabentyp & Punkte & Kapitel hier \\
|
|
\midrule
|
|
1 & Approx-Algorithmus \emph{anwenden} (LPT, Christofides, Greedy, $\Delta$TSP$_1$) & $\sim$10 & \ref{sec:anwenden} \\
|
|
2 & \emph{Vorlesungsbeweis} reproduzieren & 10 & \ref{sec:vlbeweise} \\
|
|
3 & \emph{NP-Schwere per Reduktion} (Variantenprobleme, 2 Stück) & 5+5 & \ref{sec:reduktion} \\
|
|
4 & \emph{Güte-Beweis} + Worst-Case-Instanz konstruieren & $\sim$10 & \ref{sec:gute} \\
|
|
5 & \emph{ETH-Lower-Bounds} aus vorgegebener Reduktion & 5+5 & \ref{sec:eth} \\
|
|
(6) & NP-Zugehörigkeit (Zertifikat/Verifizierer/NTM) -- nur SS23 & 10 & \ref{sec:npzug} \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\tableofcontents
|
|
\newpage
|
|
|
|
% ==================================================================
|
|
\section{NP-Zugehörigkeit zeigen}\label{sec:npzug}
|
|
% ==================================================================
|
|
|
|
Aufgabenformat (Klausur SS23, beide Male identisch): \glqq Zeigen Sie auf
|
|
verschiedene Weisen, dass das Problem in NP liegt: (a) Zertifikat angeben,
|
|
(b) Verifizierer beschreiben + Laufzeit konkret, (c) NTM in Worten + Laufzeit.\grqq
|
|
|
|
\begin{rezept}{Der NP-Dreischritt}
|
|
\textbf{(a) Zertifikat:} Die \glqq Lösung\grqq{} des Problems als Objekt --
|
|
Teilmenge, Belegung, Permutation. Angeben, wie es kodiert ist (z.\,B. ein Bit
|
|
pro Element) und dass es polynomiell lang ist.\\[0.4em]
|
|
\textbf{(b) Verifizierer:} Deterministischer Algorithmus, der (Instanz,
|
|
Zertifikat) bekommt und \emph{alle} geforderten Eigenschaften prüft. Danach
|
|
drei Punkte abhaken:
|
|
\begin{enumerate}
|
|
\item \emph{Beschreibung}: Welche Checks laufen in welcher Reihenfolge?
|
|
\item \emph{Korrektheit}: Ja-Instanz $\Rightarrow$ es existiert ein Zertifikat,
|
|
das akzeptiert wird; Nein-Instanz $\Rightarrow$ kein Zertifikat wird
|
|
akzeptiert.
|
|
\item \emph{Laufzeit}: pro Check abschätzen, Summe polynomiell (in der Klausur:
|
|
konkret in $O$-Notation!).
|
|
\end{enumerate}
|
|
\textbf{(c) NTM:} \glqq Rate und prüfe\grqq{} -- für jedes Element
|
|
nichtdeterministisch entscheiden, ob es zur Lösung gehört; danach
|
|
deterministisch dieselben Checks wie in (b). Korrektheit und Laufzeit wie oben
|
|
(polynomiell viele Rateschritte + polynomielle Prüfung).
|
|
\end{rezept}
|
|
|
|
\begin{merke}
|
|
Zusammenhang (a)--(c): Die Folge der Rateschritte der NTM \emph{ist} das
|
|
Zertifikat. Beide Wege nutzen die Extra-Ressource, um eine Lösungskandidatin
|
|
zu bestimmen und dann nur noch zu \emph{prüfen}.
|
|
\end{merke}
|
|
|
|
\subsection{Musterlösung: \problem{Knapsack} $\in$ NP (Präsenz 9.1)}
|
|
|
|
\textbf{NTM:} Für jeden Gegenstand entscheide nichtdeterministisch, ob er in
|
|
den Rucksack kommt. Prüfe anschließend $\sum_{i \in S} w_i \le K$ und
|
|
$\sum_{i \in S} p_i \ge P$; akzeptiere genau dann.
|
|
\emph{Korrektheit:} Existiert eine zulässige Füllung mit genügend Profit, gibt
|
|
es eine Folge von Entscheidungen, die sie findet -- diese wird akzeptiert.
|
|
Existiert keine, lehnt jeder Rechenweg ab.
|
|
\emph{Laufzeit:} $n$ Rateschritte, Summation und Vergleich in $O(n)$
|
|
Arithmetikschritten -- polynomiell.
|
|
|
|
\medskip
|
|
\textbf{Verifizierer:} Zertifikat ist $S \subseteq [n]$ (ein Bit pro
|
|
Gegenstand). Berechne $\sum_{i \in S} w_i$ und $\sum_{i \in S} p_i$, vergleiche
|
|
mit $K$ und $P$, akzeptiere entsprechend.
|
|
\emph{Korrektheit und Laufzeit:} analog.
|
|
|
|
\subsection{Musterlösung: \problem{FVS} $\in$ NP per Verifizierer (HA 9.2)}
|
|
|
|
Zertifikat: $X \subseteq V$ (ein Bit pro Knoten). Prüfe (1) $|X| \le k$,
|
|
(2) $G \setminus X$ ist azyklisch -- dafür den Algorithmus zur
|
|
\emph{topologischen Sortierung} aus der Vorlesung nutzen: Er findet genau dann
|
|
eine topologische Sortierung, wenn der Graph kreisfrei ist.
|
|
Beide Checks polynomiell $\Rightarrow$ polynomieller Verifizierer.
|
|
|
|
\begin{merke}
|
|
Nutze bekannte polynomielle Algorithmen als Bausteine des Verifizierers
|
|
(topologische Sortierung, DFS/BFS, Sortieren) -- mit Namen zitieren statt neu
|
|
erfinden.
|
|
\end{merke}
|
|
|
|
\subsection{Klausurniveau durchgerechnet: \problem{Longest Path} (SS23 A2)}
|
|
|
|
\emph{Gegeben $G = (V,E)$ und $k$; gibt es einen einfachen Pfad der Länge
|
|
$\ge k$?}
|
|
|
|
\medskip
|
|
\textbf{(a) Zertifikat:} Eine Folge von $k+1$ paarweise verschiedenen Knoten
|
|
$(v_0, v_1, \dots, v_k)$ -- der behauptete Pfad. Länge: $O(k \log |V|)$ Bits,
|
|
polynomiell.
|
|
|
|
\medskip
|
|
\textbf{(b) Verifizierer:} Prüfe
|
|
(1) alle $v_i$ paarweise verschieden -- $O(k^2)$ Vergleiche (oder Sortieren),
|
|
(2) $\{v_i, v_{i+1}\} \in E$ für alle $i = 0, \dots, k-1$ -- $k$ Lookups
|
|
in der Adjazenzmatrix, je $O(1)$, also $O(k)$.
|
|
Gesamt: $O(k^2) \subseteq O(|V|^2)$, polynomiell in der Eingabegröße.
|
|
\emph{Korrektheit:} Hat $G$ einen Pfad der Länge $\ge k$, so bilden seine
|
|
ersten $k+1$ Knoten ein akzeptiertes Zertifikat; wird umgekehrt ein Zertifikat
|
|
akzeptiert, ist es ein einfacher Pfad der Länge $k$.
|
|
|
|
\medskip
|
|
\textbf{(c) NTM:} Rate nacheinander $k+1$ Knoten auf ein Arbeitsband
|
|
($O(k \log |V|)$ nichtdeterministische Schritte). Prüfe dann deterministisch
|
|
Verschiedenheit und Kantenbedingung wie in (b). Laufzeit: Raten
|
|
$O(k \log |V|)$ plus Prüfung $\mathrm{poly}(|V|)$ -- insgesamt polynomiell.
|
|
|
|
\begin{warnung}
|
|
Häufige Fehlerquellen bei diesem Aufgabentyp:
|
|
\begin{itemize}
|
|
\item \emph{Korrektheit nur halb}: Es gehören \textbf{beide} Richtungen dazu
|
|
(Ja-Instanz $\Rightarrow$ akzeptierendes Zertifikat existiert; akzeptiert
|
|
$\Rightarrow$ Ja-Instanz).
|
|
\item \emph{Laufzeit vergessen oder nur \glqq polynomiell\grqq{} sagen}, wenn
|
|
konkrete $O$-Notation verlangt ist.
|
|
\item Beim Verifizierer die \emph{Kardinalitätsprüfung} ($|C| \le k$ bzw.
|
|
$\ge k$) unterschlagen.
|
|
\end{itemize}
|
|
Punkteschema der Serien: Beschreibung 2\,P., Korrektheit 1\,P., Laufzeit 1\,P.
|
|
\end{warnung}
|
|
|
|
\begin{aufgabe}{1 -- \problem{Dominating Set} (Klausur SS23-N, A2; 3+3+4\,P.)}
|
|
$G = (V,E)$ ungerichtet, $k \in \mathbb{N}_0$. Gibt es $D \subseteq V$,
|
|
$|D| \le k$, sodass jeder Knoten in $D$ liegt oder zu einem Knoten in $D$
|
|
benachbart ist?
|
|
\begin{enumerate}
|
|
\item[(a)] Geben Sie ein Zertifikat an.
|
|
\item[(b)] Beschreiben Sie einen polynomiellen Verifizierer; Laufzeit konkret
|
|
in $O$-Notation.
|
|
\item[(c)] Beschreiben Sie in Worten eine polynomielle NTM; Laufzeit konkret
|
|
in $O$-Notation.
|
|
\end{enumerate}
|
|
Lösung: Anhang~\ref{sol:domset}.
|
|
\end{aufgabe}
|
|
|
|
% ==================================================================
|
|
\section{Die vier Vorlesungsbeweise (der 10-Punkte-Block)}\label{sec:vlbeweise}
|
|
% ==================================================================
|
|
|
|
In \textbf{jeder} Altklausur gibt es genau eine Aufgabe \glqq Beweis zur
|
|
Vorlesung\grqq{} für 10 Punkte. Bisher kamen dran: $\problem{SAT} \redp
|
|
k\text{-}\problem{Clique}$ (SS24-H), $\problem{SAT} \redp \problem{3-SAT}$
|
|
(SS24-N), $k$-\problem{Clique} NP-vollständig (SS23-H), List-Scheduling-Güte
|
|
$2 - 1/m$ (SS23-N). Diese vier Beweise musst du \emph{reproduzieren} können --
|
|
sie gehören auf dein erlaubtes handschriftliches Blatt.
|
|
|
|
\subsection{Beweis 1: \problem{SAT} $\redp$ \problem{3-SAT} (Skript Satz 6.25)}
|
|
|
|
\textbf{Aussage:} \problem{3-SAT} ist NP-vollständig. (In der Klausur SS24
|
|
durfte $\problem{3-SAT} \in \NP$ angenommen werden; sonst: Belegung raten und
|
|
prüfen.)
|
|
|
|
\begin{proof}
|
|
Zu zeigen: $\problem{SAT} \redp \problem{3-SAT}$. Gesucht ist eine
|
|
polynomzeitberechenbare Transformation $\alpha \mapsto \bar{\alpha}$ mit
|
|
$\alpha \in \problem{SAT} \iff \bar{\alpha} \in \problem{3-SAT}$.
|
|
|
|
\emph{Idee:} Eine lange Klausel wird mit Hilfsvariablen in eine Kette von
|
|
3er-Klauseln aufgespalten:
|
|
\[
|
|
(y_1 \vee \dots \vee y_n) \text{ erfüllbar} \iff
|
|
(y_1 \vee y_2 \vee x_1) \wedge (\neg x_1 \vee y_3 \vee x_2) \wedge \dots
|
|
\wedge (\neg x_{n-3} \vee y_{n-1} \vee y_n) \text{ erfüllbar},
|
|
\]
|
|
wobei $x_1, \dots, x_{n-3}$ neue Hilfsvariablen sind (pro Klausel eigene).
|
|
|
|
\emph{$\Rightarrow$:} Sei $(y_1 \vee \dots \vee y_n)$ wahr, etwa $y_i$ wahr.
|
|
Setze $x_1 = \dots = x_{i-2} = \mathit{true}$ und
|
|
$x_{i-1} = \dots = x_{n-3} = \mathit{false}$. Dann ist jede Kettenklausel
|
|
erfüllt: Die ersten $i-2$ durch ihr $x$-Literal, die Klausel mit $y_i$ durch
|
|
$y_i$, die restlichen durch ihr $\neg x$-Literal.
|
|
|
|
\emph{$\Leftarrow$:} Sei die rechte Seite erfüllt und angenommen, alle $y_i$
|
|
wären falsch. Dann erzwingt die erste Klausel $x_1 = \mathit{true}$, damit die
|
|
zweite $x_2 = \mathit{true}$, induktiv $x_{n-3} = \mathit{true}$ -- aber die
|
|
letzte Klausel $(\neg x_{n-3} \vee y_{n-1} \vee y_n)$ ist dann falsch,
|
|
Widerspruch. Also ist ein $y_i$ wahr und die Originalklausel erfüllt.
|
|
|
|
Wende dies klauselweise an. Es gilt $|\bar{\alpha}| \le c\,|\alpha|$ mit
|
|
$c = O(1)$, und die Transformation ist in Polynomialzeit berechenbar. Da
|
|
\problem{SAT} NP-vollständig und $\problem{3-SAT} \in \NP$ ist, ist
|
|
\problem{3-SAT} NP-vollständig.
|
|
\end{proof}
|
|
|
|
\subsection{Beweis 2: $k$-\problem{Clique} $\in$ NP (Skript Lemma 6.13)}
|
|
|
|
Dieser kleine Beweis ist Teil des Vorlesungsbeweises \glqq $k$-\problem{Clique}
|
|
ist NP-vollständig\grqq.
|
|
|
|
\begin{proof}
|
|
Polynomieller Verifizierer: Neben der Eingabe ($G = (V,E)$, $k$) erhält der
|
|
Algorithmus ein Zertifikat $C \subseteq V$. Er prüft:
|
|
(1) für alle zweielementigen Teilmengen $\{u,v\} \subseteq C$, ob
|
|
$\{u,v\} \in E$ -- Zeit $O(|C|^2) = O(|V|^2)$;
|
|
(2) ob $|C| \ge k$ -- Zeit $O(|V|)$.
|
|
Ausgabe Ja genau dann, wenn beide Tests positiv sind. Da die Eingabelänge
|
|
$\Omega(|V| + |E|)$ ist, ist die Laufzeit polynomiell.
|
|
\end{proof}
|
|
|
|
\subsection{Beweis 3: \problem{SAT} $\redp$ $k$-\problem{Clique} (Skript Satz 6.26)}
|
|
|
|
\begin{warnung}
|
|
Die Klausur SS24 verlangte ausdrücklich die Reduktion vom \emph{allgemeinen}
|
|
SAT (beliebig lange Klauseln) -- \textbf{nicht} von 3-SAT! Die Konstruktion
|
|
unten funktioniert für beide.
|
|
\end{warnung}
|
|
|
|
\textbf{Aussage:} $k$-\problem{Clique} ist NP-vollständig.
|
|
|
|
\begin{proof}
|
|
(a) $k$-\problem{Clique} $\in \NP$: siehe Beweis 2.
|
|
|
|
(b) $\problem{SAT} \redp k\text{-}\problem{Clique}$:
|
|
Sei $F = F_1 \wedge \dots \wedge F_m$ in KNF mit Klauseln
|
|
$F_i = (y_{i1} \vee \dots \vee y_{i\ell_i})$.
|
|
\emph{Konstruktion} von $G = (V,E)$ in polynomieller Zeit:
|
|
\begin{align*}
|
|
V &= \{\, [i,j] \mid 1 \le i \le m,\ 1 \le j \le \ell_i \,\}
|
|
&& \text{(ein Knoten pro Literalvorkommen)}\\
|
|
E &= \{\, \{[i,j],[i',j']\} \mid i \ne i' \text{ und } y_{ij} \ne \neg y_{i'j'} \,\}
|
|
&& \text{(verschiedene Klausel, nicht widersprüchlich)}
|
|
\end{align*}
|
|
Setze $k = m$. \emph{Behauptung:} $F$ erfüllbar $\iff$ $G$ enthält eine Clique
|
|
mit $m$ Knoten.
|
|
|
|
\emph{$\Rightarrow$:} Sei $\psi$ erfüllende Belegung. Dann gibt es für jedes
|
|
$i$ ein $r_i$ mit $\psi(y_{ir_i}) = \mathit{true}$. Setze
|
|
$C = \{\, [i, r_i] \mid 1 \le i \le m \,\}$. Wäre
|
|
$\{[i,r_i],[j,r_j]\} \notin E$ für $i \ne j$, dann müsste (nach Definition von
|
|
$E$) $y_{ir_i} = \neg y_{jr_j}$ gelten -- aber beide sind unter $\psi$ wahr,
|
|
Widerspruch. Also ist $C$ eine $m$-Clique.
|
|
|
|
\emph{$\Leftarrow$:} Sei $C$ eine $m$-Clique. Da Knoten derselben Klausel nie
|
|
verbunden sind, hat $C$ die Form $C = \{[1,r_1], \dots, [m,r_m]\}$. Definiere
|
|
$\psi$ mit $\psi(y_{1r_1}) = \dots = \psi(y_{mr_m}) = \mathit{true}$. Das ist
|
|
widerspruchsfrei, da $y_{ir_i} \ne \neg y_{jr_j}$ für alle $i \ne j$ (sonst
|
|
keine Kante). Dann ist jede Klausel $F_i$ erfüllt, also $\psi(F) =
|
|
\mathit{true}$.
|
|
|
|
Da \problem{SAT} NP-vollständig ist, $\problem{SAT} \redp
|
|
k\text{-}\problem{Clique}$ gilt und $k$-\problem{Clique} $\in \NP$, ist
|
|
$k$-\problem{Clique} NP-vollständig.
|
|
\end{proof}
|
|
|
|
\begin{bsp}{Konstruktion konkret (Skript Beispiel 6.27)}
|
|
$F = (x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge
|
|
(x_1 \vee \neg x_2 \vee \neg x_3)$, also $m = 3$.
|
|
Knoten: $[1,1], [1,2], [1,3]$ (Klausel 1), $[2,1], [2,2]$ (Klausel 2),
|
|
$[3,1], [3,2], [3,3]$ (Klausel 3). Kanten zwischen allen Paaren aus
|
|
verschiedenen Klauseln \emph{außer} z.\,B. $\{[1,1],[2,1]\}$ ($x_1$ vs.
|
|
$\neg x_1$) oder $\{[2,2],[3,2]\}$ (beide $\neg x_2$: kein Widerspruch, Kante
|
|
existiert!). Nur \emph{komplementäre} Literalpaare bekommen keine Kante.
|
|
Die Clique $\{[1,1], [2,2], [3,1]\}$ ($x_1$, $\neg x_2$, $x_1$) liefert
|
|
$\psi(x_1) = \mathit{true}$, $\psi(x_2) = \mathit{false}$ ($x_3$ frei).
|
|
\end{bsp}
|
|
|
|
\subsection{Beweis 4: List Scheduling hat Güte $2 - \frac{1}{m}$ (Skript Satz 7.24a)}
|
|
|
|
\textbf{Aussage:} Für alle Eingaben $I = (L, m)$ gilt
|
|
$\mathrm{LS}(I)/\OPT(I) \le 2 - 1/m$.
|
|
|
|
\begin{proof}
|
|
O.B.d.A. habe Maschine $M_1$ nach der Zuordnung die höchste Last
|
|
$L = \sum_{j \in B_1} p_j$, d.\,h. $\mathrm{LS}(I) = L$. Sei $J_k$ der letzte
|
|
Job, der $M_1$ zugeordnet wurde. \emph{Kernbeobachtung:} Zum Zeitpunkt der
|
|
Zuordnung von $J_k$ hatte $M_1$ die \emph{kleinste} Last $L - p_k$ -- also
|
|
haben \emph{alle} Maschinen mindestens Last $L - p_k$. Daraus folgt
|
|
\[
|
|
\sum_{i=1}^{n} p_i \;\ge\; m\,(L - p_k) + p_k.
|
|
\]
|
|
Außerdem gelten die beiden Standard-Schranken für das Optimum:
|
|
\[
|
|
\OPT(I) \;\ge\; \frac{1}{m} \sum_{i=1}^n p_i
|
|
\qquad\text{und}\qquad
|
|
\OPT(I) \;\ge\; p_k .
|
|
\]
|
|
(Die Gesamtlast verteilt sich auf $m$ Maschinen; und jeder einzelne Job muss
|
|
irgendwo laufen.) Kombinieren:
|
|
\[
|
|
\OPT(I) \;\ge\; \frac{1}{m}\sum_{i=1}^n p_i
|
|
\;\ge\; \frac{m(L - p_k) + p_k}{m}
|
|
\;=\; L - \Big(1 - \frac{1}{m}\Big) p_k
|
|
\;=\; \mathrm{LS}(I) - \Big(1 - \frac{1}{m}\Big) p_k .
|
|
\]
|
|
Mit $p_k \le \OPT(I)$ folgt
|
|
$\OPT(I) \ge \mathrm{LS}(I) - (1 - \frac{1}{m})\,\OPT(I)$, also
|
|
$\mathrm{LS}(I) \le (2 - \frac{1}{m})\,\OPT(I)$.
|
|
\end{proof}
|
|
|
|
\begin{merke}
|
|
Die zwei $\OPT$-Schranken $\OPT \ge \frac{1}{m}\sum p_i$ (Durchschnittslast)
|
|
und $\OPT \ge p_{\max}$ (größter Job) sind das Universalwerkzeug \emph{aller}
|
|
Scheduling-Güte-Beweise -- auch für RoundRobin (Kapitel~\ref{sec:gute}) und
|
|
LPT.
|
|
\end{merke}
|
|
|
|
\begin{aufgabe}{Selbstkontrolle ohne Lösung im Anhang}
|
|
Reproduziere jeden der vier Beweise handschriftlich, ohne in dieses Dokument
|
|
zu schauen. Kontrolliere gegen die jeweilige Stelle hier. Wiederhole jeden
|
|
Beweis, bei dem du einen Schritt ausgelassen hast -- besonders gern vergessen:
|
|
die Polynomialität der Transformation und die Rückrichtung.
|
|
\end{aufgabe}
|
|
|
|
% ==================================================================
|
|
\section{NP-Schwere per Reduktion: das Handwerk}\label{sec:reduktion}
|
|
% ==================================================================
|
|
|
|
Der häufigste Klausur-Aufgabentyp: Ein \emph{Variantenproblem} (bekanntes
|
|
Problem mit Zusatzeigenschaft) soll als NP-schwer oder NP-vollständig bewiesen
|
|
werden.
|
|
|
|
\begin{rezept}{NP-Vollständigkeits-Boilerplate (6 Schritte)}
|
|
\begin{enumerate}
|
|
\item \textbf{$\in$ NP:} Verifizierer angeben (oft: \glqq wie beim
|
|
Originalproblem, da nur die Instanzen eingeschränkt sind\grqq). Bei reiner
|
|
NP-\emph{Schwere}-Frage entfällt dieser Schritt.
|
|
\item \textbf{Quellproblem wählen:} ein bekanntes NP-vollständiges Problem
|
|
$X$, das dem Zielproblem $Y$ möglichst ähnlich ist. Richtung: $X \redp Y$!
|
|
\item \textbf{Konstruktion angeben:} Wie wird aus einer $X$-Instanz eine
|
|
$Y$-Instanz? Präzise, mit allen Parametern (auch $k$ anpassen!).
|
|
\item \textbf{Polynomialität:} Konstruktion läuft in Polynomialzeit
|
|
(meist 1 Satz: \glqq naiv in $O(\cdot)$\grqq).
|
|
\item \textbf{Korrektheit, beide Richtungen:}
|
|
$\Rightarrow$ Ja-Instanz von $X$ liefert Ja-Instanz von $Y$;
|
|
$\Leftarrow$ Ja-Instanz von $Y$ liefert Ja-Instanz von $X$.
|
|
\item \textbf{Schlusssatz:} \glqq Also existiert eine polynomielle Reduktion
|
|
von $X$ auf $Y$. Da $X$ NP-vollständig ist und $Y \in \NP$ gilt, ist $Y$
|
|
NP-vollständig.\grqq
|
|
\end{enumerate}
|
|
Punkteschema (HA 11.1): Verifizierer 1+0{,}5+0{,}5\,P.; Angabe Reduktion 1\,P.;
|
|
Korrektheit 3\,P. (\textbf{1{,}5 pro Richtung}); Laufzeit 1\,P.;
|
|
Beweisführung 1\,P.
|
|
\end{rezept}
|
|
|
|
\begin{warnung}
|
|
Die drei Klassiker-Fehler:
|
|
\begin{itemize}
|
|
\item \textbf{Falsche Richtung}: Es muss das \emph{bekannte} Problem auf das
|
|
\emph{neue} reduziert werden ($X_{\text{bekannt}} \redp Y_{\text{neu}}$).
|
|
\item \textbf{Rückrichtung vergessen} -- kostet 1{,}5 von 5 Punkten.
|
|
\item Die konstruierte Instanz erfüllt die \emph{Zusatzeigenschaft} des
|
|
Zielproblems nicht (z.\,B. universeller Knoten fehlt, Grad-Bedingung
|
|
verletzt).
|
|
\end{itemize}
|
|
\end{warnung}
|
|
|
|
\subsection{Muster 1: Zusatzeigenschaft erzwingen -- $k$-\problem{Clique Universal} (HA 10.2)}
|
|
|
|
\emph{Das} Musterbeispiel; im Aufgabentext wörtlich als \glqq klassische
|
|
Klausuraufgabe\grqq{} bezeichnet. Gegeben: $k$-\problem{Clique}, aber die
|
|
Instanz enthält garantiert einen \emph{universellen Knoten} (mit allen
|
|
verbunden).
|
|
|
|
\begin{proof}
|
|
\emph{$\in$ NP:} Jeder Verifizierer für $k$-\problem{Clique} eignet sich, da
|
|
lediglich eine Zusatzeigenschaft der \emph{Instanz} hinzukam.
|
|
|
|
\emph{Reduktion} $k\text{-}\problem{Clique} \redp
|
|
k\text{-}\problem{Clique Universal}$: Gegeben $(G = (V,E), k)$. Definiere
|
|
$\bar{k} = k + 1$ und $\bar{G} = (\bar{V}, \bar{E})$ mit
|
|
$\bar{V} = V \cup \{u\}$ für einen neuen Knoten $u \notin V$ und
|
|
$\bar{E} = E \cup \{\, \{u,v\} \mid v \in V \,\}$. Der Knoten $u$ ist
|
|
universell, also ist $(\bar{G}, \bar{k})$ eine gültige Instanz; berechenbar in
|
|
$O(|V|)$.
|
|
|
|
\emph{$\Rightarrow$:} Sei $C$ eine Clique in $G$ mit $|C| \ge k$. Da $u$ mit
|
|
allen Knoten verbunden ist, ist $\bar{C} = C \cup \{u\}$ eine Clique in
|
|
$\bar{G}$ mit $|\bar{C}| \ge k + 1 = \bar{k}$.
|
|
|
|
\emph{$\Leftarrow$:} Sei $\bar{C}$ eine Clique in $\bar{G}$ mit
|
|
$|\bar{C}| \ge \bar{k}$. Dann ist $C = \bar{C} \setminus \{u\} \subseteq V$
|
|
eine Clique in $G$ (Teilmenge einer Clique; $u$ ist der einzige neue Knoten)
|
|
mit $|C| \ge \bar{k} - 1 = k$.
|
|
|
|
Also ist $k$-\problem{Clique Universal} NP-vollständig.
|
|
\end{proof}
|
|
|
|
\begin{merke}
|
|
\textbf{Schema \glqq bekanntes Problem + Zusatzeigenschaft\grqq:}
|
|
Verifizierer erben; die Reduktion muss nur die Zusatzstruktur \emph{herstellen}
|
|
(Knoten/Item hinzufügen, skalieren) und den Parameter $k$ nachziehen.
|
|
Prüfe immer: Erfüllt \emph{jede} konstruierte Instanz die Zusatzeigenschaft?
|
|
\end{merke}
|
|
|
|
\subsection{Muster 2: Komplement-Dualität -- \problem{Clique} $\redp$ \problem{VC} (Präsenz 10.2)}
|
|
|
|
\begin{proof}
|
|
$\problem{VC} \in \NP$: bekannt (HA 9.1).
|
|
|
|
\emph{Reduktion:} Gegeben $(G = (V,E), k)$ mit $n = |V|$ (o.B.d.A. $k \le n$).
|
|
Invertiere den Graphen zu $G'$ (Komplementgraph: genau die Nicht-Kanten von
|
|
$G$). Gib $(G', n - k)$ als \problem{VC}-Instanz aus.
|
|
|
|
\emph{$\Rightarrow$:} $G$ enthalte eine Clique $C$, $|C| \ge k$. Dann ist
|
|
$V' := V \setminus C$ ein Vertex Cover von $G'$ mit $|V'| \le n - k$: In $G'$
|
|
gibt es keine Kante zwischen Knoten aus $C$ (in $G$ waren alle da), also hat
|
|
jede Kante von $G'$ einen Endpunkt außerhalb von $C$, d.\,h. in $V'$.
|
|
|
|
\emph{$\Leftarrow$:} $G'$ enthalte ein VC $V'$ mit $|V'| \le n - k$. Dann ist
|
|
$C := V \setminus V'$ eine Clique in $G$ mit $|C| \ge k$: Für
|
|
$\{u,v\} \subseteq C$ gilt $\{u,v\} \notin E'$ (sonst wäre $V'$ kein VC),
|
|
also $\{u,v\} \in E$.
|
|
|
|
\emph{Laufzeit:} Invertieren naiv in $O(|V|^2)$, polynomiell. Mit dem
|
|
Schlusssatz folgt: \problem{VC} ist NP-vollständig.
|
|
\end{proof}
|
|
|
|
\subsection{Muster 3: Antiparallele Bögen -- \problem{VC} $\redp$ \problem{FVS} (HA 10.1)}
|
|
|
|
\begin{proof}
|
|
$\problem{FVS} \in \NP$: bekannt (HA 9.2, topologische Sortierung).
|
|
|
|
\emph{Reduktion:} Für eine \problem{VC}-Instanz $(G = (V,E), k)$ erzeuge den
|
|
gerichteten Graphen $G' = (V, E')$ mit
|
|
$E' := \{\, (u,v), (v,u) \mid \{u,v\} \in E \,\}$ -- jede ungerichtete Kante
|
|
wird zu \emph{zwei antiparallelen Bögen}. Gib $(G', k)$ aus.
|
|
|
|
\emph{$\Rightarrow$:} Sei $C$ ein VC mit $|C| \le k$. Dann enthält
|
|
$G \setminus C$ keine Kanten, also enthält $G' \setminus C$ keine Bögen und
|
|
damit keine Kreise.
|
|
|
|
\emph{$\Leftarrow$:} Sei $X$ ein FVS mit $|X| \le k$. Dann ist $X$ ein VC in
|
|
$G$: Gäbe es eine Kante $\{u,v\} \in E$ mit $u \notin X$ und $v \notin X$,
|
|
so wäre $(u, v, u)$ ein Kreis in $G' \setminus X$ -- Widerspruch.
|
|
|
|
\emph{Laufzeit:} $O(|E|)$. Schlusssatz $\Rightarrow$ \problem{FVS}
|
|
NP-vollständig.
|
|
\end{proof}
|
|
|
|
\subsection{Muster 4: Gadget + o.B.d.A.-Bereinigung -- \problem{VC} $\redp$ $\Delta$\problem{-Cover} (HA 11.1)}
|
|
|
|
\begin{proof}
|
|
\emph{$\in$ NP:} Zertifikat $C_\Delta \subseteq V$; prüfe $|C_\Delta| \le k$
|
|
und für alle $\le |V|^3$ Knotentripel, ob sie ein Dreieck bilden und dann
|
|
getroffen werden; $O(|V|^4)$, polynomiell.
|
|
|
|
\emph{Reduktion:} Für eine \problem{VC}-Instanz $(G = (V,E), k)$ bilde
|
|
$G' = (V', E')$ mit $V' = V \cup \{\, v_e \mid e \in E \,\}$ und
|
|
$E' = E \cup \{\, \{v_e, e_1\}, \{v_e, e_2\} \mid e = \{e_1, e_2\} \in E \,\}$
|
|
-- \textbf{jede Kante wird zu einem Dreieck} $\{v_e, e_1, e_2\}$ aufgeblasen.
|
|
Gib $(G', k)$ aus.
|
|
|
|
\emph{$\Rightarrow$:} Sei $C$ ein VC von $G$, $|C| \le k$. Jedes Dreieck in
|
|
$G'$ ist entweder ein Dreieck aus $G$ (drei paarweise verbundene Knoten, deren
|
|
Kanten alle von $C$ überdeckt sind, also ein Eckknoten in $C$) oder ein
|
|
Gadget-Dreieck $\{v_e, e_1, e_2\}$ -- und $e_1 \in C$ oder $e_2 \in C$, da $C$
|
|
die Kante $e$ überdeckt. Also ist $C$ eine Dreiecksüberdeckung.
|
|
|
|
\emph{$\Leftarrow$:} Sei $C_\Delta$ eine Dreiecksüberdeckung von $G'$,
|
|
$|C_\Delta| \le k$. \textbf{O.B.d.A. gilt $C_\Delta \subseteq V$}: Enthält
|
|
$C_\Delta$ einen Gadget-Knoten $v_e$, ersetze ihn durch $e_1$ -- die
|
|
Überdeckung bleibt erhalten (alle Dreiecke durch $v_e$ enthalten $e_1$ oder
|
|
$e_2$; das einzige Dreieck mit $v_e$ ist $\{v_e,e_1,e_2\}$) und die Menge wird
|
|
nicht größer. Nun trifft $C_\Delta$ jedes Gadget-Dreieck
|
|
$\{v_e, e_1, e_2\}$ in $e_1$ oder $e_2$ -- also ist für jede Kante
|
|
$e = \{e_1, e_2\} \in E$ ein Endpunkt in $C_\Delta$: ein Vertex Cover.
|
|
|
|
\emph{Laufzeit:} $O(|E|)$. Schlusssatz $\Rightarrow$ $\Delta$\problem{-Cover}
|
|
NP-vollständig.
|
|
\end{proof}
|
|
|
|
\begin{merke}
|
|
Die \textbf{o.B.d.A.-Bereinigung} (Gadget-Knoten in der Rückrichtung durch
|
|
Original-Knoten ersetzen) ist ein wiederkehrender Trick: Sie macht die
|
|
Rückrichtung sauber, ohne Fallunterscheidungen zu multiplizieren. Immer
|
|
begründen, warum die Ersetzung (i) die Lösungseigenschaft erhält und (ii) die
|
|
Menge nicht vergrößert.
|
|
\end{merke}
|
|
|
|
\subsection{Muster 5: Padding und Shift -- \problem{SubSet Sum} $\redp$ \problem{SubSet Sum Cardinality} (Präsenz 11.3)}
|
|
|
|
Zielproblem: wie SubSet Sum, aber zusätzlich $|S| = n/2$ gefordert.
|
|
|
|
\begin{proof}
|
|
\emph{Reduktion:} Für $I = (c_1, \dots, c_n, K)$ definiere
|
|
$c_i' := c_i + 1$ für $i \le n$ (\glqq Shift\grqq) und $c_i' := 1$ für
|
|
$i \in \{n+1, \dots, 2n\}$ ($n$ \glqq Padding-Items\grqq). Ausgabe:
|
|
$I' = (c_1', \dots, c_{2n}', K + n)$ mit Kardinalitätsforderung $n$ (von $2n$
|
|
Items).
|
|
|
|
\emph{$\Rightarrow$:} Sei $S$ mit $\sum_{i \in S} c_i = K$. Dann
|
|
$\sum_{i \in S} c_i' = K + |S|$. Fülle mit Padding-Items
|
|
$S' = \{n+1, \dots, 2n - |S|\}$ auf: $|S \cup S'| = n$ und
|
|
$\sum_{i \in S \cup S'} c_i' = K + |S| + (n - |S|) = K + n$.
|
|
|
|
\emph{$\Leftarrow$:} Sei $S'$ mit $|S'| = n$ und $\sum_{i \in S'} c_i' = K+n$.
|
|
Setze $S := S' \cap \{1, \dots, n\}$. Die $n - |S|$ Padding-Items in $S'$
|
|
tragen je 1 bei, also
|
|
$\sum_{i \in S} (c_i + 1) = K + n - (n - |S|) = K + |S|$, d.\,h.
|
|
$\sum_{i \in S} c_i = K$.
|
|
|
|
\emph{Laufzeit:} $O(n)$. Schlusssatz.
|
|
\end{proof}
|
|
|
|
\begin{merke}
|
|
\textbf{Der SubSet-Sum-Werkzeugkasten} (für die Klausur-Varianten):
|
|
\begin{itemize}
|
|
\item \emph{Skalieren}: $c_i' = \lambda c_i$, $K' = \lambda K$ ändert die
|
|
Lösbarkeit nicht -- erzwingt Teilbarkeitseigenschaften (z.\,B. $\lambda = 3$:
|
|
alle Größen durch 3 teilbar / keine Größe ist Zweierpotenz).
|
|
\item \emph{Shift + Padding}: $c_i' = c_i + 1$ plus Einsen-Items -- erzwingt
|
|
Kardinalitäten (Muster 5).
|
|
\item \emph{Skalieren + Sonder-Item}: $c_i' = 2 c_i$, neues Item der Größe 1,
|
|
$K' = 2K + 1$ -- erzwingt, dass das Sonder-Item in jeder Lösung liegt
|
|
(Parität!).
|
|
\end{itemize}
|
|
In jeder Altklausur kam genau eine solche SubSet-Sum-Variante dran.
|
|
\end{merke}
|
|
|
|
\subsection{Muster 6: Dummy-Knoten -- \problem{Clique-Nomember} (Präsenz 11.2)}
|
|
|
|
Kurzfassung: Gegeben \problem{Clique}-Instanz $(G, k)$; füge einen neuen
|
|
\emph{isolierten} Knoten $v$ hinzu und frage nach einer $k$-Clique ohne $v$ in
|
|
$G' = (V \cup \{v\}, E)$.
|
|
$\Rightarrow$: Eine $k$-Clique in $G$ enthält $v$ nicht (v ist neu) -- fertig.
|
|
$\Leftarrow$: Eine $k$-Clique ohne $v$ in $G'$ liegt komplett in $G$.
|
|
Laufzeit $O(1)$ zusätzlich. Der isolierte Knoten ist das einfachste Gadget
|
|
überhaupt.
|
|
|
|
\subsection{Gadget-Katalog}
|
|
|
|
\begin{center}
|
|
\small
|
|
\begin{tabular}{p{4.6cm}p{5.2cm}p{4.2cm}}
|
|
\toprule
|
|
Zusatzeigenschaft / Ziel & Trick & Beispiel \\
|
|
\midrule
|
|
Verbotener/erzwungener Knoten & isolierten bzw. universellen Knoten hinzufügen, $k$ anpassen & Clique-Nomember; Clique Universal \\
|
|
ungerichtet $\to$ gerichtet & Kante $\to$ zwei antiparallele Bögen (2-Kreise) & VC $\redp$ FVS \\
|
|
Kanten- $\to$ Dreiecksstruktur & Kante zu Dreieck aufblasen (neuer Knoten pro Kante) & VC $\redp$ $\Delta$-Cover \\
|
|
Komplement-Sicht & Graph invertieren; Clique $\leftrightarrow$ IS $\leftrightarrow$ VC & Clique $\redp$ VC \\
|
|
Kardinalität erzwingen & $+1$-Shift + Padding-Einsen & SubSetSum Cardinality \\
|
|
Zahleneigenschaften & skalieren ($\times \lambda$), Sonder-Item, Parität & SubsetSum-Klausurvarianten \\
|
|
Grad-Bedingungen ($\deg \ge d$) & Gadget an jeden Knoten hängen, das Grad erhöht, ohne Lösungen zu ändern & Hitchhiker's-HK (SS24-N) \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{aufgabe}{2 -- \problem{CliqueAndIndependentSet} (Klausur SS24-H, A3a; 5\,P.)}
|
|
Gegeben $G = (V,E)$ und $k \ge 1$. Entscheide: Gibt es in $G$ \emph{sowohl}
|
|
ein Independent Set der Größe $k$ \emph{als auch} eine Clique der Größe $k$?
|
|
Zeigen Sie die NP-Schwere durch Reduktion eines bekannten NP-schweren
|
|
Problems. Lösung: Anhang~\ref{sol:cis}.
|
|
\end{aufgabe}
|
|
|
|
\begin{aufgabe}{3 -- \problem{SubSet Sum} mit Teilbarkeit (Klausur SS23-H, A5a; 4\,P.)}
|
|
Beweisen Sie die NP-Vollständigkeit von \problem{SubSet Sum}, bei dem jede
|
|
Itemgröße durch 3 oder durch 7 teilbar ist. Lösung: Anhang~\ref{sol:teilbar}.
|
|
\end{aufgabe}
|
|
|
|
\begin{aufgabe}{4 -- \problem{HamiltonianPath} $\leftrightarrow$ \problem{HamiltonianCycle} (Klausur SS23-N, A5b/c; 5+6\,P.)}
|
|
Geben Sie polynomielle Reduktionen an:
|
|
(b) $\problem{HamiltonianPath} \redp \problem{HamiltonianCycle}$;
|
|
(c) $\problem{HamiltonianCycle} \redp \problem{HamiltonianPath}$.
|
|
Lösung: Anhang~\ref{sol:hamilton}.
|
|
\end{aufgabe}
|
|
|
|
% ==================================================================
|
|
\section{Approximation: anwenden, beweisen, Worst Case bauen}\label{sec:anwenden}
|
|
% ==================================================================
|
|
|
|
Dieser Aufgabenkomplex besteht in der Klausur aus zwei Aufgaben: einer
|
|
\emph{Anwendungsaufgabe} (Algorithmus auf konkrete Instanz, Aufgabe 1) und
|
|
einem \emph{Güte-Beweis mit Worst-Case-Konstruktion} (Aufgabe 4).
|
|
|
|
\subsection{Anwenden: die Rechenaufgabe}
|
|
|
|
\begin{rezept}{Was du flüssig rechnen können musst}
|
|
\begin{itemize}
|
|
\item \textbf{LPT/List Scheduling:} Jobs (ggf. sortieren), der Reihe nach auf
|
|
die Maschine mit kleinster Last; Schedule \emph{grafisch} zeichnen
|
|
(Maschinen-Balken mit Zeitachse); Güte nennen ($2 - \frac1m$ bzw.
|
|
$\frac43 - \frac{1}{3m}$).
|
|
\item \textbf{$\Delta$TSP$_1$:} MST $\to$ Kanten verdoppeln $\to$ Eulerkreis
|
|
(Startknoten beachten!) $\to$ Abkürzen; erklären, warum Güte 2 und wozu die
|
|
$\Delta$-Ungleichung.
|
|
\item \textbf{Christofides:} MST $\to$ ungerad-gradige Knoten $X$ $\to$
|
|
min. perfektes Matching auf $X$ $\to$ Eulerkreis $\to$ Abkürzen. Alle
|
|
Zwischengraphen angeben -- auch Schritte nennen, die nichts ändern!
|
|
\item \textbf{Knapsack-Greedy/MGA:} nach Profitdichte $p_i/w_i$ sortieren,
|
|
einpacken was passt; MGA: Vergleich mit bestem Einzel-Item; Güte 2 nennen;
|
|
Verbesserungsidee: $k$-Enumeration (Sahni) $\to$ $3/2$ bei $k = 2$, $4/3$ bei
|
|
$k = 3$.
|
|
\end{itemize}
|
|
\end{rezept}
|
|
|
|
\begin{bsp}{Knapsack-Greedy durchgerechnet (Klausur SS23-H, A1)}
|
|
Instanz (Items als $(p_i, w_i)$, Kapazität $B = 16$):
|
|
$(1,4), (1,1), (1,3), (11,13), (3,3), (5,6), (1,5)$.\\[0.3em]
|
|
\textbf{GA:} Profitdichten: $1/4, 1/1, 1/3, 11/13, 3/3, 5/6, 1/5$
|
|
$= 0{,}25;\ 1;\ 0{,}33;\ 0{,}85;\ 1;\ 0{,}83;\ 0{,}2$.
|
|
Sortierung: $(1,1), (3,3), (11,13), (5,6), (1,3), (1,4), (1,5)$.
|
|
Einpacken: $(1,1)$ [Last 1], $(3,3)$ [4], $(11,13)$ passt nicht ($17 > 16$),
|
|
$(5,6)$ [10], $(1,3)$ [13], $(1,4)$ passt nicht, $(1,5)$ passt nicht.
|
|
$\mathrm{GA} = 1 + 3 + 5 + 1 = 10$.\\[0.3em]
|
|
\textbf{MGA:} bestes Einzel-Item $(11,13)$ mit Profit 11 $> 10$
|
|
$\Rightarrow$ $\mathrm{MGA} = 11$.\\[0.3em]
|
|
\textbf{Vergleich:} Optimal ist $\{(11,13), (3,3)\}$: Gewicht 16, Profit
|
|
$\OPT = 14$. GA verfehlt wegen des Dichte-Fokus das schwere profitable Item;
|
|
MGA repariert das teilweise (Güte 2 garantiert).
|
|
\end{bsp}
|
|
|
|
\begin{bsp}{Christofides durchgerechnet (Klausur SS23-N, A1)}
|
|
Graph: Knoten $a, b, c, d$; Distanzen $d(a,b) = 1$, $d(b,c) = 2$,
|
|
$d(a,d) = 2$, $d(a,c) = 3$, $d(c,d) = 3$ (fehlende Paare über kürzeste Wege,
|
|
z.\,B. $d(b,d) = 3$).\\[0.3em]
|
|
(1) \textbf{MST} (Kruskal): $\{a,b\}$ (1), $\{b,c\}$ (2), $\{a,d\}$ (2);
|
|
Gewicht 5.\\
|
|
(2) \textbf{Ungerade Grade im MST}: $a$: Grad 2, $b$: Grad 2, $c$: Grad 1,
|
|
$d$: Grad 1 $\Rightarrow X = \{c, d\}$.\\
|
|
(3) \textbf{Min. perfektes Matching auf $X$}: einzige Möglichkeit
|
|
$K = \{\{c,d\}\}$, Kosten 3.\\
|
|
(4) \textbf{Multigraph} $T + K$: alle Grade gerade.
|
|
\textbf{Eulerkreis} ab $a$: $[a, b, c, d, a]$, Kosten $1 + 2 + 3 + 2 = 8$.\\
|
|
(5) \textbf{Abkürzen}: kein Knoten doppelt -- dieser Schritt ändert hier
|
|
nichts (in der Klausur trotzdem erwähnen!). Tour $R = [a,b,c,d,a]$, Länge 8.\\
|
|
Hier gilt sogar $R = \OPT$. Güte-Garantie: $1{,}5$; benötigt Symmetrie
|
|
\emph{und} Dreiecksungleichung.
|
|
\end{bsp}
|
|
|
|
\subsection{Güte-Beweise: die drei Beweismuster}\label{sec:gute}
|
|
|
|
\begin{rezept}{Muster A: OPT von unten durch Struktur abschätzen (Matching)}
|
|
Für Minimierungsprobleme: Finde eine Struktur in der Algorithmus-Lösung, die
|
|
\emph{jede} Optimallösung zwingt, groß zu sein.\\[0.3em]
|
|
\textbf{Musterbeweis 2ApproxVC (Präsenz 12.1):} Der Algorithmus nimmt für jede
|
|
noch unüberdeckte Kante \emph{beide} Endpunkte. Sei $A$ die Menge dieser
|
|
Kanten; dann $|C| = 2|A|$. Die Kanten in $A$ sind paarweise knotendisjunkt
|
|
(ein \emph{Matching}) -- sonst wäre eine schon überdeckt gewesen. Jedes VC
|
|
$C^*$ braucht pro Kante aus $A$ einen \emph{eigenen} Knoten, also
|
|
$|C^*| \ge |A|$. Zusammen: $|C| = 2|A| \le 2|C^*|$. \qedhere
|
|
\end{rezept}
|
|
|
|
\begin{rezept}{Muster B: Widerspruch + Zählen (MAX-3-SAT, HA 12.1 = Klausur SoSe23)}
|
|
Algorithmus $A$: werte $\beta_0$ (alles false) und $\beta_1$ (alles true) aus,
|
|
gib die bessere zurück. \textbf{Zu zeigen:} $v(A(\varphi)) \ge \frac12
|
|
v(\OPT(\varphi))$.\\[0.3em]
|
|
\emph{Beweis (Widerspruch):} Angenommen $v(A(\varphi)) < \frac12
|
|
v(\OPT(\varphi))$ für ein $\varphi$ mit $m$ Klauseln. Wegen
|
|
$v(\OPT(\varphi)) \le m$ folgt $v(\beta_0) < \frac{m}{2}$ \emph{und}
|
|
$v(\beta_1) < \frac{m}{2}$. Aber jede Klausel enthält mindestens ein positives
|
|
oder ein negatives Literal und wird daher von $\beta_0$ \emph{oder} $\beta_1$
|
|
erfüllt; also $v(\beta_0) + v(\beta_1) \ge m$, d.\,h. eine der beiden erfüllt
|
|
$\ge \frac{m}{2}$ Klauseln -- Widerspruch.\\[0.3em]
|
|
\emph{Scharfe Instanz (Teil b):}
|
|
$\varphi = (x_1 \vee x_2 \vee x_3) \wedge (\neg x_0 \vee \neg x_2 \vee \neg x_3)$.
|
|
Mit $\beta = \{x_0 \mapsto \mathit{false},\ x_1, x_2, x_3 \mapsto
|
|
\mathit{true}\}$ sind beide Klauseln erfüllt: $\OPT = 2$. Aber $\beta_0$
|
|
erfüllt nur Klausel 2, $\beta_1$ nur Klausel 1: $v(A(\varphi)) = 1 = \frac12
|
|
\OPT$. \emph{Bauprinzip: komplementäre Klauseln.}
|
|
\end{rezept}
|
|
|
|
\begin{rezept}{Muster C: Scheduling-Schranken (RoundRobin, Klausur SS24-N A4)}
|
|
RoundRobin: Jobs absteigend sortiert, reihum verteilt ($J_j$ auf Maschine
|
|
$((j-1) \bmod m) + 1$). \textbf{Zu zeigen (per Widerspruch): Güte 2.}\\[0.3em]
|
|
Angenommen $\mathrm{RR}(I) > 2 \cdot \OPT(I)$. Sei $M_i$ die Maschine mit
|
|
maximaler Last; sie trägt die Jobs $J_i, J_{i+m}, J_{i+2m}, \dots$
|
|
Für $l \ge 1$ gilt wegen der Sortierung
|
|
$p_{i+lm} \le p_j$ für alle $j \le (l-1)m + m = lm$, insbesondere
|
|
\[
|
|
p_{i+lm} \;\le\; \frac{1}{m} \sum_{j=(l-1)m+1}^{lm} p_j .
|
|
\]
|
|
Summieren über $l \ge 1$:
|
|
$\mathrm{RR}(I) - p_i \le \frac1m \sum_{j} p_j \le \OPT(I)$.
|
|
Mit $p_i \le p_1 \le \OPT(I)$ folgt $\mathrm{RR}(I) \le 2\,\OPT(I)$ --
|
|
Widerspruch zur Annahme.\\[0.3em]
|
|
Kern: dieselben zwei $\OPT$-Schranken wie bei List Scheduling
|
|
(Durchschnittslast, größter Job).
|
|
\end{rezept}
|
|
|
|
\subsection{Worst-Case-Instanzen konstruieren}
|
|
|
|
Der zweite Teil der Klausuraufgabe: \glqq Geben Sie eine
|
|
Konstruktionsvorschrift für eine Instanz an, mit der der Algorithmus beliebig
|
|
nah an die Güte kommt.\grqq
|
|
|
|
\begin{rezept}{Bauprinzip}
|
|
\begin{enumerate}
|
|
\item Zwinge den Algorithmus zu einer lokal guten, global schlechten
|
|
Entscheidung (Greedy-Falle) -- oder nutze adversarielles Tie-Breaking
|
|
(bei Gleichständen die schlechteste Wahl unterstellen).
|
|
\item Parametrisiere die Instanz ($n$, $m$, $T$, \dots) und berechne
|
|
$A(I)$ und $\OPT(I)$ \emph{explizit}.
|
|
\item Zeige $A(I)/\OPT(I) \to$ Schranke (Grenzwert angeben).
|
|
\end{enumerate}
|
|
\end{rezept}
|
|
|
|
\begin{bsp}{List Scheduling erreicht $2 - \frac1m$}
|
|
$m(m-1)$ Jobs der Größe 1, danach \emph{ein} Job der Größe $m$ (Liste in
|
|
dieser Reihenfolge). List Scheduling verteilt die Einsen gleichmäßig (jede
|
|
Maschine $m-1$), der große Job kommt obendrauf: $\mathrm{LS} = (m-1) + m =
|
|
2m - 1$. Optimal: großer Job allein auf eine Maschine, die $m(m-1)$ Einsen auf
|
|
die übrigen $m-1$ Maschinen ($m$ pro Maschine): $\OPT = m$. Rate:
|
|
$(2m-1)/m = 2 - \frac1m$ -- exakt die Schranke.
|
|
\end{bsp}
|
|
|
|
\begin{bsp}{RoundRobin erreicht $2 - \frac1m$ (Klausur SS24-N A4b, Bonus)}
|
|
Ein Job der Größe $m$ und $m(m-1)$ Jobs der Größe 1 (absteigend sortiert:
|
|
der große zuerst). RoundRobin gibt Maschine 1 den großen Job \emph{und} (da
|
|
reihum verteilt wird) $m - 1$ weitere Einser-Jobs:
|
|
$\mathrm{RR} = m + (m-1) = 2m - 1$; $\OPT = m$ wie eben. Für $m = 3$ (7 Jobs:
|
|
$3,1,1,1,1,1,1$): $\mathrm{RR} = 5$, $\OPT = 3$, Rate $5/3$ -- genau die in
|
|
der Klausur gestufte Teilpunkt-Konstruktion.
|
|
\end{bsp}
|
|
|
|
\begin{bsp}{Christofides erreicht $3/2$ asymptotisch (Präsenz 12.2, Skizze)}
|
|
Leiter-Graph mit $n$ Knoten ($n \bmod 4 = 2$): Sprossen und Holme mit
|
|
Distanz 1, Rest über kürzeste Wege. Adversariell gewählter Zickzack-MST
|
|
(Kosten $n-1$) lässt nur die Knoten $1$ und $n$ mit ungeradem Grad; das
|
|
Matching ist die einzelne Kante $\{1, n\}$ mit Kosten $n/2$ (kürzester Weg).
|
|
Tour: $n - 1 + n/2$, $\OPT = n$ (außen herum). Rate
|
|
$\frac{n - 1 + n/2}{n} = \frac32 - \frac1n \to \frac32$.
|
|
Merke: Bei MST-/Matching-Gleichständen darf der Prüfling die \emph{schlechte}
|
|
Wahl unterstellen -- das ist der Sinn von \glqq eine mögliche Ausführung\grqq.
|
|
\end{bsp}
|
|
|
|
\begin{aufgabe}{5 -- \problem{ApproximateSubsetSum} (Klausur SS24-H, A4; 3+7\,P.)}
|
|
Maximiere $\sum_{j \in S} a_j \le T$ (alle $a_i \le T$, $\sum a_i > T$).
|
|
Algorithmus GA: sortiere absteigend, nimm Zahlen der Reihe nach, \emph{stoppe}
|
|
beim ersten Element, das nicht mehr passt.
|
|
(a) Konstruktionsvorschrift für Instanzen, mit denen GA beliebig nah an Güte 2
|
|
kommt. (b) Zeigen Sie $\mathrm{GA}(I) \ge \OPT(I)/2$.
|
|
Lösung: Anhang~\ref{sol:apxss}.
|
|
\end{aufgabe}
|
|
|
|
\begin{aufgabe}{6 -- \problem{Min-Edge-Cover} (Klausur SS23-N, A3; 6+4\,P.)}
|
|
Gesucht: kardinalitätsminimale Kantenmenge $C$, sodass jeder Knoten inzident
|
|
zu einer Kante aus $C$ ist ($G$ zusammenhängend). Algorithmus $A$: gehe die
|
|
Knoten in beliebiger Reihenfolge durch; ist der aktuelle Knoten $v$ noch nicht
|
|
abgedeckt, füge eine beliebige zu $v$ inzidente Kante zu $C$ hinzu.
|
|
(a) Zeigen Sie $A(G) \le 2 \cdot \OPT(G)$.
|
|
(b) Kreisgraph $G_n$ ($n \ge 4$ gerade): Wie groß ist ein Min-Edge-Cover?
|
|
Geben Sie Reihenfolge und Kantenwahl an, die zur schlechtesten Rate führen.
|
|
Lösung: Anhang~\ref{sol:edgecover}.
|
|
\end{aufgabe}
|
|
|
|
% ==================================================================
|
|
\section{ETH-Lower-Bounds: das Schema}\label{sec:eth}
|
|
% ==================================================================
|
|
|
|
Immer die letzte Klausuraufgabe: Eine Reduktion ist \emph{vorgegeben}; du
|
|
sollst untere Schranken bzgl. zweier Parameter herleiten. Das ist ein
|
|
Schema-Spiel -- wer das Muster kennt, sammelt hier die sichersten 10 Punkte
|
|
der Klausur.
|
|
|
|
\begin{rezept}{ETH-Aufgabe in drei Schritten}
|
|
\textbf{Schritt 1 -- Parameter abschätzen:} Drücke jeden gefragten Parameter
|
|
der konstruierten Instanz durch $n$ (Variablen) und $m$ (Klauseln) der
|
|
3-SAT-Quellinstanz aus. Nutze $n \le 3m$ (jede Variable kommt in einer Klausel
|
|
vor, jede Klausel hat $\le 3$ Literale).\\[0.4em]
|
|
\textbf{Schritt 2 -- Textbaustein (Kontraposition):}
|
|
\begin{quote}
|
|
\glqq Angenommen, es gäbe einen Algorithmus, der [Zielproblem] in
|
|
$2^{o(p)} \cdot |I|^{O(1)}$ löst. Da $p = O(f(m))$ nach Schritt 1, existiert
|
|
durch Kombination der Reduktion mit diesem Algorithmus ein Algorithmus, der
|
|
3-SAT in $2^{o(m)} \cdot |I|^{O(1)}$ löst. Nach dem Sparsification-Lemma geht
|
|
das nur, wenn die ETH nicht gilt. Also existiert ein solcher Algorithmus nur,
|
|
wenn die ETH falsch ist.\grqq
|
|
\end{quote}
|
|
\textbf{Schritt 3 -- Exponent justieren (Wurzel-Regel):} Wächst der Parameter
|
|
polynomiell, $p = O(m^c)$, dann ist die Schranke
|
|
$2^{o(\sqrt[c]{p})}$: aus $q = o(\sqrt[c]{p})$ und $p = O(m^c)$ folgt
|
|
$q = o(m)$. Beispiele: $|E| = O(m^2) \Rightarrow 2^{o(\sqrt{|E|})}$;
|
|
$|T| = O(m^4) \Rightarrow 2^{o(\sqrt[4]{|T|})}$.
|
|
\end{rezept}
|
|
|
|
\begin{warnung}
|
|
\begin{itemize}
|
|
\item \textbf{$n$ oder $m$?} Hängt dein Parameter (auch) an $m$, brauchst du
|
|
das \emph{Sparsification-Lemma} und schreibst $2^{o(m)}$. Hängt er nur an $n$,
|
|
reicht die ETH direkt ($2^{o(n)}$). Im Zweifel: Lemma zitieren schadet nicht.
|
|
\item \textbf{Reduktionsketten:} Bei $X \redp Y \redp Z$ die Schranken
|
|
schrittweise durchreichen und auf den vorigen Teil verweisen (\glqq nach
|
|
Aufgabenteil 1 gibt es diesen nur, wenn die ETH nicht gilt\grqq).
|
|
\item Die Schlussformel \glqq \dots{} nur, wenn die ETH falsch ist\grqq{} in
|
|
\emph{jedem} Teilpunkt wiederholen -- sie ist Teil der erwarteten Lösung.
|
|
\end{itemize}
|
|
\end{warnung}
|
|
|
|
\subsection{Die Vorlesungs-Reduktionskette mit allen Schranken (Präsenz 13.1)}
|
|
|
|
\begin{center}
|
|
\footnotesize
|
|
\begin{tabular}{lll}
|
|
\toprule
|
|
Reduktion & Parameter der Zielinstanz & ergibt Lower Bounds \\
|
|
\midrule
|
|
$\problem{3-SAT} \redp k\text{-}\problem{Clique}$ &
|
|
$|V| = O(m)$, $|E| = O(m^2)$, $k = m$ &
|
|
$2^{o(|V|)}$, $2^{o(\sqrt{|E|})}$, $2^{o(k)}$ \\
|
|
$k\text{-}\problem{Clique} \redp k\text{-}\problem{IS}$ &
|
|
$|V'| = |V|$, $|E'| \le |V|^2$ &
|
|
$2^{o(|V|)}$, $2^{o(\sqrt{|E|})}$ \\
|
|
$\problem{SAT} \redp \problem{3-DM}$ &
|
|
$|U| = |V| = |W| = O(mn) \subseteq O(m^2)$, $|T| = O(m^2 n^2) \subseteq O(m^4)$ &
|
|
$2^{o(\sqrt{|V|})}$, $2^{o(\sqrt[4]{|T|})}$ \\
|
|
$\problem{3-DM} \redp \problem{3-EC}$ &
|
|
Spezialfall: $|U| = O(|V|)$, $|F| = |T|$ &
|
|
$2^{o(\sqrt{|U|})}$, $2^{o(\sqrt[4]{|F|})}$ \\
|
|
$\problem{3-EC} \redp \problem{SubSet Sum}$ &
|
|
$n_{\text{Items}} = |F|$ &
|
|
$2^{o(\sqrt[4]{n})}$ \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
(Über die \emph{strenge} Wegener-Reduktion $\problem{3-SAT} \redp
|
|
\problem{SubSet Sum}$ mit $|A| = O(m)$ Items gilt sogar: kein
|
|
$2^{o(n)} \cdot \poly$ für SubSet Sum und Partition; Skript Satz 6.40.)
|
|
|
|
\subsection{Musterlösung 1: Lower Bounds für \problem{Vertex Cover} (HA 13.1)}
|
|
|
|
Reduktion: $\problem{Clique} \redp \problem{VC}$ aus Präsenz 10
|
|
(Komplementgraph, $k' = n - k$).
|
|
|
|
\medskip
|
|
\textbf{Teil 1 -- Parameter:} $|V'| = |V|$;\quad
|
|
$|E'| = \binom{|V|}{2} - |E| \le |V|^2$;\quad $k' = |V| - k \le |V|$.
|
|
|
|
\medskip
|
|
\textbf{Teil 2 -- Schranken} (jeweils mit dem Textbaustein):
|
|
\begin{itemize}
|
|
\item Kein $2^{o(|V'|)} \cdot |I|^{O(1)}$: Sonst gäbe es (Reduktion +
|
|
Algorithmus, $|V'| = |V|$) einen $2^{o(|V|)}$-Algorithmus für \problem{Clique}
|
|
-- nach Präsenz 13 nur möglich, wenn die ETH falsch ist.
|
|
\item Kein $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$: Wegen $|E'| \le |V|^2$ ist
|
|
$\sqrt{|E'|} \le |V|$, also ergäbe sich ein $2^{o(|V|)}$-Algorithmus für
|
|
\problem{Clique} -- ETH falsch.
|
|
\item Kein $2^{o(k')} \cdot |I|^{O(1)}$: Wegen $k' \le |V|$ analog.
|
|
\end{itemize}
|
|
Punkteschema: Teil 1: 1\,P.; Teil 2: 1{,}5 + 1{,}5 + 1\,P.
|
|
|
|
\subsection{Musterlösung 2: Lower Bounds für \problem{Hitting Set} (HA 13.2)}
|
|
|
|
Gegebene Reduktion $\problem{3-SAT} \redp \problem{Hitting Set}$:
|
|
$U = \{x_1, \bar{x}_1, \dots, x_n, \bar{x}_n\}$; pro Variable
|
|
$F_i = \{x_i, \bar{x}_i\}$; pro Klausel $F_{n+j} = C_j$; $k = n$.
|
|
|
|
\medskip
|
|
\textbf{Teil 1 -- Parameter:} $|U| = 2n$;\quad $r = n + m$;\quad $k = n$.
|
|
|
|
\medskip
|
|
\textbf{Teil 2 -- Schranken:}
|
|
\begin{itemize}
|
|
\item Kein $2^{o(|U|)}$: $|U| = 2n$, also ergäbe sich ein
|
|
$2^{o(n)}$-Algorithmus für 3-SAT -- direkt ein Widerspruch zur ETH
|
|
(nur $n$ beteiligt, Lemma nicht nötig).
|
|
\item Kein $2^{o(r)}$: $r = n + m \le 3m + m = 4m = O(m)$, also ergäbe sich
|
|
ein $2^{o(m)}$-Algorithmus für 3-SAT -- \textbf{hier} braucht es das
|
|
Sparsification-Lemma.
|
|
\item Kein $2^{o(k)}$: $k = n$, analog zum ersten Punkt.
|
|
\end{itemize}
|
|
|
|
\begin{aufgabe}{7 -- Lower Bounds für $k$-\problem{Color} (Klausur SS24-H, A5a; 5\,P.)}
|
|
Gegeben ist die Vorlesungsreduktion $\problem{3-SAT} \redp
|
|
k\text{-}\problem{Color}$ (Knoten $x_i, \bar{x}_i, v_i$ für jede Variable,
|
|
$C_j$ für jede Klausel, Zentrum $z$; Kanten wie im Skript).
|
|
Welche Lower Bounds ergeben sich unter der ETH bzgl.
|
|
(i) $|V|$ und (ii) $|E|$? Lösung: Anhang~\ref{sol:kcolor}.
|
|
\end{aufgabe}
|
|
|
|
\begin{aufgabe}{8 -- Lower Bounds für \problem{Set Cover} (Klausur SS23-N, A6a; 5\,P.)}
|
|
Bekannt: \problem{Hitting Set} ist unter der ETH weder in
|
|
$2^{o(r')}\langle I \rangle^{O(1)}$ noch in
|
|
$2^{o(|U'|)}\langle I \rangle^{O(1)}$ lösbar. Gegeben ist die
|
|
Dualitäts-Reduktion $\problem{Set Cover} \redp \problem{Hitting Set}$:
|
|
$U' := \{1, \dots, r\}$ (Mengen-Indizes werden Elemente), für jedes
|
|
$w \in U$ die Menge $F_w' := \{\, v \in \{1,\dots,r\} \mid w \in F_v \,\}$,
|
|
$k' = k$. Welche Schranken folgen für \problem{Set Cover} bzgl.
|
|
(i) $|U|$ und (ii) $r$? Lösung: Anhang~\ref{sol:setcover}.
|
|
\end{aufgabe}
|
|
|
|
% ==================================================================
|
|
\section{Kurz: NP-Schwere via Unentscheidbarkeit (Halteproblem)}\label{sec:halt}
|
|
% ==================================================================
|
|
|
|
Serienstoff (HA 11.2), in den vier Altklausuren nie geprüft -- der Beweis ist
|
|
kurz, nimm ihn mit.
|
|
|
|
\begin{proof}[Beweis ($\problem{HALT}_{\mathrm{TM}}$ ist NP-schwer)]
|
|
Wir zeigen $\problem{SAT} \redp \problem{HALT}_{\mathrm{TM}}$. Aus einer
|
|
KNF-Formel $\varphi$ konstruiere eine DTM $M_\varphi$: (1) ignoriere die
|
|
Eingabe, (2) enumeriere systematisch alle Belegungen der Variablen von
|
|
$\varphi$, (3) prüfe jede, (4) \emph{halte}, sobald eine erfüllende gefunden
|
|
ist, (5) sonst laufe für immer. Setze $f(\varphi) = \langle M_\varphi,
|
|
\varepsilon \rangle$.
|
|
|
|
\emph{Pointe:} $M_\varphi$ läuft nicht polynomiell -- aber sie lässt sich in
|
|
Polynomialzeit \emph{konstruieren}; nur das zählt für $f$.
|
|
|
|
$\Rightarrow$: Ist $\varphi$ erfüllbar, findet $M_\varphi$ eine erfüllende
|
|
Belegung und hält. $\Leftarrow$: Hält $M_\varphi$, so nur, weil eine
|
|
erfüllende Belegung gefunden wurde; also $\varphi \in \problem{SAT}$.
|
|
\end{proof}
|
|
|
|
\begin{merke}
|
|
$\problem{HALT}_{\mathrm{TM}}$ ist NP-schwer, aber nicht NP-vollständig: Es
|
|
liegt nicht in NP (nicht einmal entscheidbar). Typische Transferfrage im Stil
|
|
von Präsenz 10.1 (ii).
|
|
\end{merke}
|
|
|
|
% ==================================================================
|
|
\section{Klausur-Fahrplan und Checklisten}
|
|
% ==================================================================
|
|
|
|
\begin{rezept}{Zeitbudget (120 Minuten, $\sim$55 Punkte)}
|
|
Grob 2 Minuten pro Punkt: Anwendungsaufgabe $\sim$20\,min,
|
|
Vorlesungsbeweis $\sim$20\,min, Reduktionen $2 \times 12$\,min, Güte-Beweis
|
|
$\sim$20\,min, ETH $\sim$15\,min, Puffer $\sim$20\,min.
|
|
Beginne mit deinen sichersten Typen -- ETH und Vorlesungsbeweis sind am besten
|
|
vorhersagbar. Notenschlüssel der Altklausuren: 4{,}0 ab $\sim$17{,}5\,P.,
|
|
1{,}0 ab $\sim$35\,P. -- du musst nicht alles schaffen.
|
|
\end{rezept}
|
|
|
|
\begin{rezept}{Was auf das handbeschriebene Blatt gehört}
|
|
\begin{itemize}
|
|
\item Die vier Vorlesungsbeweise (Kapitel~\ref{sec:vlbeweise}), mindestens als
|
|
Stichpunkt-Gerüst.
|
|
\item Boilerplate: 6-Schritte-Reduktionsschema + Schlusssatz
|
|
(Kapitel~\ref{sec:reduktion}).
|
|
\item ETH-Textbaustein + Wurzel-Regel + $n \le 3m$
|
|
(Kapitel~\ref{sec:eth}).
|
|
\item Gadget-Katalog und SubSet-Sum-Werkzeugkasten.
|
|
\item Die zwei $\OPT$-Schranken fürs Scheduling; MAX-3-SAT-Formel;
|
|
LS-Worst-Case-Instanz.
|
|
\item Dualitätsdreieck Clique/IS/VC; NP-Dreischritt.
|
|
\end{itemize}
|
|
\end{rezept}
|
|
|
|
\begin{rezept}{Letzte Kontrolle bei jeder Beweisaufgabe}
|
|
\begin{itemize}
|
|
\item Reduktionsrichtung richtig? ($X_{\text{bekannt}} \redp Y_{\text{neu}}$)
|
|
\item Beide Korrektheitsrichtungen da?
|
|
\item Polynomialität (Reduktion bzw. Verifizierer) explizit erwähnt?
|
|
\item Parameter ($k$, $T$, \dots) in der Konstruktion angepasst?
|
|
\item Schlusssatz geschrieben?
|
|
\end{itemize}
|
|
\end{rezept}
|
|
|
|
% ==================================================================
|
|
\appendix
|
|
\section{Lösungen zu den Selbsttests}\label{sec:loesungen}
|
|
% ==================================================================
|
|
|
|
\subsection{Lösung zu Selbsttest 1: \problem{Dominating Set}}\label{sol:domset}
|
|
|
|
\textbf{(a) Zertifikat:} Eine Teilmenge $D \subseteq V$ (ein Bit pro Knoten,
|
|
Länge $O(|V|)$) -- die behauptete dominierende Menge.
|
|
|
|
\medskip
|
|
\textbf{(b) Verifizierer:} Prüfe (1) $|D| \le k$: Bits zählen, $O(|V|)$.
|
|
(2) Dominanz: Für jeden Knoten $v \in V$ teste, ob $v \in D$ oder ein Nachbar
|
|
von $v$ in $D$ liegt -- pro Knoten Durchlauf seiner Zeile in der
|
|
Adjazenzmatrix, $O(|V|)$; gesamt $O(|V|^2)$.
|
|
Akzeptiere genau dann, wenn beides gilt. Laufzeit insgesamt
|
|
$O(|V|^2)$, polynomiell.
|
|
\emph{Korrektheit:} Existiert ein Dominating Set der Größe $\le k$, so wird
|
|
das zugehörige Zertifikat akzeptiert; akzeptiert der Verifizierer ein $D$,
|
|
erfüllt $D$ per Konstruktion beide definierenden Eigenschaften.
|
|
|
|
\medskip
|
|
\textbf{(c) NTM:} Rate für jeden Knoten nichtdeterministisch, ob er in $D$
|
|
liegt ($O(|V|)$ Rateschritte). Prüfe danach deterministisch $|D| \le k$ und
|
|
die Dominanzbedingung wie in (b). Laufzeit: $O(|V|)$ Raten +
|
|
$O(|V|^2)$ Prüfen $= O(|V|^2)$, polynomiell.
|
|
\emph{Korrektheit:} Ja-Instanz $\Rightarrow$ es existiert ein Rechenweg, der
|
|
ein gültiges $D$ rät und akzeptiert; Nein-Instanz $\Rightarrow$ jeder
|
|
Rechenweg verwirft in der Prüfphase.
|
|
|
|
\subsection{Lösung zu Selbsttest 2: \problem{CliqueAndIndependentSet}}\label{sol:cis}
|
|
|
|
Reduktion von \problem{Clique}. Sei $(G = (V,E), k)$ gegeben (o.B.d.A.
|
|
$k \ge 1$). Konstruiere $G'$, indem zu $G$ genau $k$ \emph{neue isolierte
|
|
Knoten} $u_1, \dots, u_k$ hinzugefügt werden; Ausgabe $(G', k)$. Laufzeit
|
|
$O(k) \subseteq O(|V|)$, polynomiell.
|
|
|
|
\emph{$\Rightarrow$:} Hat $G$ eine Clique $C$ mit $|C| \ge k$, so hat $G'$
|
|
dieselbe Clique; außerdem ist $\{u_1, \dots, u_k\}$ ein Independent Set der
|
|
Größe $k$ (isolierte Knoten). Also Ja-Instanz.
|
|
|
|
\emph{$\Leftarrow$:} Hat $G'$ eine Clique $C'$ der Größe $k$, so gilt für
|
|
$k \ge 2$: $C'$ enthält keinen der isolierten Knoten (die haben keine Kanten),
|
|
also $C' \subseteq V$ und $C'$ ist eine $k$-Clique in $G$. (Für $k = 1$ ist
|
|
jede Instanz mit $V \neq \emptyset$ trivial eine Ja-Instanz beider Probleme.)
|
|
|
|
Da \problem{Clique} NP-schwer ist, ist \problem{CliqueAndIndependentSet}
|
|
NP-schwer. \emph{Trick: Das Independent Set wird \glqq gratis\grqq{}
|
|
mitgeliefert, ohne die Clique-Frage zu beeinflussen.}
|
|
|
|
\subsection{Lösung zu Selbsttest 3: \problem{SubSet Sum} mit Teilbarkeit}\label{sol:teilbar}
|
|
|
|
$\in \NP$: Verifizierer wie bei \problem{SubSet Sum} (Teilmenge als
|
|
Zertifikat, Summe prüfen) -- nur die Instanzmenge ist eingeschränkt.
|
|
|
|
\emph{Reduktion von \problem{SubSet Sum}:} Gegeben $(c_1, \dots, c_n, K)$.
|
|
Setze $c_i' := 3 c_i$ und $K' := 3K$. Jede Itemgröße ist durch 3 teilbar,
|
|
also ist die konstruierte Instanz gültig; Laufzeit $O(n)$.
|
|
|
|
\emph{Korrektheit:} Für jede Teilmenge $S$ gilt
|
|
$\sum_{i \in S} c_i' = 3 \sum_{i \in S} c_i$, also
|
|
$\sum_{i \in S} c_i' = K' \iff \sum_{i \in S} c_i = K$ -- beide Richtungen in
|
|
einem Schritt. Mit dem Schlusssatz folgt die NP-Vollständigkeit.
|
|
|
|
\subsection{Lösung zu Selbsttest 4: \problem{HamiltonianPath} $\leftrightarrow$ \problem{HamiltonianCycle}}\label{sol:hamilton}
|
|
|
|
\textbf{(b) HP $\redp$ HC:} Gegeben $G = (V,E)$. Füge einen neuen
|
|
\emph{universellen} Knoten $u$ hinzu: $G' = (V \cup \{u\},\;
|
|
E \cup \{\,\{u,v\} \mid v \in V\,\})$. Laufzeit $O(|V|)$.
|
|
\emph{$\Rightarrow$:} Ein Hamiltonpfad $v_1, \dots, v_n$ in $G$ wird durch $u$
|
|
zum Kreis $v_1, \dots, v_n, u, v_1$ geschlossen.
|
|
\emph{$\Leftarrow$:} Ein Hamiltonkreis in $G'$ besucht $u$ genau einmal;
|
|
Entfernen von $u$ (und seiner zwei Kreiskanten) liefert einen Hamiltonpfad in
|
|
$G$.
|
|
|
|
\medskip
|
|
\textbf{(c) HC $\redp$ HP:} Gegeben $G = (V,E)$, o.B.d.A. $|V| \ge 3$. Wähle
|
|
einen beliebigen Knoten $v$. Konstruiere $G'$: füge eine Kopie $v^*$ mit
|
|
derselben Nachbarschaft wie $v$ hinzu sowie zwei neue Grad-1-Knoten $s$
|
|
(nur mit $v$ verbunden) und $t$ (nur mit $v^*$ verbunden). Laufzeit
|
|
$O(|V| + |E|)$.
|
|
\emph{$\Rightarrow$:} Ein Hamiltonkreis $v, w_1, w_2, \dots, w_{n-1}, v$ in
|
|
$G$ liefert den Hamiltonpfad $s, v, w_1, \dots, w_{n-1}, v^*, t$ in $G'$
|
|
(die letzte Kreiskante $\{w_{n-1}, v\}$ existiert auch zu $v^*$).
|
|
\emph{$\Leftarrow$:} Ein Hamiltonpfad in $G'$ muss in den Grad-1-Knoten $s$
|
|
und $t$ enden, hat also die Form $s, v, \dots, v^*, t$. Der Mittelteil
|
|
$v, \dots, v^*$ besucht alle Knoten von $G$ (plus $v^*$); Ersetzen von $v^*$
|
|
durch $v$ am Ende schließt einen Hamiltonkreis in $G$ (Nachbarschaften
|
|
identisch).
|
|
|
|
\subsection{Lösung zu Selbsttest 5: \problem{ApproximateSubsetSum}}\label{sol:apxss}
|
|
|
|
\textbf{(a) Konstruktionsvorschrift:} Für gerades $T$ nimm
|
|
$a_1 = T/2 + 1$, $a_2 = a_3 = T/2$. GA sortiert absteigend, nimmt $a_1$,
|
|
und stoppt: $a_2$ passt nicht mehr ($T/2 + 1 + T/2 > T$).
|
|
$\mathrm{GA}(I) = T/2 + 1$, aber $\OPT(I) = T$ (Items 2 und 3).
|
|
Rate: $\frac{T}{T/2 + 1} \to 2$ für $T \to \infty$.
|
|
|
|
\medskip
|
|
\textbf{(b) Güte 2:} Sei $S$ die von GA gewählte Menge und $a_\ell$ das erste
|
|
Element, das nicht mehr passte (existiert wegen $\sum_i a_i > T$; falls GA
|
|
alle Elemente bis zum Abbruch einpackt, betrachte den Abbruchmoment). Dann
|
|
gilt
|
|
\[
|
|
\mathrm{GA}(I) + a_\ell \;>\; T \;\ge\; \OPT(I).
|
|
\]
|
|
Wegen der absteigenden Sortierung wurde $a_\ell$ erst nach allen gewählten
|
|
Elementen betrachtet. Ist $S = \emptyset$, wäre schon $a_1 = a_\ell > T$ --
|
|
ausgeschlossen, da $a_i \le T$. Also enthält $S$ ein Element
|
|
$a_j \ge a_\ell$ (Sortierung), somit $\mathrm{GA}(I) \ge a_\ell$. Einsetzen:
|
|
\[
|
|
2\,\mathrm{GA}(I) \;\ge\; \mathrm{GA}(I) + a_\ell \;>\; T \;\ge\; \OPT(I),
|
|
\]
|
|
also $\mathrm{GA}(I) \ge \OPT(I)/2$. \qed
|
|
|
|
\subsection{Lösung zu Selbsttest 6: \problem{Min-Edge-Cover}}\label{sol:edgecover}
|
|
|
|
\textbf{(a) Güte 2:} Jede von $A$ gewählte Kante wird für einen zu diesem
|
|
Zeitpunkt \emph{unabgedeckten} Knoten $v$ gewählt; danach ist $v$ abgedeckt.
|
|
Verschiedene Auswahlschritte gehören also zu verschiedenen Knoten:
|
|
$A(G) = |C| \le |V|$... genauer: $|C| \le$ Anzahl der Auswahlschritte $\le
|
|
|V|$. Andererseits deckt jede Kante höchstens 2 Knoten ab, also braucht jede
|
|
Lösung $\OPT(G) \ge |V|/2$ Kanten. Zusammen:
|
|
$A(G) \le |V| \le 2 \cdot \OPT(G)$. \qed
|
|
|
|
\medskip
|
|
\textbf{(b) Kreisgraph $G_n$:} Ein minimales Edge Cover ist ein perfektes
|
|
Matching des Kreises: $\OPT(G_n) = n/2$ (jede Kante deckt 2 Knoten, $n$
|
|
Knoten). \emph{Schlechteste Ausführung:} Besuche die Knoten in der Reihenfolge
|
|
$1, 3, 4, 5, \dots, n$ und wähle: für 1 die Kante $\{1,2\}$, für 3 die Kante
|
|
$\{2,3\}$, für 4 die Kante $\{3,4\}$, \dots, für $n$ die Kante $\{n-1,n\}$ --
|
|
jede neue Kante deckt nur \emph{einen} neuen Knoten ab (der andere Endpunkt
|
|
war schon abgedeckt). Das ergibt $|C| = n - 1$ Kanten. Rate:
|
|
\[
|
|
\frac{n-1}{n/2} \;=\; 2 - \frac{2}{n} \;\longrightarrow\; 2 .
|
|
\]
|
|
|
|
\subsection{Lösung zu Selbsttest 7: Lower Bounds für $k$-\problem{Color}}\label{sol:kcolor}
|
|
|
|
\textbf{Parameter abschätzen:} Die Konstruktion erzeugt
|
|
\[
|
|
|V| = \underbrace{3n}_{x_i,\, \bar{x}_i,\, v_i} + \underbrace{m}_{C_j} +
|
|
\underbrace{1}_{z} = O(n + m) \subseteq O(m)
|
|
\quad (\text{da } n \le 3m).
|
|
\]
|
|
Kanten: $\{v_i, v_j\}$: $O(n^2)$; $\{v_i, x_j\}, \{v_i, \bar{x}_j\}$:
|
|
$O(n^2)$; $\{x_i, \bar{x}_i\}$: $n$; $\{x_i, C_j\}, \{\bar{x}_i, C_j\}$:
|
|
$O(nm)$; $\{v_i, z\}$, $\{C_j, z\}$: $O(n + m)$. Gesamt
|
|
$|E| = O(n^2 + nm + m) \subseteq O(m^2)$.
|
|
|
|
\medskip
|
|
\textbf{(i)} Kein $2^{o(|V|)} \cdot |I|^{O(1)}$ für $k$-\problem{Color}:
|
|
Sonst lieferte die Reduktion (mit $|V| = O(m)$) einen
|
|
$2^{o(m)}$-Algorithmus für 3-SAT -- nach dem Sparsification-Lemma nur
|
|
möglich, wenn die ETH falsch ist.
|
|
|
|
\medskip
|
|
\textbf{(ii)} Kein $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$:
|
|
Wegen $|E| = O(m^2)$ gilt $\sqrt{|E|} = O(m)$; ein solcher Algorithmus ergäbe
|
|
wieder $2^{o(m)}$ für 3-SAT -- ETH falsch (Wurzel-Regel).
|
|
|
|
\subsection{Lösung zu Selbsttest 8: Lower Bounds für \problem{Set Cover}}\label{sol:setcover}
|
|
|
|
\textbf{Parameter der konstruierten \problem{Hitting-Set}-Instanz:}
|
|
$|U'| = r$ (die Mengen-Indizes) und $r' = |U|$ (eine Menge $F_w'$ pro Element
|
|
$w \in U$); $k' = k$. Die Reduktion vertauscht also die Rollen von Elementen
|
|
und Mengen (Dualität über den bipartiten Inzidenzgraphen) und ist in
|
|
polynomieller Zeit berechenbar. Entscheidend: Sie ist eine \emph{Reduktion von
|
|
Set Cover auf Hitting Set} -- ein schneller Set-Cover-Algorithmus hilft so
|
|
nicht direkt. Die Schranken erhält man über die \emph{umgekehrte} Anwendung:
|
|
Dieselbe Konstruktion, auf eine \problem{Hitting-Set}-Instanz angewandt,
|
|
liefert eine \problem{Set-Cover}-Instanz (die Dualisierung ist involutorisch:
|
|
zweimal anwenden ergibt die Ausgangsinstanz). Also gilt
|
|
$\problem{Hitting Set} \redp \problem{Set Cover}$ mit $|U| = r'$ und
|
|
$r = |U'|$.
|
|
|
|
\medskip
|
|
\textbf{(i)} Kein $2^{o(|U|)} \cdot \langle I \rangle^{O(1)}$ für
|
|
\problem{Set Cover}: Sonst könnte man eine \problem{Hitting-Set}-Instanz
|
|
dualisieren ($|U| = r'$) und erhielte einen
|
|
$2^{o(r')}$-Algorithmus für \problem{Hitting Set} -- nach Voraussetzung nur
|
|
möglich, wenn die ETH falsch ist.
|
|
|
|
\medskip
|
|
\textbf{(ii)} Kein $2^{o(r)} \cdot \langle I \rangle^{O(1)}$:
|
|
analog mit $r = |U'|$ -- ein solcher Algorithmus ergäbe
|
|
$2^{o(|U'|)}$ für \problem{Hitting Set}, also ETH falsch.
|
|
|
|
\end{document}
|