3332 lines
130 KiB
Plaintext
3332 lines
130 KiB
Plaintext
\documentclass[11pt,a4paper]{article}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage{lmodern}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[margin=2.5cm]{geometry}
|
|
\usepackage{amsmath,amssymb}
|
|
\usepackage{tikz}
|
|
|
|
\setlength{\parskip}{0.4em}
|
|
\setlength{\parindent}{0pt}
|
|
\setcounter{tocdepth}{1}
|
|
\emergencystretch=1.5em
|
|
|
|
% ---- Makros ----
|
|
\newcommand{\problem}[1]{\textsc{#1}}
|
|
\newcommand{\redp}{\le_p}
|
|
\newcommand{\NP}{\textsf{NP}}
|
|
\newcommand{\true}{\textsf{wahr}}
|
|
\newcommand{\false}{\textsf{falsch}}
|
|
\tikzset{knoten/.style={circle,draw,thick,minimum size=6.5mm,inner sep=1pt}}
|
|
|
|
% ---- Aufgabenkopf: Nummer + Titel, duenne Linie, keine Farbe ----
|
|
\newcounter{aufg}
|
|
\newcommand{\aufg}[1]{\clearpage
|
|
\stepcounter{aufg}%
|
|
\addcontentsline{toc}{subsection}{\theaufg\ \ #1}%
|
|
\noindent{\large\textbf{\theaufg\quad #1}}\par\nobreak
|
|
\noindent\rule{\linewidth}{0.4pt}\par\medskip}
|
|
\newcommand{\lsg}{\par\medskip\noindent\rule{\linewidth}{0.4pt}\par\smallskip
|
|
\noindent\textbf{Lösung.}\par\smallskip}
|
|
|
|
\title{\textbf{\Huge Übungsaufgaben}\\[0.4em]
|
|
\large 71 Aufgaben nach Kompetenzliste\\
|
|
\normalsize \textit{Analyse von Algorithmen und Komplexität} -- CAU Kiel}
|
|
\author{}
|
|
\date{}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
\thispagestyle{empty}
|
|
\tableofcontents
|
|
|
|
\clearpage
|
|
\section{Anwendung}
|
|
% ==================================================================
|
|
\aufg{Greedy anwenden}
|
|
Rucksack mit Kapazität $B = 10$; Gegenstände als $(p_i, w_i)$:
|
|
\[
|
|
A = (10,6),\quad B = (7,5),\quad C = (6,4),\quad D = (3,3),\quad E = (4,2).
|
|
\]
|
|
Wenden Sie Greedy an und geben Sie den Lösungswert an.
|
|
|
|
\emph{Hinweis:} Greedy sortiert absteigend nach Profitdichte $p_i/w_i$ und
|
|
packt in dieser Reihenfolge jeden Gegenstand ein, der noch passt.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Dichten $p_i/w_i$: $A\,1{,}67$, $B\,1{,}4$, $C\,1{,}5$, $D\,1{,}0$,
|
|
$E\,2{,}0$. Sortiert: $E, A, C, B, D$.
|
|
\item $E\,(w{=}2)$ einpacken -- Restkapazität $8$.
|
|
\item $A\,(w{=}6)$ einpacken -- Restkapazität $2$.
|
|
\item $C\,(w{=}4)$ passt nicht.
|
|
\item $B\,(w{=}5)$ passt nicht.
|
|
\item $D\,(w{=}3)$ passt nicht.
|
|
\end{itemize}
|
|
Auswahl $\{E, A\}$, Lösungswert $\mathrm{GA} = 4 + 10 = 14$.
|
|
(Optimum wäre $\{A, C\}$ mit Wert $16$.) \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{ModifiedGreedy anwenden}
|
|
Rucksack mit Kapazität $B = 8$; Gegenstände $(p_i, w_i)$:
|
|
\[
|
|
a = (3,2),\quad b = (3,2),\quad c = (9,7),\quad d = (1,2).
|
|
\]
|
|
Wenden Sie ModifiedGreedy an. Wie ändert sich die Lösung gegenüber Greedy?
|
|
|
|
\emph{Hinweis:} ModifiedGreedy gibt das Bessere aus Greedy-Lösung und
|
|
profitreichstem Einzel-Gegenstand (der allein passt) aus.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Dichten: $a\,1{,}5$, $b\,1{,}5$, $c\,1{,}29$, $d\,0{,}5$. Reihenfolge
|
|
$a, b, c, d$.
|
|
\item Greedy: $a$ rein (Rest $6$), $b$ rein (Rest $4$), $c\,(w{=}7)$ passt
|
|
nicht, $d$ rein (Rest $2$). Greedy-Wert $\mathrm{GA} = 3+3+1 = 7$.
|
|
\item Profitreichster Einzel-Gegenstand: $c$ mit Profit $9$ (und $w = 7 \le
|
|
8$).
|
|
\item $\mathrm{MGA} = \max\{7,\ 9\} = 9$.
|
|
\end{itemize}
|
|
Die Lösung wechselt von der Greedy-Auswahl $\{a, b, d\}$ (Wert $7$) zum
|
|
einzelnen Gegenstand $c$ (Wert $9$). \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{Sahni anwenden}
|
|
Rucksack mit Kapazität $B = 11$; Gegenstände $(p_i, w_i)$:
|
|
\[
|
|
A = (5,4),\quad B = (6,5),\quad C = (7,6),\quad D = (4,6).
|
|
\]
|
|
Wenden Sie Sahni mit $k = 2$ an.
|
|
|
|
\emph{Hinweis:} Sahni probiert jede Vorauswahl aus höchstens $k$ Gegenständen,
|
|
füllt sie jeweils mit Greedy auf und gibt die beste gefundene Lösung aus; das
|
|
liefert Güte $1 + \frac1k$.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Reines Greedy (Dichten $A\,1{,}25$, $B\,1{,}2$, $C\,1{,}17$, $D\,0{,}67$):
|
|
$A$ rein (Rest $7$), $B$ rein (Rest $2$), $C$ und $D$ passen nicht -- Wert
|
|
$11$.
|
|
\item Vorauswahl $\{A, C\}$: Gewicht $4+6 = 10$, Greedy füllt nichts mehr
|
|
(Rest $1$) -- Wert $12$.
|
|
\item Vorauswahl $\{B, C\}$: Gewicht $5+6 = 11$, kein Platz mehr -- Wert
|
|
$6 + 7 = 13$.
|
|
\item Alle übrigen Vorauswahlen bleiben $\le 12$.
|
|
\end{itemize}
|
|
Beste Lösung: $\{B, C\}$ mit Wert $13$ (hier zugleich das Optimum).
|
|
\hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{ListScheduling anwenden}
|
|
$m = 3$ Maschinen; Jobs in gegebener Reihenfolge
|
|
$p = (3, 5, 2, 4, 1)$. Wenden Sie ListScheduling an.
|
|
|
|
\emph{Hinweis:} Jeder Job kommt der Reihe nach auf die aktuell am wenigsten
|
|
belastete Maschine; Lastvektor $(M_1, M_2, M_3)$.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Start $(0,0,0)$.
|
|
\item $3 \to M_1$: $(3,0,0)$.
|
|
\item $5 \to M_2$: $(3,5,0)$.
|
|
\item $2 \to M_3$: $(3,5,2)$.
|
|
\item $4 \to M_3$ (kleinste Last $2$): $(3,5,6)$.
|
|
\item $1 \to M_1$ (kleinste Last $3$): $(4,5,6)$.
|
|
\end{itemize}
|
|
Makespan $C_{\max} = 6$. \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{LPT anwenden}
|
|
$m = 3$ Maschinen; Jobs $p = (4, 2, 6, 3, 5, 1)$. Wenden Sie LPT an.
|
|
|
|
\emph{Hinweis:} LPT ist ListScheduling nach absteigender Sortierung der
|
|
Bearbeitungszeiten.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Absteigend sortiert: $6, 5, 4, 3, 2, 1$.
|
|
\item $6 \to M_1$: $(6,0,0)$; \quad $5 \to M_2$: $(6,5,0)$; \quad
|
|
$4 \to M_3$: $(6,5,4)$.
|
|
\item $3 \to M_3$ (kleinste Last $4$): $(6,5,7)$.
|
|
\item $2 \to M_2$ (kleinste Last $5$): $(6,7,7)$.
|
|
\item $1 \to M_1$ (kleinste Last $6$): $(7,7,7)$.
|
|
\end{itemize}
|
|
Makespan $C_{\max} = 7$; wegen $\sum_j p_j = 21 = 3 \cdot 7$ ist das zugleich
|
|
optimal. \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{RoundRobin anwenden}
|
|
$m = 2$ Maschinen; Jobs $p = (3, 6, 1, 4)$. Wenden Sie RoundRobin an.
|
|
|
|
\emph{Hinweis:} RoundRobin sortiert die Jobs absteigend und verteilt sie
|
|
reihum: der $j$-te sortierte Job kommt auf Maschine $((j-1) \bmod m) + 1$.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Absteigend sortiert: $6, 4, 3, 1$.
|
|
\item Reihum bei $m = 2$: $6 \to M_1$, $4 \to M_2$, $3 \to M_1$, $1 \to M_2$.
|
|
\item Lasten: $M_1 = 6 + 3 = 9$, \quad $M_2 = 4 + 1 = 5$.
|
|
\end{itemize}
|
|
Makespan $C_{\max} = 9$. (Optimal wäre $\{6,1\}$ / $\{4,3\}$ mit
|
|
$\mathrm{OPT} = 7$.) \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{Parallel-Task-Scheduling anwenden}
|
|
$m = 3$ Maschinen. Ein Job $(p_j, q_j)$ belegt $q_j$ Maschinen gleichzeitig
|
|
für Zeit $p_j$. Jobs in Reihenfolge:
|
|
\[
|
|
(2,1),\quad (2,2),\quad (1,3),\quad (3,1).
|
|
\]
|
|
Wenden Sie Parallel-Task-ListScheduling an.
|
|
|
|
\emph{Hinweis:} Jeder Job startet zum frühesten Zeitpunkt, an dem $q_j$
|
|
Maschinen frei sind, auf den $q_j$ am wenigsten belasteten Maschinen.
|
|
|
|
\lsg
|
|
Lastvektor $(M_1, M_2, M_3)$ als Fertigstellungszeiten; Start $(0,0,0)$.
|
|
\begin{itemize}
|
|
\item $(2,1)$: eine Maschine $M_1$ (Last $0$), Start $0$, läuft $[0,2]$ --
|
|
$(2,0,0)$.
|
|
\item $(2,2)$: zwei Maschinen $M_2, M_3$ (Last $0$), Start $0$, läuft $[0,2]$
|
|
-- $(2,2,2)$.
|
|
\item $(1,3)$: alle drei Maschinen, frühester Start $= \max = 2$, läuft
|
|
$[2,3]$ -- $(3,3,3)$.
|
|
\item $(3,1)$: leerste Maschine $M_1$ (Last $3$), Start $3$, läuft $[3,6]$ --
|
|
$(6,3,3)$.
|
|
\end{itemize}
|
|
Makespan $C_{\max} = 6$. \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{TSP1 anwenden}
|
|
Vollständiger, symmetrischer Graph $G$ auf $\{A,B,C,D,E\}$; die
|
|
Dreiecksungleichung gilt für jede Kante. Wenden Sie $\Delta$TSP1 ab
|
|
Startknoten $A$ an; geben Sie alle Zwischenschritte und die Tourlänge an.
|
|
\begin{center}
|
|
\begin{tikzpicture}
|
|
\node[knoten] (A) at ( 90:2.1) {$A$};
|
|
\node[knoten] (B) at ( 18:2.1) {$B$};
|
|
\node[knoten] (C) at ( -54:2.1) {$C$};
|
|
\node[knoten] (D) at (-126:2.1) {$D$};
|
|
\node[knoten] (E) at ( 162:2.1) {$E$};
|
|
\draw (A) -- (B) node[fill=white,inner sep=1pt,font=\small,midway] {2};
|
|
\draw (B) -- (C) node[fill=white,inner sep=1pt,font=\small,midway] {1};
|
|
\draw (C) -- (D) node[fill=white,inner sep=1pt,font=\small,midway] {2};
|
|
\draw (D) -- (E) node[fill=white,inner sep=1pt,font=\small,midway] {1};
|
|
\draw (E) -- (A) node[fill=white,inner sep=1pt,font=\small,midway] {4};
|
|
\draw (A) -- (C) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {1};
|
|
\draw (A) -- (D) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3};
|
|
\draw (B) -- (D) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3};
|
|
\draw (B) -- (E) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {4};
|
|
\draw (C) -- (E) node[fill=white,inner sep=1pt,font=\small,pos=0.28] {3};
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
|
|
\emph{Hinweis ($\Delta$TSP1):} (1) MST $T$ berechnen; (2) alle MST-Kanten
|
|
verdoppeln; (3) Eulerkreis ab Startknoten; (4) Abkürzen -- bereits besuchte
|
|
Knoten überspringen. Güte $2$.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item[(1)] MST (Kruskal, aufsteigend): $A$--$C\,(1)$, $B$--$C\,(1)$,
|
|
$D$--$E\,(1)$, $C$--$D\,(2)$; Gewicht $5$. Knoten $C$ hat Grad $3$.
|
|
\item[(2)] Verdoppeln: alle Grade werden gerade, Multigraph-Gewicht $10$.
|
|
\item[(3)] Eulerkreis ab $A$: $[A, C, B, C, D, E, D, C, A]$.
|
|
\item[(4)] Abkürzen (besuchte Knoten überspringen): Tour
|
|
$[A, C, B, D, E, A]$.
|
|
\end{itemize}
|
|
Tourlänge $= AC + CB + BD + DE + EA = 1 + 1 + 3 + 1 + 4 = 10$.
|
|
\hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{Christofides anwenden}
|
|
Vollständiger, symmetrischer Graph $G$ auf $\{a,b,c,d\}$; die
|
|
Dreiecksungleichung gilt für jede Kante. Wenden Sie Christofides
|
|
($\Delta$TSP2) ab Startknoten $a$ an; geben Sie alle Zwischenschritte und die
|
|
Tourlänge an.
|
|
\begin{center}
|
|
\begin{tikzpicture}
|
|
\node[knoten] (a) at (0,2.4) {$a$};
|
|
\node[knoten] (b) at (2.4,2.4) {$b$};
|
|
\node[knoten] (c) at (0,0) {$c$};
|
|
\node[knoten] (d) at (2.4,0) {$d$};
|
|
\draw (a) -- (b) node[fill=white,inner sep=1pt,font=\small,midway] {1};
|
|
\draw (a) -- (c) node[fill=white,inner sep=1pt,font=\small,midway] {2};
|
|
\draw (b) -- (d) node[fill=white,inner sep=1pt,font=\small,midway] {3};
|
|
\draw (c) -- (d) node[fill=white,inner sep=1pt,font=\small,midway] {3};
|
|
\draw (a) -- (d) node[fill=white,inner sep=1pt,font=\small,pos=0.3] {2};
|
|
\draw (b) -- (c) node[fill=white,inner sep=1pt,font=\small,pos=0.3] {3};
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
|
|
\emph{Hinweis (Christofides):} (1) MST $T$ berechnen; (2) $X = $ Knoten mit
|
|
ungeradem Grad in $T$; (3) minimales perfektes Matching $K$ auf $X$;
|
|
(4) Eulerkreis in $T + K$; (5) Abkürzen. Güte $\frac32$.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item[(1)] MST (Kruskal): $a$--$b\,(1)$, $a$--$c\,(2)$, $a$--$d\,(2)$;
|
|
Gewicht $5$ (Stern um $a$).
|
|
\item[(2)] Grade im MST: $a{:}\,3$, $b{:}\,1$, $c{:}\,1$, $d{:}\,1$ -- alle
|
|
ungerade, also $X = \{a,b,c,d\}$.
|
|
\item[(3)] Minimales perfektes Matching auf $X$: Kandidaten
|
|
$\{a b, c d\} = 1 + 3 = 4$, $\{a c, b d\} = 2 + 3 = 5$,
|
|
$\{a d, b c\} = 2 + 3 = 5$. Wähle $K = \{\{a,b\}, \{c,d\}\}$, Kosten $4$.
|
|
\item[(4)] Multigraph $T + K$ (Kante $a$--$b$ doppelt): alle Grade gerade.
|
|
Eulerkreis ab $a$: $[a, b, a, c, d, a]$.
|
|
\item[(5)] Abkürzen: Tour $[a, b, c, d, a]$.
|
|
\end{itemize}
|
|
Tourlänge $= ab + bc + cd + da = 1 + 3 + 3 + 2 = 9$. \hfill$\square$
|
|
|
|
% ==================================================================
|
|
\aufg{Strip Packing: NFDH anwenden}
|
|
Streifen der Breite $1$. Rechtecke als $(\text{Breite}, \text{Höhe})$:
|
|
\[
|
|
r_1 = (0{,}6,\,3),\ r_2 = (0{,}5,\,2),\ r_3 = (0{,}5,\,2),\
|
|
r_4 = (0{,}4,\,1),\ r_5 = (0{,}3,\,1).
|
|
\]
|
|
Wenden Sie NFDH an und geben Sie die Gesamthöhe an.
|
|
|
|
\emph{Hinweis:} NFDH sortiert nach Höhe absteigend und packt stufenweise von
|
|
links; passt ein Rechteck nicht mehr, beginnt eine neue Stufe darüber. Die
|
|
Stufenhöhe ist die Höhe ihres ersten (höchsten) Rechtecks.
|
|
|
|
\lsg
|
|
\begin{itemize}
|
|
\item Sortiert nach Höhe: $r_1\,(3), r_2\,(2), r_3\,(2), r_4\,(1), r_5\,(1)$.
|
|
\item Stufe 1: $r_1$ (Breite $0{,}6$, Höhe $3$). $r_2$: $0{,}6 + 0{,}5 =
|
|
1{,}1 > 1$ -- passt nicht.
|
|
\item Stufe 2: $r_2$ (Höhe $2$), Breite $0{,}5$. $r_3$: $0{,}5 + 0{,}5 = 1{,}0
|
|
\le 1$ -- passt. $r_4$: $1{,}0 + 0{,}4 > 1$ -- passt nicht.
|
|
\item Stufe 3: $r_4$ (Höhe $1$), Breite $0{,}4$. $r_5$: $0{,}4 + 0{,}3 = 0{,}7
|
|
\le 1$ -- passt.
|
|
\end{itemize}
|
|
Gesamthöhe $\mathrm{NFDH} = 3 + 2 + 1 = 6$.
|
|
\begin{center}
|
|
\begin{tikzpicture}[x=3.4cm,y=0.5cm]
|
|
\draw[thin] (0,6.4) -- (0,0) -- (1,0) -- (1,6.4);
|
|
\draw[fill=black!20] (0,0) rectangle (0.6,3); \node at (0.3,1.5) {$r_1$};
|
|
\draw[fill=black!12] (0,3) rectangle (0.5,5); \node at (0.25,4) {$r_2$};
|
|
\draw[fill=black!20] (0.5,3) rectangle (1.0,5); \node at (0.75,4) {$r_3$};
|
|
\draw[fill=black!12] (0,5) rectangle (0.4,6); \node at (0.2,5.5) {\small $r_4$};
|
|
\draw[fill=black!20] (0.4,5) rectangle (0.7,6); \node at (0.55,5.5) {\small $r_5$};
|
|
\draw[dashed,thin] (0,6) -- (1,6);
|
|
\node[right,font=\small] at (1.03,6) {$\mathrm{NFDH} = 6$};
|
|
\node[below,font=\small] at (0.5,-0.4) {Breite $1$};
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
Die Gesamtfläche ist $4{,}5$ (untere Schranke $\mathrm{OPT} \ge 4{,}5$); eine
|
|
Packung der Höhe $5$ existiert. \hfill$\square$
|
|
|
|
% ==================================================================
|
|
|
|
\clearpage
|
|
\section{Vorlesungsbeweis}
|
|
\aufg{$P \subseteq \NP$ zeigen}
|
|
Zeigen Sie: $P \subseteq \NP$.
|
|
\lsg
|
|
Sei $L \in P$ beliebig. Dann entscheidet ein Algorithmus $A$ die Sprache $L$
|
|
in Zeit $O(n^d)$.
|
|
|
|
\textbf{Konstruktion:} Fasse $A$ als Verifizierer auf durch $V(x,c) := A(x)$;
|
|
das Zertifikat $c$ wird ignoriert.
|
|
|
|
\textbf{Korrektheit:} Ist $x \in L$, so akzeptiert $V(x,c)$ für jedes $c$,
|
|
etwa $c = \varepsilon$ -- ein akzeptiertes Zertifikat existiert. Ist
|
|
$x \notin L$, so verwirft $V(x,c)$ für jedes $c$ -- kein Zertifikat wird
|
|
akzeptiert. Also $L = \{x \mid \exists c:\ V(x,c) = 1\}$.
|
|
|
|
\textbf{Laufzeit:} $V$ läuft wie $A$ in $O(n^d)$. Damit ist $V$ ein
|
|
Verifizierer für $L$, und $L \in \NP$. Da $L$ beliebig war, folgt
|
|
$P \subseteq \NP$. \hfill$\square$
|
|
|
|
\aufg{NDTM-Definition $\subseteq$ Verifizierer-Definition zeigen}
|
|
Sei $L$ eine Sprache, die von einer NDTM $M$ in nichtdeterministischer Zeit
|
|
$T$ (ein Polynom) entschieden wird. Zeigen Sie, dass ein polynomieller
|
|
Verifizierer für $L$ existiert.
|
|
\lsg
|
|
Eingabe: Wort $x$ und als Zertifikat eine Folge $c$ von höchstens $T(|x|)$
|
|
nichtdeterministischen Entscheidungen von $M$.
|
|
|
|
Der Verifizierer $V(x,c)$ arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Simuliere $M$ auf $x$ deterministisch für höchstens $T(|x|)$ Schritte.
|
|
\item Wähle an jeder Verzweigung den Übergang, den die Folge $c$ vorgibt.
|
|
\item Akzeptiere, falls die Simulation akzeptierend hält; sonst verwirf.
|
|
\end{itemize}
|
|
|
|
\textbf{Korrektheit:} Ist $x \in L$, so hat $M$ einen akzeptierenden
|
|
Rechenweg mit höchstens $T(|x|)$ Schritten; dessen Entscheidungsfolge ist ein
|
|
Zertifikat, das $V$ akzeptiert. Ist $x \notin L$, so akzeptiert kein Rechenweg
|
|
von $M$; jede Folge $c$ steuert die Simulation einen Rechenweg entlang, also
|
|
verwirft $V$ jedes Zertifikat.
|
|
|
|
\textbf{Laufzeit:} Höchstens $T(|x|)$ Simulationsschritte mit konstantem
|
|
Aufwand -- $O(T(|x|))$; das Zertifikat hat Länge höchstens $T(|x|)$. Also
|
|
existiert ein polynomieller Verifizierer für $L$. \hfill$\square$
|
|
|
|
\aufg{Verifizierer-Definition $\subseteq$ NDTM-Definition zeigen}
|
|
Sei $L$ eine Sprache mit polynomiellem Verifizierer $M$ (Laufzeit
|
|
$O(|x|^d)$): Für $x \in L$ existiert ein Zertifikat $c$ mit $M(x,c) = 1$, für
|
|
$x \notin L$ akzeptiert $M$ kein Zertifikat. Zeigen Sie, dass eine NDTM $N$
|
|
die Sprache $L$ in Polynomialzeit entscheidet.
|
|
\lsg
|
|
Sei $p(|x|) = O(|x|^d)$ die Laufzeit von $M$. In $p(|x|)$ Schritten liest $M$
|
|
höchstens $p(|x|)$ Zeichen des Zertifikats.
|
|
|
|
Die NDTM $N$ arbeitet bei Eingabe $x$ in zwei Phasen:
|
|
\begin{itemize}
|
|
\item \emph{Raten:} Schreibe mit nichtdeterministischen Entscheidungen einen
|
|
String $u$ mit $|u| \le p(|x|)$ auf ein Arbeitsband.
|
|
\item \emph{Verifizieren:} Simuliere $M$ auf $(x,u)$ und übernimm dessen
|
|
Antwort.
|
|
\end{itemize}
|
|
|
|
\textbf{Korrektheit:} Ist $x \in L$, so existiert ein Zertifikat $c$ mit
|
|
$M(x,c) = 1$; $M$ liest davon höchstens die ersten $p(|x|)$ Zeichen. Der
|
|
Rechenweg, der genau diesen Anfang als $u$ rät, akzeptiert -- also akzeptiert
|
|
$N$. Ist $x \notin L$, so verwirft $M$ jedes geratene $u$; alle Rechenwege
|
|
verwerfen -- also verwirft $N$.
|
|
|
|
\textbf{Laufzeit:} Phase~1 braucht $p(|x|)$ Rateschritte, Phase~2 läuft in
|
|
$O(|x|^d)$ -- gesamt $O(|x|^d)$. Also entscheidet $N$ die Sprache $L$ in
|
|
nichtdeterministischer Polynomialzeit. \hfill$\square$
|
|
|
|
\aufg{Transitivität von Polynomialzeitreduktionen zeigen}
|
|
Zeigen Sie: Für Entscheidungsprobleme $L_1, L_2, L_3$ folgt aus
|
|
$L_1 \redp L_2$ und $L_2 \redp L_3$ auch $L_1 \redp L_3$.
|
|
\lsg
|
|
Sei $R_1$ eine Reduktion $L_1 \redp L_2$ mit Laufzeit $O(n^a)$ und $R_2$ eine
|
|
Reduktion $L_2 \redp L_3$ mit Laufzeit $O(n^b)$. Setze $R := R_2 \circ R_1$.
|
|
|
|
\textbf{Korrektheit:} Für jede Eingabe $x$ gilt
|
|
\[
|
|
x \in L_1 \iff R_1(x) \in L_2 \iff R_2(R_1(x)) \in L_3,
|
|
\]
|
|
also $x \in L_1 \iff R(x) \in L_3$.
|
|
|
|
\textbf{Laufzeit:} Sei $|x| = n$.
|
|
\begin{itemize}
|
|
\item $R_1(x)$ braucht $O(n^a)$ Zeit; die Ausgabe hat damit Größe $O(n^a)$.
|
|
\item $R_2$ auf dieser Ausgabe braucht $O((n^a)^b) = O(n^{ab})$ Zeit.
|
|
\end{itemize}
|
|
Somit ist $R$ eine Reduktion $L_1 \redp L_3$ mit Laufzeit $O(n^{ab})$.
|
|
\hfill$\square$
|
|
|
|
\aufg{Vererbung der NP-Vollständigkeit zeigen}
|
|
Zeigen Sie: Ist $L_0$ NP-vollständig, gilt $L_0 \redp L_1$ und ist
|
|
$L_1 \in \NP$, so ist auch $L_1$ NP-vollständig.
|
|
\emph{Hinweis:} Die Relation $\redp$ ist transitiv.
|
|
\lsg
|
|
$L_1 \in \NP$ gilt nach Voraussetzung. Zu zeigen bleibt, dass $L_1$
|
|
NP-schwer ist, also $L \redp L_1$ für jedes $L \in \NP$.
|
|
|
|
Sei $L \in \NP$ beliebig.
|
|
\begin{itemize}
|
|
\item Da $L_0$ NP-vollständig ist, gilt $L \redp L_0$.
|
|
\item Nach Voraussetzung gilt $L_0 \redp L_1$.
|
|
\item Da $\redp$ transitiv ist, folgt $L \redp L_1$.
|
|
\end{itemize}
|
|
$L$ war beliebig, also reduziert jedes NP-Problem auf $L_1$ -- $L_1$ ist
|
|
NP-schwer. Zusammen mit $L_1 \in \NP$ ist $L_1$ NP-vollständig.
|
|
\hfill$\square$
|
|
|
|
\aufg{$L$ NP-vollständig: $L \in P \Leftrightarrow P = \NP$ zeigen}
|
|
Sei $L$ eine NP-vollständige Sprache. Beweisen Sie: $L \in P$ genau dann,
|
|
wenn $P = \NP$.
|
|
\lsg
|
|
\textbf{$\Leftarrow$:} Sei $P = \NP$. $L$ ist NP-vollständig, also
|
|
$L \in \NP = P$.
|
|
|
|
\textbf{$\Rightarrow$:} Sei $L \in P$. $P \subseteq \NP$ gilt stets. Zu
|
|
zeigen bleibt $\NP \subseteq P$.
|
|
|
|
Sei $L' \in \NP$ beliebig. Da $L$ NP-vollständig ist, gibt es eine Reduktion
|
|
$f$ mit $L' \redp L$ und Laufzeit $O(n^a)$. Sei $A$ ein Algorithmus, der $L$
|
|
in Zeit $O(n^c)$ entscheidet.
|
|
|
|
So entscheidet man $L'$: Berechne $f(x)$ und wende $A$ darauf an. Das ist
|
|
korrekt, denn $x \in L' \iff f(x) \in L$. Die Ausgabe $f(x)$ hat Größe
|
|
$O(n^a)$, also braucht $A$ darauf $O((n^a)^c) = O(n^{ac})$ Zeit.
|
|
|
|
Also gilt $L' \in P$ für jedes $L' \in \NP$, und mit $P \subseteq \NP$ folgt
|
|
$P = \NP$. \hfill$\square$
|
|
|
|
\clearpage
|
|
\section{NP-Vollständigkeit}
|
|
\aufg{NP-Vollständigkeit zeigen für $k$-Clique}
|
|
Beweisen Sie, dass $k$-\problem{Clique} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie allgemeines \problem{SAT} (nicht 3-SAT).
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$C \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C| < k$, lehne ab.
|
|
\item Prüfe für jedes Paar $\{u,v\} \subseteq C$, ob $\{u,v\} \in E$; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine $k$-Clique, so ist sie ein akzeptiertes Zertifikat; sonst
|
|
verletzt jedes Zertifikat eine Prüfung. Laufzeit: Größe zählen $O(|V|)$, alle
|
|
Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt
|
|
$k$-\problem{Clique} $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SAT} \redp k\text{-}\problem{Clique}.
|
|
\] \problem{SAT} ist bereits als
|
|
NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $F = F_1 \wedge \dots \wedge F_m$ eine KNF-Formel;
|
|
$y_{ij}$ sei das $j$-te Literal von Klausel $F_i$. Wir konstruieren daraus
|
|
eine $k$-\problem{Clique}-Instanz durch:
|
|
\begin{itemize}
|
|
\item $V = \{[i,j] \mid y_{ij} \text{ ist Literal in } F_i\}$
|
|
\item $E = \{\{[i,j],[i',j']\} \mid i \ne i',\ y_{ij} \ne \neg y_{i'j'}\}$
|
|
\item $k = m$
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $\psi$ eine erfüllende Belegung von $F$.
|
|
\item In jeder Klausel $F_i$ ist ein Literal wahr; wähle je eines, Knoten
|
|
$[i,j_i]$.
|
|
\item Sei $C = \{[i,j_i] \mid i \in [m]\}$; die $m$ Knoten stammen aus
|
|
verschiedenen Klauseln.
|
|
\item Zwei gewählte Literale sind beide unter $\psi$ wahr, widersprechen sich
|
|
also nicht.
|
|
\item Somit sind ihre Knoten durch eine Kante verbunden.
|
|
\item Also ist $C$ eine $m$-Clique.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine $m$-Clique in $G$.
|
|
\item Knoten derselben Klausel sind nie verbunden, also enthält $C$ aus jeder
|
|
Klausel genau einen Knoten.
|
|
\item Die zugehörigen Literale widersprechen sich paarweise nicht (sonst
|
|
fehlte eine Kante).
|
|
\item Setze diese Literale wahr -- eine widerspruchsfreie Belegung.
|
|
\item Sie erfüllt in jeder Klausel ein Literal.
|
|
\item Also ist $F$ erfüllbar.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Sei $L$ die Zahl der Literalvorkommen. Knoten anlegen
|
|
$O(L)$, Kantenpaare prüfen $O(L^2)$ -- gesamt $O(L^2)$.
|
|
|
|
Da $k$-\problem{Clique} $\in \NP$ und NP-schwer ist, folgt:
|
|
$k$-\problem{Clique} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für 3-SAT}
|
|
Beweisen Sie, dass \problem{3-SAT} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{SAT} auf \problem{3-SAT}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: KNF-Formel $F$ mit Klauseln der Länge $\le 3$ und
|
|
Zertifikat $\beta$ (eine Belegung der Variablen). Der Verifizierer arbeitet
|
|
wie folgt:
|
|
\begin{itemize}
|
|
\item Werte jede Klausel unter $\beta$ aus.
|
|
\item Lehne ab, falls eine Klausel unerfüllt ist.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine erfüllende Belegung, so ist sie ein akzeptiertes Zertifikat;
|
|
sonst scheitert jede. Laufzeit: alle Klauseln auswerten $O(|F|)$ -- gesamt
|
|
$O(|F|)$. Also gilt $\problem{3-SAT} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SAT} \redp \problem{3-SAT}.
|
|
\] \problem{SAT} ist bereits als
|
|
NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Ersetze jede Klausel $(y_1 \vee \dots \vee y_\ell)$
|
|
mit $\ell > 3$ durch die Kette
|
|
\[
|
|
(y_1 \vee y_2 \vee x_1) \wedge (\neg x_1 \vee y_3 \vee x_2) \wedge \dots
|
|
\wedge (\neg x_{\ell-3} \vee y_{\ell-1} \vee y_\ell)
|
|
\]
|
|
mit neuen Hilfsvariablen $x_1, \dots, x_{\ell-3}$ (pro Klausel eigene).
|
|
Klauseln mit $\ell \le 3$ bleiben unverändert.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei die Originalklausel erfüllt, etwa $y_i$ wahr.
|
|
\item Setze $x_1 = \dots = x_{i-2} = \true$ und
|
|
$x_{i-1} = \dots = x_{\ell-3} = \false$.
|
|
\item Die Kettenklauseln links von $y_i$ sind durch ihr positives $x$-Literal
|
|
erfüllt.
|
|
\item Die Klausel mit $y_i$ ist durch $y_i$ erfüllt.
|
|
\item Die Kettenklauseln rechts sind durch ihr Literal $\neg x$ erfüllt.
|
|
\item Also ist die ganze Kette erfüllt.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei die Kette erfüllt, aber angenommen, alle $y_i$ seien falsch.
|
|
\item Dann erzwingt die erste Klausel $x_1 = \true$, die zweite
|
|
$x_2 = \true$, induktiv $x_{\ell-3} = \true$.
|
|
\item Dann ist die letzte Klausel
|
|
$(\neg x_{\ell-3} \vee y_{\ell-1} \vee y_\ell)$ falsch -- Widerspruch.
|
|
\item Also ist ein $y_i$ wahr und die Originalklausel erfüllt.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Jede Klausel der Länge $\ell$ wird zu $\ell-2$ Klauseln --
|
|
gesamt $O(|F|)$.
|
|
|
|
Da $\problem{3-SAT} \in \NP$ und NP-schwer ist, folgt: \problem{3-SAT} ist
|
|
NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für VertexCover}
|
|
Beweisen Sie, dass \problem{VertexCover} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{Clique}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$C \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C| > k$, lehne ab.
|
|
\item Prüfe für jede Kante $\{u,v\} \in E$, ob $u \in C$ oder $v \in C$;
|
|
lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert ein Vertex Cover der Größe $\le k$, so ist es ein akzeptiertes
|
|
Zertifikat; sonst bleibt eine Kante ungedeckt. Laufzeit: Größe zählen
|
|
$O(|V|)$, Kanten prüfen $O(|E|)$ -- gesamt $O(|V| + |E|)$. Also gilt
|
|
$\problem{VertexCover} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{Clique} \redp \problem{VertexCover}.
|
|
\] \problem{Clique} ist bereits
|
|
als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz
|
|
mit $n = |V|$. Wir konstruieren daraus eine \problem{VertexCover}-Instanz
|
|
$(G' = (V, E'),\, k')$ durch:
|
|
\begin{itemize}
|
|
\item $E' = \binom{V}{2} \setminus E$
|
|
\item $k' = n - k$
|
|
\end{itemize}
|
|
Damit ist $G'$ der Komplementgraph von $G$.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine Clique in $G$ mit $|C| \ge k$.
|
|
\item Setze $W = V \setminus C$; dann gilt $|W| \le n - k = k'$.
|
|
\item Alle Kanten innerhalb $C$ liegen in $E$, also enthält $E'$ keine Kante
|
|
mit beiden Endpunkten in $C$.
|
|
\item Somit hat jede Kante von $G'$ einen Endpunkt in $W$.
|
|
\item Also ist $W$ ein Vertex Cover von $G'$ mit $|W| \le k'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $W$ ein Vertex Cover von $G'$ mit $|W| \le k'$.
|
|
\item Setze $C = V \setminus W$; dann gilt $|C| \ge n - k' = k$.
|
|
\item Für $\{u,v\} \subseteq C$ gilt $u,v \notin W$, also $\{u,v\} \notin E'$.
|
|
\item Da $E'$ genau die Nicht-Kanten von $G$ enthält, gilt $\{u,v\} \in E$.
|
|
\item Also ist $C$ eine Clique in $G$ mit $|C| \ge k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Alle Knotenpaare durchgehen und die Kanten invertieren --
|
|
$O(|V|^2)$.
|
|
|
|
Da $\problem{VertexCover} \in \NP$ und NP-schwer ist, folgt:
|
|
\problem{VertexCover} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für CliqueAndIndependentSet}
|
|
\textbf{Problem \problem{CliqueAndIndependentSet}:} Gegeben ein Graph
|
|
$G = (V,E)$ und $k$. Enthält $G$ zugleich eine Clique der Größe $k$ und ein
|
|
Independent Set der Größe $k$ (eine Knotenmenge ohne Kanten untereinander)?
|
|
Beweisen Sie, dass \problem{CliqueAndIndependentSet} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{Clique}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$(C, I)$ mit $C, I \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C| < k$ oder $|I| < k$, lehne ab.
|
|
\item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne
|
|
sonst ab.
|
|
\item Prüfe für jedes Paar $\{x,y\} \subseteq I$, ob $\{x,y\} \notin E$; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert beides, so ist $(C,I)$ ein akzeptiertes Zertifikat; sonst scheitert
|
|
eine Prüfung. Laufzeit: alle Paare in $C$ und $I$ testen -- $O(|V|^2)$.
|
|
Also gilt $\problem{CliqueAndIndependentSet} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{Clique} \redp \problem{CliqueAndIndependentSet}.
|
|
\] \problem{Clique}
|
|
ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz,
|
|
o.B.d.A.\ $k \ge 2$. Wir konstruieren daraus eine
|
|
\problem{CliqueAndIndependentSet}-Instanz $(G' = (V', E'),\, k)$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{u_1, \dots, u_k\}$ mit $k$ neuen isolierten Knoten
|
|
\item $E' = E$
|
|
\item $k$ bleibt unverändert
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine $k$-Clique in $G$.
|
|
\item Da keine Kanten entfernt wurden, ist $C$ auch eine $k$-Clique in $G'$.
|
|
\item Die Knoten $u_1, \dots, u_k$ sind isoliert, also paarweise nicht
|
|
adjazent.
|
|
\item Somit ist $\{u_1, \dots, u_k\}$ ein Independent Set der Größe $k$.
|
|
\item Also enthält $G'$ eine $k$-Clique und ein Independent Set der Größe $k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $(G', k)$ eine Ja-Instanz; dann enthält $G'$ eine $k$-Clique $C'$.
|
|
\item Wegen $k \ge 2$ hat jeder Knoten von $C'$ einen Nachbarn in $C'$.
|
|
\item Die $u_1, \dots, u_k$ sind isoliert, liegen also nicht in $C'$.
|
|
\item Somit gilt $C' \subseteq V$.
|
|
\item Also ist $C'$ eine $k$-Clique in $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} $k$ isolierte Knoten anhängen -- $O(k) \subseteq O(|V|)$.
|
|
|
|
Da $\problem{CliqueAndIndependentSet} \in \NP$ und NP-schwer ist, folgt:
|
|
\problem{CliqueAndIndependentSet} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $k$-CliqueUniversal}
|
|
\textbf{Problem $k$-\problem{CliqueUniversal}:} Gegeben ein Graph
|
|
$G = (V,E)$ und $k$, wobei ein Knoten $u \in V$ mit allen anderen verbunden
|
|
ist. Enthält $G$ eine Clique der Größe $\ge k$? Beweisen Sie, dass
|
|
$k$-\problem{CliqueUniversal} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{Clique}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$C \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C| < k$, lehne ab.
|
|
\item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine $k$-Clique, so ist sie ein akzeptiertes Zertifikat; sonst
|
|
verletzt jedes Zertifikat eine Prüfung. Laufzeit: Größe zählen $O(|V|)$, alle
|
|
Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt
|
|
$k$-\problem{CliqueUniversal} $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{Clique} \redp k\text{-}\problem{CliqueUniversal}.
|
|
\] \problem{Clique}
|
|
ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz.
|
|
Wir konstruieren daraus eine $k$-\problem{CliqueUniversal}-Instanz
|
|
$(\bar G = (\bar V, \bar E),\, \bar k)$ durch:
|
|
\begin{itemize}
|
|
\item $\bar V = V \cup \{u\}$ mit einem neuen Knoten $u$
|
|
\item $\bar E = E \cup \{\{u,v\} \mid v \in V\}$
|
|
\item $\bar k = k + 1$
|
|
\end{itemize}
|
|
Der Knoten $u$ ist mit allen anderen verbunden, also ist $(\bar G, \bar k)$
|
|
eine gültige Instanz.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine Clique in $G$ mit $|C| \ge k$.
|
|
\item $u$ ist mit allen Knoten von $C$ verbunden.
|
|
\item Somit ist $C \cup \{u\}$ eine Clique in $\bar G$.
|
|
\item Also gilt $|C \cup \{u\}| \ge k + 1 = \bar k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $\bar C$ eine Clique in $\bar G$ mit $|\bar C| \ge \bar k$.
|
|
\item Setze $C = \bar C \setminus \{u\}$; dann gilt $|C| \ge \bar k - 1 = k$.
|
|
\item Alle Kanten zwischen Knoten von $C$ liegen in $E$, denn neu sind nur
|
|
Kanten an $u$.
|
|
\item Also ist $C$ eine Clique in $G$ mit $|C| \ge k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Einen Knoten und $|V|$ Kanten anlegen -- $O(|V|)$.
|
|
|
|
Da $k$-\problem{CliqueUniversal} $\in \NP$ und NP-schwer ist, folgt:
|
|
$k$-\problem{CliqueUniversal} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für Clique-Nomember}
|
|
\textbf{Problem \problem{Clique-Nomember}:} Gegeben ein Graph $G = (V,E)$,
|
|
ein Knoten $v \in V$ und $k$. Gibt es eine $k$-Clique, die $v$ \emph{nicht}
|
|
enthält? Beweisen Sie, dass \problem{Clique-Nomember} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{Clique}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Knoten $v$, Zahl $k$ und
|
|
Zertifikat $C \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C| < k$ oder $v \in C$, lehne ab.
|
|
\item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine $k$-Clique ohne $v$, so ist sie ein akzeptiertes Zertifikat;
|
|
sonst scheitert eine Prüfung. Laufzeit: Größe und Ausschluss prüfen $O(|V|)$,
|
|
alle Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt
|
|
$\problem{Clique-Nomember} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{Clique} \redp \problem{Clique-Nomember}.
|
|
\] \problem{Clique} ist
|
|
bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{Clique}-Instanz.
|
|
Wir konstruieren daraus eine \problem{Clique-Nomember}-Instanz
|
|
$(G' = (V', E'),\, v,\, k)$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{v\}$ mit einem neuen, isolierten Knoten $v \notin V$
|
|
\item $E' = E$
|
|
\item $k$ bleibt unverändert
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine $k$-Clique in $G$.
|
|
\item Da keine Kanten entfernt wurden, ist $C$ auch eine $k$-Clique in $G'$.
|
|
\item Da $v \notin V$, gilt $v \notin C$.
|
|
\item Also ist $C$ eine $k$-Clique in $G'$, die $v$ nicht enthält.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $C$ eine $k$-Clique in $G'$ mit $v \notin C$.
|
|
\item Dann gilt $C \subseteq V$, denn $v$ ist der einzige neue Knoten.
|
|
\item Alle Kanten zwischen Knoten von $C$ liegen in $E$.
|
|
\item Also ist $C$ eine $k$-Clique in $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Graph kopieren und einen isolierten Knoten anhängen --
|
|
$O(|V| + |E|)$.
|
|
|
|
Da $\problem{Clique-Nomember} \in \NP$ und NP-schwer ist, folgt:
|
|
\problem{Clique-Nomember} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $k$-Color}
|
|
\textbf{Problem $k$-\problem{Color}:} Gegeben ein Graph $G = (V,E)$ und
|
|
$k \in \mathbb{N}$. Gibt es eine Färbung $f\colon V \to \{1, \dots, k\}$ mit
|
|
$f(u) \ne f(v)$ für alle $\{u,v\} \in E$? Beweisen Sie, dass
|
|
$k$-\problem{Color} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{3-SAT}; o.B.d.A.\ enthält keine
|
|
Klausel ein Paar $x, \neg x$.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G$, Zahl $k$ und Zertifikat
|
|
$f\colon V \to \{1, \dots, k\}$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jede Kante $\{u,v\} \in E$, ob $f(u) \ne f(v)$ gilt; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine $k$-Färbung, wird ihr Zertifikat akzeptiert; sonst scheitert
|
|
jedes an einer Kante. Kanten prüfen -- $O(|V| + |E|)$. Also gilt
|
|
$k$-\problem{Color} $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{3-SAT} \redp k\text{-}\problem{Color}.
|
|
\]
|
|
\problem{3-SAT} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $F = F_1 \wedge \dots \wedge F_m$ über
|
|
$x_1, \dots, x_n$. Wir konstruieren $G$ und $k = n+1$ durch:
|
|
\begin{itemize}
|
|
\item Knoten: $x_i, \bar{x}_i, v_i$ für $i \in [n]$; $F_j$ für $j \in [m]$;
|
|
$z$
|
|
\item $\{v_i, v_j\}$ für $i \ne j$ und $\{v_i, z\}$ -- die $v_i$ und $z$
|
|
bilden eine $(n{+}1)$-Clique
|
|
\item $\{v_i, x_j\}$ und $\{v_i, \bar{x}_j\}$ für $i \ne j$
|
|
\item $\{x_i, \bar{x}_i\}$ für alle $i$
|
|
\item $\{F_j, y\}$ für jedes Literal $y$, das \emph{nicht} in $F_j$ vorkommt
|
|
\item $\{F_j, z\}$ für alle $j$
|
|
\end{itemize}
|
|
|
|
\textbf{Vorüberlegung} (für jede $(n{+}1)$-Färbung $f$):
|
|
\begin{itemize}
|
|
\item $\{v_1, \dots, v_n, z\}$ ist eine $(n{+}1)$-Clique. O.B.d.A.\ gilt
|
|
$f(v_i) = i$ und $f(z) = n+1$.
|
|
\item $x_j$ und $\bar{x}_j$ sind mit allen $v_i$, $i \ne j$, verbunden.
|
|
Somit $f(x_j), f(\bar{x}_j) \in \{j, n+1\}$.
|
|
\item Wegen der Kante $\{x_j, \bar{x}_j\}$ trägt genau einer die Farbe $j$,
|
|
der andere $n+1$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis 3-SAT nach $k$-Color:}
|
|
\begin{itemize}
|
|
\item Sei $\psi$ eine erfüllende Belegung.
|
|
\item Färbe je Paar das wahre Literal mit $i$, das falsche mit $n+1$;
|
|
dazu $f(v_i) = i$, $f(z) = n+1$.
|
|
\item Jede Klausel $F_j$ enthält ein wahres Literal $y$ aus Paar $i$.
|
|
$y$ hat Farbe $i$, und $\{F_j, y\} \notin E$.
|
|
\item Färbe $f(F_j) = i$. Kein Nachbar von $F_j$ trägt Farbe $i$: Das
|
|
andere Literal des Paars $i$ hat Farbe $n+1$, und $v_i$ ist nicht mit
|
|
$F_j$ verbunden.
|
|
\item Also ist $G$ mit $n+1$ Farben färbbar.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis $k$-Color nach 3-SAT:}
|
|
\begin{itemize}
|
|
\item Sei $f$ eine $(n{+}1)$-Färbung, o.B.d.A.\ wie in der Vorüberlegung.
|
|
\item Setze $\psi(x_j) = \true$ genau dann, wenn $f(x_j) = j$.
|
|
\item Angenommen, eine Klausel $F_j$ wäre unter $\psi$ falsch. Dann tragen
|
|
alle ihre Literale die Farbe $n+1$.
|
|
\item Für jedes $i$ liegt dann der Farbe-$i$-Knoten des Paars $i$ nicht in
|
|
$F_j$ -- also ist er mit $F_j$ verbunden.
|
|
\item $F_j$ sieht so alle Farben $1, \dots, n$ und über $z$ die Farbe
|
|
$n+1$. Keine Farbe bleibt frei -- Widerspruch.
|
|
\item Also erfüllt $\psi$ jede Klausel.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Knoten und Kanten anlegen -- $O(n^2 + nm)$.
|
|
|
|
Da $k$-\problem{Color} $\in \NP$ und NP-schwer ist, folgt:
|
|
$k$-\problem{Color} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $k$-COLOR-PRECOLORING}
|
|
\textbf{Problem $k$-\problem{COLOR-PRECOLORING}:} Gegeben ein Graph
|
|
$G = (V,E)$, eine Zahl $k$ und paarweise verschiedene Knoten
|
|
$v_1, \dots, v_k \in V$. Gibt es eine Färbung $f: V \to [k]$ mit
|
|
$f(u) \ne f(w)$ für alle $\{u,w\} \in E$ und $f(v_i) = i$ für alle $i$?
|
|
Beweisen Sie, dass $k$-\problem{COLOR-PRECOLORING} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie $k$-\problem{Color}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$, Knoten
|
|
$v_1, \dots, v_k$ und Zertifikat $f: V \to [k]$. Der Verifizierer arbeitet wie
|
|
folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jedes $i \in [k]$, ob $f(v_i) = i$; lehne sonst ab.
|
|
\item Prüfe für jede Kante $\{u,w\} \in E$, ob $f(u) \ne f(w)$; lehne sonst
|
|
ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine gültige Färbung mit Vorgabe, so ist sie ein akzeptiertes
|
|
Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Vorgaben prüfen $O(k)$,
|
|
Kanten prüfen $O(|E|)$ -- gesamt $O(k + |E|)$. Also gilt
|
|
$k$-\problem{COLOR-PRECOLORING} $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
k\text{-}\problem{Color} \redp k\text{-}\problem{COLOR-PRECOLORING}.
|
|
\]
|
|
$k$-\problem{Color} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine $k$-\problem{Color}-Instanz.
|
|
Wir konstruieren daraus eine $k$-\problem{COLOR-PRECOLORING}-Instanz
|
|
$(G' = (V', E'),\, k,\, v_1, \dots, v_k)$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{v_1, \dots, v_k\}$ mit $k$ neuen Knoten
|
|
\item $E' = E \cup \{\{v_i, v_j\} \mid i \ne j\}$; die $v_i$ bilden ein
|
|
$K_k$, ohne Kante nach $V$
|
|
\item Vorgabe $f(v_i) = i$
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $f$ eine $k$-Färbung von $G$.
|
|
\item Erweitere $f$ durch $f(v_i) = i$ für alle $i \in [k]$.
|
|
\item Die $v_i$ sind nur untereinander verbunden und tragen paarweise
|
|
verschiedene Farben.
|
|
\item Somit ist $f$ eine gültige Färbung von $G'$ und erfüllt die Vorgabe.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $f$ eine gültige Färbung von $G'$ mit $f(v_i) = i$.
|
|
\item Alle Kanten von $G$ liegen in $G'$.
|
|
\item Also ist die Einschränkung von $f$ auf $V$ eine $k$-Färbung von $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Das $K_k$ anlegen -- $O(k^2)$.
|
|
|
|
Da $k$-\problem{COLOR-PRECOLORING} $\in \NP$ und NP-schwer ist, folgt:
|
|
Das Problem ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für HamiltonianCycle}
|
|
Beweisen Sie, dass \problem{HamiltonianCycle} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{HamiltonianPath}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ mit $n = |V|$ und Zertifikat:
|
|
eine Folge $(w_1, \dots, w_n)$ von Knoten. Der Verifizierer arbeitet wie
|
|
folgt:
|
|
\begin{itemize}
|
|
\item Prüfe, ob $(w_1, \dots, w_n)$ jeden Knoten aus $V$ genau einmal
|
|
enthält; lehne sonst ab.
|
|
\item Prüfe für $i = 1, \dots, n-1$, ob $\{w_i, w_{i+1}\} \in E$, und ob
|
|
$\{w_n, w_1\} \in E$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert ein Hamiltonkreis, so ist seine Knotenfolge ein akzeptiertes
|
|
Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Permutation prüfen
|
|
$O(|V|)$, die $|V|$ Kreiskanten nachschlagen $O(|V|)$ -- gesamt $O(|V|)$.
|
|
Also gilt $\problem{HamiltonianCycle} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{HamiltonianPath} \redp \problem{HamiltonianCycle}.
|
|
\]
|
|
\problem{HamiltonianPath} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $G = (V,E)$ eine \problem{HamiltonianPath}-Instanz.
|
|
Wir konstruieren daraus eine \problem{HamiltonianCycle}-Instanz
|
|
$G' = (V', E')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{u\}$ mit einem neuen Knoten $u$
|
|
\item $E' = E \cup \{\{u,v\} \mid v \in V\}$
|
|
\end{itemize}
|
|
So wird $u$ ein universeller Knoten.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $v_1, \dots, v_n$ ein Hamiltonpfad in $G$.
|
|
\item Da $u$ universell ist, existieren $\{v_n, u\}$ und $\{u, v_1\}$ in $G'$.
|
|
\item Also ist $v_1, \dots, v_n, u, v_1$ ein Hamiltonkreis in $G'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $K$ ein Hamiltonkreis in $G'$.
|
|
\item $K$ besucht $u$ genau einmal, zwischen zwei Nachbarn $v_i, v_j \in V$.
|
|
\item Entferne $u$ aus $K$; es bleibt ein Pfad von $v_i$ nach $v_j$ durch alle
|
|
Knoten von $V$.
|
|
\item Dieser Pfad benutzt nur Kanten aus $E$, denn neu sind nur die Kanten an
|
|
$u$.
|
|
\item Also ist er ein Hamiltonpfad in $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Einen Knoten und $|V|$ Kanten anlegen -- $O(|V|)$.
|
|
|
|
Da $\problem{HamiltonianCycle} \in \NP$ und NP-schwer ist, folgt:
|
|
\problem{HamiltonianCycle} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für FeedbackVertexSet}
|
|
Beweisen Sie, dass \problem{FeedbackVertexSet} NP-vollständig ist: Gegeben
|
|
ein \emph{gerichteter} Graph $G = (V,E)$ und $k$, gibt es $X \subseteq V$ mit
|
|
$|X| \le k$, sodass $G \setminus X$ kreisfrei ist?
|
|
\emph{Hinweis:} Reduzieren Sie \problem{VertexCover}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: gerichteter Graph $G = (V,E)$, Zahl $k$ und
|
|
Zertifikat $X \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|X| > k$, lehne ab.
|
|
\item Prüfe per topologischer Sortierung, ob $G \setminus X$ kreisfrei ist;
|
|
lehne bei einem Kreis ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert ein Feedback Vertex Set der Größe $\le k$, so ist es ein
|
|
akzeptiertes Zertifikat; sonst scheitert eine Prüfung. Laufzeit: Größe zählen
|
|
und topologisch sortieren -- $O(|V| + |E|)$. Also gilt
|
|
$\problem{FeedbackVertexSet} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{VertexCover} \redp \problem{FeedbackVertexSet}.
|
|
\]
|
|
\problem{VertexCover} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{VertexCover}-Instanz.
|
|
Wir konstruieren daraus eine \problem{FeedbackVertexSet}-Instanz
|
|
$(G' = (V', E'),\, k')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V$
|
|
\item $E' = \{(u,v),\, (v,u) \mid \{u,v\} \in E\}$
|
|
\item $k' = k$
|
|
\end{itemize}
|
|
So wird jede Kante zu zwei antiparallelen Bögen, also einem $2$-Kreis.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ ein Vertex Cover von $G$ mit $|C| \le k$.
|
|
\item Dann ist $V \setminus C$ unabhängig in $G$.
|
|
\item Also gibt es in $G'$ keinen Bogen zwischen zwei Knoten aus
|
|
$V \setminus C$.
|
|
\item Somit ist $G' \setminus C$ bogenlos, insbesondere kreisfrei.
|
|
\item Also ist $C$ ein Feedback Vertex Set mit $|C| \le k' = k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $X$ ein Feedback Vertex Set von $G'$ mit $|X| \le k'$.
|
|
\item Für jede Kante $\{u,v\} \in E$ bilden $(u,v),\, (v,u)$ einen $2$-Kreis
|
|
in $G'$.
|
|
\item $X$ zerstört jeden Kreis, trifft also diesen $2$-Kreis: $u \in X$ oder
|
|
$v \in X$.
|
|
\item Somit deckt $X$ jede Kante von $G$.
|
|
\item Also ist $X$ ein Vertex Cover von $G$ mit $|X| \le k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Pro Kante zwei Bögen anlegen -- $O(|E|)$.
|
|
|
|
Da $\problem{FeedbackVertexSet} \in \NP$ und NP-schwer ist, folgt:
|
|
\problem{FeedbackVertexSet} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $\Delta$-Cover}
|
|
\textbf{Problem $\Delta$-\problem{Cover}:} Gegeben ein Graph $G = (V,E)$ und
|
|
$k$. Gibt es $C_\Delta \subseteq V$ mit $|C_\Delta| \le k$, sodass jedes
|
|
Dreieck (3-Clique) von $G$ mindestens einen Knoten in $C_\Delta$ hat?
|
|
Beweisen Sie, dass $\Delta$-\problem{Cover} NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{VertexCover}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$C_\Delta \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Falls $|C_\Delta| > k$, lehne ab.
|
|
\item Prüfe für jedes Tripel $\{a,b,c\} \subseteq V$ mit
|
|
$\{a,b\}, \{b,c\}, \{a,c\} \in E$, ob es einen Knoten in $C_\Delta$ hat; lehne
|
|
sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine Dreiecksüberdeckung der Größe $\le k$, so ist sie ein
|
|
akzeptiertes Zertifikat; sonst bleibt ein Dreieck ungedeckt. Laufzeit: Größe
|
|
zählen $O(|V|)$, alle Tripel prüfen $O(|V|^3)$ -- gesamt $O(|V|^3)$. Also gilt
|
|
$\Delta$-\problem{Cover} $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{VertexCover} \redp \Delta\text{-}\problem{Cover}.
|
|
\]
|
|
\problem{VertexCover} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E),\, k)$ eine \problem{VertexCover}-Instanz.
|
|
Wir konstruieren daraus eine $\Delta$-\problem{Cover}-Instanz
|
|
$(G' = (V', E'),\, k')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{w_e \mid e \in E\}$ mit je einem neuen Knoten $w_e$ pro
|
|
Kante
|
|
\item $E' = E \cup \{\{w_e, u\}, \{w_e, v\} \mid e = \{u,v\} \in E\}$
|
|
\item $k' = k$
|
|
\end{itemize}
|
|
So wird jede Kante $e = \{u,v\}$ zum Dreieck $\{u, v, w_e\}$.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $C$ ein Vertex Cover von $G$ mit $|C| \le k$.
|
|
\item Jeder neue Knoten $w_e$ hat genau die Nachbarn $u, v$; jedes Dreieck von
|
|
$G'$ ist daher ein Gadget-Dreieck $\{u, v, w_e\}$ oder ein Dreieck
|
|
$\{a,b,c\} \subseteq V$ aus $G$.
|
|
\item Beim Gadget-Dreieck deckt $C$ die Kante $\{u,v\}$, enthält also $u$ oder
|
|
$v$.
|
|
\item Beim geerbten Dreieck deckt $C$ die Kante $\{a,b\}$, enthält also einen
|
|
Eckknoten.
|
|
\item Somit trifft $C$ jedes Dreieck von $G'$.
|
|
\item Also ist $C$ eine Dreiecksüberdeckung mit $|C| \le k'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $C_\Delta$ eine Dreiecksüberdeckung von $G'$ mit
|
|
$|C_\Delta| \le k'$.
|
|
\item Enthält $C_\Delta$ ein $w_e$ mit $e = \{u,v\}$, ersetze es durch $u$;
|
|
da $w_e$ nur im Dreieck $\{u,v,w_e\}$ liegt und dieses auch $u$ enthält,
|
|
bleibt es eine Überdeckung und wird nicht größer.
|
|
\item So entsteht $C \subseteq V$ mit $|C| \le k$, das jedes Dreieck von $G'$
|
|
trifft.
|
|
\item Jede Kante $\{u,v\} \in E$ bildet mit $w_e$ das Dreieck
|
|
$\{u, v, w_e\}$; $C$ trifft es, und da $w_e \notin C$, gilt $u \in C$ oder
|
|
$v \in C$.
|
|
\item Also ist $C$ ein Vertex Cover von $G$ mit $|C| \le k$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Pro Kante einen Knoten und zwei Kanten anlegen --
|
|
$O(|E|)$.
|
|
|
|
Da $\Delta$-\problem{Cover} $\in \NP$ und NP-schwer ist, folgt:
|
|
$\Delta$-\problem{Cover} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für 3-COLOR mit Minimalgrad 3}
|
|
\textbf{Problem \problem{3-COLOR-Grad-3}:} \problem{3-COLOR}, eingeschränkt
|
|
auf Graphen $G = (V,E)$ mit $\deg(v) \ge 3$ für alle $v \in V$. Ist $G$ mit
|
|
$3$ Farben färbbar? Beweisen Sie, dass diese Variante NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{3-COLOR}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat
|
|
$f: V \to \{1,2,3\}$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jeden Knoten $v$, ob $\deg(v) \ge 3$; lehne sonst ab.
|
|
\item Prüfe für jede Kante $\{u,v\} \in E$, ob $f(u) \ne f(v)$; lehne sonst
|
|
ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine $3$-Färbung der gültigen Instanz, so ist sie ein akzeptiertes
|
|
Zertifikat; sonst hat eine Kante gleich gefärbte Endpunkte. Laufzeit:
|
|
Gradprüfung $O(|V| + |E|)$, Kantenprüfung $O(|E|)$ -- gesamt $O(|V| + |E|)$.
|
|
Also gilt die Grad-3-Variante $\in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{3-COLOR} \redp \problem{3-COLOR-Grad-3}.
|
|
\] \problem{3-COLOR} ist
|
|
bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Benutze das Diamant-Gadget $D$ auf Knoten $p, q, r, s$
|
|
mit den Kanten $pq, pr, qr, qs, rs$ (ein $K_4$ ohne die Kante $\{p,s\}$;
|
|
insbesondere sind $p, s$ nicht benachbart). Sei $G = (V,E)$ eine
|
|
\problem{3-COLOR}-Instanz. Wir konstruieren $G'$ durch:
|
|
\begin{itemize}
|
|
\item Hänge an jeden Knoten $v \in V$ mit $\deg(v) < 3$ zwei eigene Kopien von
|
|
$D$.
|
|
\item Verbinde $v$ mit jeder Kopie über die Kanten $\{v, p\}$ und $\{v, s\}$.
|
|
\end{itemize}
|
|
Dann steigt $\deg(v)$ um $4$, und alle Gadget-Knoten haben Grad $3$ ($q, r$
|
|
über drei Gadget-Kanten, $p, s$ über zwei plus die Kante zu $v$); somit hat
|
|
$G'$ Minimalgrad $3$.
|
|
|
|
\textbf{Beweis hin:}
|
|
\begin{itemize}
|
|
\item Sei $f$ eine $3$-Färbung von $G$.
|
|
\item Erweitere $f$ auf jedes an $v$ angehängte Gadget: Wähle eine Farbe
|
|
$c \ne f(v)$ und setze $p = s = c$ (erlaubt, da $p, s$ nicht benachbart).
|
|
\item $q$ und $r$ sind untereinander sowie zu $p$ und $s$ benachbart; da $p,
|
|
s$ dieselbe Farbe $c$ tragen, bleiben für die Kante $qr$ die beiden anderen
|
|
Farben -- färbe $q, r$ damit.
|
|
\item Die Kanten $\{v,p\}, \{v,s\}$ sind gültig, da $c \ne f(v)$.
|
|
\item Also ist $G'$ mit $3$ Farben färbbar.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis zurück:}
|
|
\begin{itemize}
|
|
\item Sei $f'$ eine $3$-Färbung von $G'$.
|
|
\item Die Gadgets lassen die Originalkanten unverändert, also $E \subseteq
|
|
E'$.
|
|
\item Somit ist die Einschränkung von $f'$ auf $V$ eine $3$-Färbung von $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Pro untergradigem Knoten zwei Gadgets konstanter Größe
|
|
anlegen -- $O(|V|)$.
|
|
|
|
Da die Grad-3-Variante $\in \NP$ und NP-schwer ist, folgt: \problem{3-COLOR}
|
|
mit Minimalgrad $3$ ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für HamiltonianPath}
|
|
\textbf{Problem \problem{HamiltonianPath}:} Gegeben ein ungerichteter Graph
|
|
$G = (V,E)$. Entscheide: Gibt es einen Pfad, der jeden Knoten genau einmal
|
|
besucht? Zeigen Sie, dass \problem{HamiltonianPath} NP-vollständig ist.
|
|
\emph{Hinweis: Reduzieren Sie \problem{HamiltonianCycle}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat: eine Knotenfolge
|
|
$(v_1, \dots, v_n)$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe, ob $(v_1, \dots, v_n)$ jeden Knoten aus $V$ genau einmal
|
|
enthält; lehne sonst ab.
|
|
\item Prüfe für jedes $i < n$, ob $\{v_i, v_{i+1}\} \in E$ gilt; lehne sonst
|
|
ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Hat $G$ einen Hamiltonpfad, dann ist seine Knotenfolge
|
|
ein akzeptiertes Zertifikat. Hat $G$ keinen, dann scheitert jedes Zertifikat
|
|
an einer Prüfung -- abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Knoten auf Vollständigkeit zählen $O(|V|)$, Kantenprüfungen
|
|
$O(|V|)$ -- gesamt $O(|V|)$. Also gilt $\problem{HamiltonianPath} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{HamiltonianCycle} \redp \problem{HamiltonianPath}.
|
|
\]
|
|
\problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $G = (V,E)$ gegeben, o.B.d.A.\ $|V| \ge 3$. Wähle
|
|
einen festen Knoten $v \in V$. Konstruiere $G' = (V', E')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{v^*, s, t\}$
|
|
\item $E' = E \cup \{\{v^*, w\} \mid \{v,w\} \in E\} \cup
|
|
\{\{s,v\}, \{t,v^*\}\}$
|
|
\end{itemize}
|
|
Der Zwilling $v^*$ erbt die Nachbarn von $v$; die Pendants $s,t$ haben Grad 1.
|
|
|
|
\textbf{Beweis HamiltonianCycle nach HamiltonianPath:}
|
|
\begin{itemize}
|
|
\item Sei $v, w_1, \dots, w_{n-1}, v$ ein Hamiltonkreis in $G$.
|
|
\item Da $v^*$ dieselben Nachbarn wie $v$ hat, existiert die Kante
|
|
$\{w_{n-1}, v^*\}$.
|
|
\item Also ist $s, v, w_1, \dots, w_{n-1}, v^*, t$ ein Hamiltonpfad in $G'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis HamiltonianPath nach HamiltonianCycle:}
|
|
\begin{itemize}
|
|
\item Sei $P$ ein Hamiltonpfad in $G'$.
|
|
\item $s$ und $t$ haben Grad 1, sind also die beiden Endpunkte von $P$.
|
|
\item Da $s$ nur an $v$ und $t$ nur an $v^*$ hängt, hat $P$ die Form
|
|
$s, v, x_1, \dots, x_{n-1}, v^*, t$.
|
|
\item Dann sind $x_1, \dots, x_{n-1}$ alle Knoten aus $V \setminus \{v\}$.
|
|
\item Da $\{x_{n-1}, v^*\} \in E'$ und $v^*$ dieselben Nachbarn wie $v$ hat,
|
|
ist $x_{n-1}$ auch Nachbar von $v$.
|
|
\item Ersetze $v^*$ durch $v$: Es entsteht der Kreis $v, x_1, \dots, x_{n-1},
|
|
v$, der jeden Knoten von $G$ genau einmal besucht.
|
|
\item Also ist er ein Hamiltonkreis in $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Zwilling mit bis zu $|V|$ Nachbarn und zwei Pendants
|
|
anlegen -- $O(|V|)$.
|
|
|
|
Da \problem{HamiltonianCycle} NP-schwer ist,
|
|
$\problem{HamiltonianCycle} \redp \problem{HamiltonianPath}$ gilt und
|
|
$\problem{HamiltonianPath} \in \NP$, ist \problem{HamiltonianPath}
|
|
NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für Hitchhiker's-HamiltonianCycle}
|
|
\textbf{Problem \problem{Hitchhiker's-HamiltonianCycle}:} Gegeben ein
|
|
ungerichteter Graph $G = (V,E)$ mit $\deg(v) \ge 42$ für alle $v \in V$.
|
|
Entscheide: Gibt es einen Hamiltonkreis? Zeigen Sie, dass das Problem
|
|
NP-vollständig ist. \emph{Hinweis: Reduzieren Sie \problem{HamiltonianCycle}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$ und Zertifikat: eine
|
|
Knotenfolge $(v_1, \dots, v_n)$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jeden Knoten $v \in V$, ob $\deg(v) \ge 42$ gilt; lehne sonst
|
|
ab.
|
|
\item Prüfe, ob $(v_1, \dots, v_n)$ jeden Knoten aus $V$ genau einmal
|
|
enthält; lehne sonst ab.
|
|
\item Prüfe für jedes $i < n$, ob $\{v_i, v_{i+1}\} \in E$, und ob
|
|
$\{v_n, v_1\} \in E$ gilt; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz gültig und hat $G$ einen Hamiltonkreis,
|
|
dann ist dessen Knotenfolge ein akzeptiertes Zertifikat; sonst scheitert
|
|
jedes Zertifikat an einer Prüfung -- abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Gradprüfung $O(|V| + |E|)$, Folge zählen $O(|V|)$,
|
|
Kantenprüfungen $O(|V|)$ -- gesamt $O(|V| + |E|)$. Also gilt
|
|
$\problem{Hitchhiker's-HamiltonianCycle} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{HamiltonianCycle} \redp \problem{Hitchhiker's-HamiltonianCycle}.
|
|
\]
|
|
\problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $G = (V,E)$ gegeben. Ersetze jeden Knoten $v$ durch
|
|
eine Clique $K_{43}$ auf $\{v_1, \dots, v_{43}\}$ (Portale sind $v_1$ und
|
|
$v_{43}$). Konstruiere $G' = (V', E')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = \{v_1, \dots, v_{43} \mid v \in V\}$
|
|
\item $E' = \{\{v_i, v_j\} \mid v \in V,\ i \ne j\}
|
|
\cup \{\{u_i, v_j\} \mid \{u,v\} \in E,\ i,j \in \{1,43\}\}$
|
|
\end{itemize}
|
|
Innere Clique-Knoten haben Grad $42$, die Portale Grad $\ge 42$ -- die Instanz
|
|
ist gültig.
|
|
\begin{center}
|
|
\begin{tikzpicture}[scale=0.9]
|
|
\node[knoten,font=\small] (u1) at (0,0.85) {$u_1$};
|
|
\node[knoten,font=\small] (u43) at (0,-0.85) {$u_{43}$};
|
|
\node[knoten,font=\small] (v1) at (2.9,0.85) {$v_1$};
|
|
\node[knoten,font=\small] (v43) at (2.9,-0.85) {$v_{43}$};
|
|
\draw (u1)--(v1) (u1)--(v43) (u43)--(v1) (u43)--(v43);
|
|
\draw[dashed] (0,0) ellipse [x radius=0.55, y radius=1.45];
|
|
\draw[dashed] (2.9,0) ellipse [x radius=0.55, y radius=1.45];
|
|
\node[font=\footnotesize] at (0,-2.0) {Clique $K_{43}$ von $u$};
|
|
\node[font=\footnotesize] at (2.9,-2.0) {Clique $K_{43}$ von $v$};
|
|
\node[font=\footnotesize,align=center] at (1.45,2.05)
|
|
{vier Portalkanten\\ pro Originalkante $\{u,v\}$};
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
|
|
\textbf{Beweis HamiltonianCycle nach Hitchhiker's-HamiltonianCycle:}
|
|
\begin{itemize}
|
|
\item Sei $v^{(1)}, \dots, v^{(n)}, v^{(1)}$ ein Hamiltonkreis in $G$.
|
|
\item Durchlaufe die Clique jedes $v^{(j)}$ auf dem Pfad
|
|
$v^{(j)}_1 \to \dots \to v^{(j)}_{43}$; dieser Pfad existiert in jeder Clique.
|
|
\item Wechsle über die Portalkante $\{v^{(j)}_{43}, v^{(j+1)}_1\}$ zur
|
|
nächsten Clique.
|
|
\item Diese Kante existiert, denn $\{v^{(j)}, v^{(j+1)}\} \in E$.
|
|
\item Also wird jeder Knoten von $G'$ genau einmal besucht -- ein
|
|
Hamiltonkreis in $G'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Hitchhiker's-HamiltonianCycle nach HamiltonianCycle:}
|
|
\begin{itemize}
|
|
\item Sei $C'$ ein Hamiltonkreis in $G'$.
|
|
\item Innere Clique-Knoten haben nur Nachbarn in der eigenen Clique; nach
|
|
außen führen nur die Portalkanten.
|
|
\item Somit durchläuft $C'$ jede Clique als ein Segment von Portal zu Portal.
|
|
\item Ziehe jede Clique auf ihren Originalknoten zusammen.
|
|
\item Jede benutzte Portalkante stammt von einer Originalkante $\{u,v\} \in E$.
|
|
\item Also entsteht ein Kreis in $G$, der jeden Knoten genau einmal besucht --
|
|
ein Hamiltonkreis in $G$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Pro Knoten eine $K_{43}$ mit $43^2$ Kanten, pro Kante vier
|
|
Portalkanten -- $O(43^2 \cdot |V| + |E|)$.
|
|
|
|
Da das Problem in $\NP$ liegt und NP-schwer ist, folgt:
|
|
\problem{Hitchhiker's-HamiltonianCycle} ist NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für TSP-Entscheidung}
|
|
\textbf{Problem \problem{TSP-Entscheidung}:} Gegeben $n$ Städte mit
|
|
Distanzen $d(u,v) > 0$ und eine Schranke $L$. Gibt es eine Rundtour der
|
|
Länge $\le L$ durch alle Städte? Beweisen Sie, dass das Problem
|
|
NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{HamiltonianCycle}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Distanzen, Schranke $L$ und Zertifikat: eine
|
|
Rundtour $\pi$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe, ob $\pi$ jede Stadt genau einmal besucht; lehne sonst ab.
|
|
\item Summiere die Distanzen entlang $\pi$; lehne ab, falls $> L$.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert eine Tour der Länge $\le L$, wird sie akzeptiert; sonst scheitert
|
|
jedes Zertifikat. Besuchsprüfung und Summieren -- $O(n^2)$. Also liegt
|
|
\problem{TSP-Entscheidung} in $\NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{HamiltonianCycle} \redp \problem{TSP-Entscheidung}.
|
|
\]
|
|
\problem{HamiltonianCycle} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $G = (V,E)$ eine
|
|
\problem{HamiltonianCycle}-Instanz mit $n = |V|$. Wir konstruieren daraus:
|
|
\begin{itemize}
|
|
\item Städte $= V$
|
|
\item $d(u,v) = 1$ falls $\{u,v\} \in E$, sonst $d(u,v) = n+1$
|
|
\item $L = n$
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis HamiltonianCycle nach TSP:}
|
|
\begin{itemize}
|
|
\item Sei $C$ ein Hamiltonkreis in $G$.
|
|
\item $C$ ist eine Rundtour aus $n$ Kanten mit Distanz je $1$.
|
|
\item Also hat die Tour Länge $n \le L$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis TSP nach HamiltonianCycle:}
|
|
\begin{itemize}
|
|
\item Sei $\pi$ eine Rundtour der Länge $\le n$.
|
|
\item $\pi$ hat $n$ Schritte, jeder kostet mindestens $1$.
|
|
\item Enthielte $\pi$ eine Nicht-Kante, wäre die Länge
|
|
$\ge (n-1) + (n+1) = 2n > n$.
|
|
\item Also nutzt $\pi$ nur Kanten aus $E$ -- $\pi$ ist ein Hamiltonkreis.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Alle Paare belegen -- $O(n^2)$.
|
|
|
|
Da \problem{TSP-Entscheidung} $\in \NP$ und NP-schwer ist, folgt:
|
|
\problem{TSP-Entscheidung} ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $k$-CLIQUE-DEG-3}
|
|
\textbf{Problem $k$-\problem{CLIQUE-DEG-3}:} Gegeben $G = (V,E)$ mit
|
|
$\deg(v) \ge 3$ für alle $v \in V$ und $k \in \mathbb{N}_{>0}$. Entscheide:
|
|
Gibt es eine Clique $C$ mit $|C| \ge k$? Zeigen Sie NP-Vollständigkeit.
|
|
\emph{Hinweis: Reduzieren Sie $k$-\problem{Clique}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Graph $G = (V,E)$, Zahl $k$ und Zertifikat
|
|
$C \subseteq V$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jeden Knoten $v \in V$, ob $\deg(v) \ge 3$ gilt; lehne sonst
|
|
ab.
|
|
\item Falls $|C| < k$, lehne ab.
|
|
\item Prüfe für jedes Paar $\{x,y\} \subseteq C$, ob $\{x,y\} \in E$ gilt;
|
|
lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz gültig und hat $G$ eine Clique mit
|
|
$|C| \ge k$, dann ist diese ein akzeptiertes Zertifikat; sonst verletzt jedes
|
|
Zertifikat eine Prüfung -- abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Gradprüfung $O(|V| + |E|)$, Größe zählen $O(|V|)$, alle
|
|
Paare testen $O(|V|^2)$ -- gesamt $O(|V|^2)$. Also gilt
|
|
$k\text{-}\problem{CLIQUE-DEG-3} \in \NP$.
|
|
|
|
\textbf{Fall $k \le 4$:} Teste jede Knotenmenge $C \subseteq V$ mit $|C| = k$
|
|
und prüfe alle Paare per Adjazenzmatrix. Es gibt $O(|V|^k) \subseteq
|
|
O(|V|^4)$ Mengen mit je $O(1)$ Prüfaufwand -- gesamt $O(|V|^4)$. Für $k \le 4$
|
|
ist das Problem also direkt lösbar; die Konstruktion nimmt daher o.B.d.A.\
|
|
$k \ge 5$ an.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
k\text{-}\problem{Clique} \redp k\text{-}\problem{CLIQUE-DEG-3}.
|
|
\]
|
|
$k$-\problem{Clique} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(G = (V,E), k)$ eine $k$-\problem{Clique}-Instanz,
|
|
o.B.d.A.\ $k \ge 5$. Hänge an jeden Knoten $v$ ein privates $K_4$. Konstruiere
|
|
$(G' = (V', E'), k')$ durch:
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{a_v, b_v, c_v \mid v \in V\}$
|
|
\item $E' = E \cup \{\{x,y\} \mid v \in V,\ x,y \in \{v, a_v, b_v, c_v\},\
|
|
x \ne y\}$
|
|
\item $k' = k$
|
|
\end{itemize}
|
|
Jedes $v \in V$ hat die drei Nachbarn $a_v, b_v, c_v$, Gadget-Knoten haben Grad
|
|
genau 3 -- die Instanz ist gültig.
|
|
|
|
\textbf{Beweis $k$-Clique nach $k$-CLIQUE-DEG-3} (Fall $k \ge 5$):
|
|
\begin{itemize}
|
|
\item Sei $C$ eine $k$-Clique in $G$.
|
|
\item Es wurde keine Kante entfernt.
|
|
\item Also ist $C$ auch eine $k$-Clique in $G'$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis $k$-CLIQUE-DEG-3 nach $k$-Clique} (Fall $k \ge 5$):
|
|
\begin{itemize}
|
|
\item Sei $C'$ eine $k$-Clique in $G'$.
|
|
\item Jeder Knoten in $C'$ hat mindestens $k - 1 \ge 4$ Nachbarn innerhalb
|
|
$C'$.
|
|
\item Gadget-Knoten haben Grad $3 < 4$, können also keine vier Clique-Nachbarn
|
|
haben.
|
|
\item Somit liegt kein Gadget-Knoten in $C'$, also $C' \subseteq V$.
|
|
\item Zwischen Knoten aus $V$ kam keine Kante hinzu.
|
|
\item Also ist $C'$ eine $k$-Clique in $G$.
|
|
\end{itemize}
|
|
Im Fall $k \le 4$ wird $(G,k)$ direkt gelöst und eine triviale Instanz mit
|
|
gleicher Antwort ausgegeben.
|
|
|
|
\textbf{Laufzeit:} Pro Knoten ein $K_4$-Gadget konstanter Größe -- $O(|V|)$;
|
|
im Fall $k \le 4$ alle Mengen testen -- $O(|V|^4)$.
|
|
|
|
Da $k\text{-}\problem{CLIQUE-DEG-3} \in \NP$ und NP-schwer ist, ist
|
|
$k$-\problem{CLIQUE-DEG-3} NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für Knapsack}
|
|
\textbf{Problem \problem{Knapsack}:} Gegeben $n$ Gegenstände mit Gewichten
|
|
$w_i$ und Profiten $p_i$, Kapazität $B$, Zielprofit $P$. Entscheide: Gibt es
|
|
$S \subseteq [n]$ mit $\sum_{i\in S} w_i \le B$ und $\sum_{i\in S} p_i \ge P$?
|
|
Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie
|
|
\problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Gewichte $w_i$, Profite $p_i$, Schranken $B, P$
|
|
und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe $\sum_{i\in S} w_i \le B$; lehne sonst ab.
|
|
\item Prüfe $\sum_{i\in S} p_i \ge P$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Gibt es eine gültige Auswahl, dann ist sie ein
|
|
akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Zwei Summen bilden und vergleichen -- $O(n)$. Also gilt
|
|
$\problem{Knapsack} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp \problem{Knapsack}.
|
|
\] \problem{SubsetSum} ist bereits
|
|
als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Setze
|
|
\[
|
|
w_i := c_i, \quad p_i := c_i \ \ (i \in [n]), \qquad B := K, \quad P := K.
|
|
\]
|
|
|
|
\textbf{Beweis SubsetSum nach Knapsack:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i = K$.
|
|
\item Dann gilt $\sum_{i\in S} w_i = K \le B$.
|
|
\item Und $\sum_{i\in S} p_i = K \ge P$.
|
|
\item Also ist $S$ eine Knapsack-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Knapsack nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S$ eine Knapsack-Lösung.
|
|
\item Gewicht und Profit von $S$ sind dieselbe Zahl $\sum_{i\in S} c_i$.
|
|
\item Aus der Kapazität folgt $\sum_{i\in S} c_i \le B = K$.
|
|
\item Aus dem Zielprofit folgt $\sum_{i\in S} c_i \ge P = K$.
|
|
\item Also gilt $\sum_{i\in S} c_i = K$ -- eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Werte kopieren -- $O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist,
|
|
$\problem{SubsetSum} \redp \problem{Knapsack}$ gilt und
|
|
$\problem{Knapsack} \in \NP$, ist \problem{Knapsack} NP-vollständig.
|
|
\hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für Partition}
|
|
\textbf{Problem \problem{Partition}:} Gegeben Zahlen $c_1, \dots, c_n$.
|
|
Entscheide: Gibt es $S$ mit $\sum_{j\in S} c_j = \frac12 \sum_{j=1}^{n} c_j$?
|
|
Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie
|
|
\problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$ und Zertifikat
|
|
$S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Berechne $\Sigma = \sum_{j=1}^{n} c_j$.
|
|
\item Prüfe $\sum_{j\in S} c_j = \Sigma / 2$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Gibt es eine Partition, dann ist eine ihrer Seiten ein
|
|
akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Zwei Summen bilden und vergleichen -- $O(n)$. Also gilt
|
|
$\problem{Partition} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp \problem{Partition}.
|
|
\] \problem{SubsetSum} ist
|
|
bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Setze $N := \sum_{j=1}^{n} c_j + 1$ und hänge zwei
|
|
Ausgleichszahlen an:
|
|
\[
|
|
c_{n+1} := N - K, \qquad c_{n+2} := K + 1.
|
|
\]
|
|
Die neue Gesamtsumme ist $(N-1) + (N-K) + (K+1) = 2N$, die Hälfte also $N$.
|
|
|
|
\textbf{Schlüsselbeobachtung:} $c_{n+1} + c_{n+2} = N + 1 > N$ -- in jeder
|
|
Partition liegen die beiden Ausgleichszahlen auf verschiedenen Seiten.
|
|
|
|
\textbf{Beweis SubsetSum nach Partition:}
|
|
\begin{itemize}
|
|
\item Sei $S \subseteq [n]$ mit $\sum_{j\in S} c_j = K$.
|
|
\item Setze $S' := S \cup \{n{+}1\}$.
|
|
\item Dann gilt $\sum_{j\in S'} c_j = K + (N - K) = N$.
|
|
\item Also ist $S'$ eine Seite halber Gesamtsumme -- eine Partition.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Partition nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S'$ eine Seite mit $\sum_{j\in S'} c_j = N$.
|
|
\item Nach der Schlüsselbeobachtung liegen $n{+}1$ und $n{+}2$ auf
|
|
verschiedenen Seiten.
|
|
\item O.B.d.A.\ $n{+}1 \in S'$ und $n{+}2 \notin S'$.
|
|
\item Setze $S := S' \setminus \{n{+}1\} \subseteq [n]$.
|
|
\item Dann gilt $\sum_{j\in S} c_j = N - (N - K) = K$ -- eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Gesamtsumme berechnen und zwei Zahlen anhängen -- $O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist,
|
|
$\problem{SubsetSum} \redp \problem{Partition}$ gilt und
|
|
$\problem{Partition} \in \NP$, ist \problem{Partition} NP-vollständig.
|
|
\hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $P2\,||\,C_{\max}$}
|
|
\textbf{Problem $P2\,||\,C_{\max}$ (Entscheidung):} Gegeben $n$ Jobs mit
|
|
Zeiten $p_1, \dots, p_n$, zwei identische Maschinen und eine Schranke $T$.
|
|
Gibt es einen Schedule mit Makespan $\le T$? Beweisen Sie, dass das Problem
|
|
NP-vollständig ist.
|
|
\emph{Hinweis:} Reduzieren Sie \problem{Partition}.
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Zeiten, Schranke $T$ und Zertifikat
|
|
$S \subseteq [n]$ -- die Jobs auf Maschine 1. Der Verifizierer arbeitet wie
|
|
folgt:
|
|
\begin{itemize}
|
|
\item Prüfe $\sum_{i \in S} p_i \le T$; lehne sonst ab.
|
|
\item Prüfe $\sum_{i \notin S} p_i \le T$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
Existiert ein Schedule mit Makespan $\le T$, wird seine
|
|
Maschinen-1-Menge akzeptiert; sonst scheitert jedes Zertifikat.
|
|
Zwei Summen bilden -- $O(n)$. Also liegt $P2\,||\,C_{\max}$ in $\NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{Partition} \redp P2\,||\,C_{\max}.
|
|
\]
|
|
\problem{Partition} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n)$ eine
|
|
\problem{Partition}-Instanz mit Summe $\Sigma$. Ist $\Sigma$ ungerade, gib
|
|
eine feste Nein-Instanz aus. Sonst konstruiere:
|
|
\begin{itemize}
|
|
\item $p_i = c_i$ für $i \in [n]$
|
|
\item $m = 2$ Maschinen, $T = \Sigma/2$
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Partition nach $P2\,||\,C_{\max}$:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i \in S} c_i = \Sigma/2$.
|
|
\item Lege $S$ auf Maschine 1, den Rest auf Maschine 2.
|
|
\item Beide Maschinen haben Last $\Sigma/2 = T$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis $P2\,||\,C_{\max}$ nach Partition:}
|
|
\begin{itemize}
|
|
\item Sei ein Schedule mit Makespan $\le \Sigma/2$ gegeben.
|
|
\item Beide Lasten summieren zu $\Sigma$, und jede ist $\le \Sigma/2$.
|
|
\item Also sind beide Lasten genau $\Sigma/2$.
|
|
\item Die Jobs auf Maschine 1 bilden eine Menge $S$ mit
|
|
$\sum_{i \in S} c_i = \Sigma/2$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Zeiten übernehmen und Summe halbieren -- $O(n)$.
|
|
|
|
Da $P2\,||\,C_{\max} \in \NP$ und NP-schwer ist, folgt:
|
|
$P2\,||\,C_{\max}$ ist NP-vollständig. \hfill$\square$
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für SubsetSumCardinality}
|
|
\textbf{Problem \problem{SubsetSumCardinality}:} Gegeben $c_1, \dots, c_n$
|
|
($n$ gerade) und $K$. Entscheide: Gibt es $S$ mit $|S| = n/2$ und
|
|
$\sum_{i\in S} c_i = K$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis:
|
|
Reduzieren Sie \problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$ ($n$ gerade), Zielwert
|
|
$K$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe $|S| = n/2$; lehne sonst ab.
|
|
\item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Gibt es eine Lösung passender Größe und Summe, dann ist
|
|
sie ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} $|S|$ zählen und Summe bilden -- $O(n)$. Also gilt
|
|
$\problem{SubsetSumCardinality} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp \problem{SubsetSumCardinality}.
|
|
\] \problem{SubsetSum}
|
|
ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Shifte alle Größen um $1$ und füge $n$
|
|
Padding-Items der Größe $1$ hinzu:
|
|
\[
|
|
c_i' := c_i + 1 \ \ (i \le n), \qquad c_i' := 1 \ \ (n < i \le 2n),
|
|
\qquad K' := K + n.
|
|
\]
|
|
Die Ausgabeinstanz hat $2n$ (gerade) Items und verlangt $|S'| = n$.
|
|
|
|
\textbf{Beweis SubsetSum nach SubsetSumCardinality:}
|
|
\begin{itemize}
|
|
\item Sei $S \subseteq [n]$ mit $\sum_{i\in S} c_i = K$.
|
|
\item Dann gilt $\sum_{i\in S} c_i' = \sum_{i\in S}(c_i + 1) = K + |S|$.
|
|
\item Setze $S' := S \cup \{n{+}1, \dots, 2n - |S|\}$, also $n - |S|$
|
|
Padding-Items dazu.
|
|
\item Dann gilt $|S'| = |S| + (n - |S|) = n$.
|
|
\item Und $\sum_{i\in S'} c_i' = (K + |S|) + (n - |S|) = K + n = K'$.
|
|
\item Also ist $S'$ eine Lösung der neuen Instanz.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis SubsetSumCardinality nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S'$ mit $|S'| = n$ und $\sum_{i\in S'} c_i' = K + n$.
|
|
\item Setze $S := S' \cap [n]$; dann enthält $S'$ genau $n - |S|$
|
|
Padding-Items.
|
|
\item Es folgt $\sum_{i\in S}(c_i + 1) = (K + n) - (n - |S|) = K + |S|$.
|
|
\item Also $\sum_{i\in S} c_i = K$ -- eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} $n$ Zahlen shiften und $n$ Padding-Items anhängen --
|
|
$O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist,
|
|
$\problem{SubsetSum} \redp \problem{SubsetSumCardinality}$ gilt und
|
|
$\problem{SubsetSumCardinality} \in \NP$, ist \problem{SubsetSumCardinality}
|
|
NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für $(a_1{=}1)$-SubsetSum}
|
|
\textbf{Problem $(a_1{=}1)$-\problem{SubsetSum}:} Gegeben $n$ Items mit Größen
|
|
$a_i \in \mathbb{N}_{>0}$, wobei $a_1 = 1$, und Zielwert $T$. Entscheide: Gibt
|
|
es $I \subseteq [n]$ mit $\sum_{i\in I} a_i = T$? Zeigen Sie
|
|
NP-Vollständigkeit. \emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Größen $a_1, \dots, a_n$, Zielwert $T$ und
|
|
Zertifikat $I \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe $a_1 = 1$; lehne sonst ab.
|
|
\item Prüfe $\sum_{i\in I} a_i = T$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz gültig und hat sie eine Lösung, dann ist
|
|
diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} $a_1$ prüfen und Summe bilden -- $O(n)$. Also gilt
|
|
$(a_1{=}1)\text{-}\problem{SubsetSum} \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp (a_1{=}1)\text{-}\problem{SubsetSum}.
|
|
\]
|
|
\problem{SubsetSum} ist bereits als NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Verdopple alle Größen und stelle ein
|
|
Ballast-Item voran:
|
|
\[
|
|
a_1 := 1, \qquad a_{i+1} := 2 c_i \ \ (i \in [n]), \qquad T := 2K.
|
|
\]
|
|
Wegen $a_1 = 1$ ist die Instanz gültig.
|
|
|
|
\textbf{Beweis SubsetSum nach $(a_1{=}1)$-SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i = K$.
|
|
\item Setze $I := \{i + 1 \mid i \in S\}$.
|
|
\item Dann gilt $\sum_{j\in I} a_j = \sum_{i\in S} 2 c_i = 2K = T$.
|
|
\item Also ist $I$ eine Lösung der neuen Instanz.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis $(a_1{=}1)$-SubsetSum nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $I$ mit $\sum_{i\in I} a_i = T = 2K$.
|
|
\item Alle Items außer $a_1$ sind gerade, und $T = 2K$ ist gerade.
|
|
\item Angenommen $1 \in I$: Dann wäre die Summe ungerade, da $a_1 = 1$ das
|
|
einzige ungerade Item ist -- Widerspruch.
|
|
\item Also $1 \notin I$; setze $S := \{i - 1 \mid i \in I\}$.
|
|
\item Dann gilt $\sum_{i\in S} 2 c_i = 2K$, also $\sum_{i\in S} c_i = K$ --
|
|
eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} $n$ Zahlen verdoppeln und das Ballast-Item voranstellen --
|
|
$O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist, die Reduktion gilt und
|
|
$(a_1{=}1)\text{-}\problem{SubsetSum} \in \NP$, ist
|
|
$(a_1{=}1)$-\problem{SubsetSum} NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für SubsetSum mit Teilbarkeit}
|
|
Sei $L$ die Menge der \problem{SubsetSum}-Instanzen, bei denen jede Itemgröße
|
|
durch $3$ oder durch $7$ teilbar ist. Entscheide: Gibt es $S$ mit
|
|
$\sum_{i\in S} c_i = K$? Zeigen Sie, dass $L$ NP-vollständig ist.
|
|
\emph{Hinweis: Reduzieren Sie \problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$, Zielwert $K$ und
|
|
Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jede Größe $c_i$, ob $3 \mid c_i$ oder $7 \mid c_i$ gilt; lehne
|
|
sonst ab.
|
|
\item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann
|
|
ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Teilbarkeitstests und Summe bilden -- $O(n)$. Also gilt
|
|
$L \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp L.
|
|
\] \problem{SubsetSum} ist bereits als
|
|
NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Skaliere mit $3$:
|
|
\[
|
|
c_i' := 3 c_i \ \ (i \in [n]), \qquad K' := 3K.
|
|
\]
|
|
Jede Größe $c_i'$ ist durch $3$ teilbar -- die Instanz liegt in $L$.
|
|
|
|
\textbf{Beweis SubsetSum nach Variante:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i = K$.
|
|
\item Dann gilt $\sum_{i\in S} c_i' = \sum_{i\in S} 3 c_i = 3 \sum_{i\in S} c_i
|
|
= 3K = K'$.
|
|
\item Also ist $S$ eine Lösung der neuen Instanz.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Variante nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i' = K'$.
|
|
\item Wegen $c_i' = 3 c_i$ heißt das $3 \sum_{i\in S} c_i = 3K$.
|
|
\item Division durch $3$ liefert $\sum_{i\in S} c_i = K$.
|
|
\item Also ist $S$ eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Jede der $n$ Zahlen und $K$ mit $3$ multiplizieren --
|
|
$O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp L$ gilt
|
|
und $L \in \NP$, ist $L$ NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für SubsetSum ohne Zweierpotenzen}
|
|
Sei $L$ die Menge der \problem{SubsetSum}-Instanzen, bei denen keine Itemgröße
|
|
eine Zweierpotenz ist. Entscheide: Gibt es $S$ mit $\sum_{i\in S} c_i = K$?
|
|
Zeigen Sie, dass $L$ NP-vollständig ist. \emph{Hinweis: Reduzieren Sie
|
|
\problem{SubsetSum}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$, Zielwert $K$ und
|
|
Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jede Größe $c_i$, dass sie keine Zweierpotenz ist ($c_i$ ist
|
|
Zweierpotenz genau dann, wenn $c_i \wedge (c_i - 1) = 0$); lehne sonst ab.
|
|
\item Prüfe $\sum_{i\in S} c_i = K$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann
|
|
ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Bit-Test je Größe und Summe bilden -- $O(n)$. Also gilt
|
|
$L \in \NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SubsetSum} \redp L.
|
|
\] \problem{SubsetSum} ist bereits als
|
|
NP-vollständig bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine
|
|
\problem{SubsetSum}-Instanz. Skaliere mit $3$:
|
|
\[
|
|
c_i' := 3 c_i \ \ (i \in [n]), \qquad K' := 3K.
|
|
\]
|
|
Jede Größe $c_i' \ge 3$ hat den Primfaktor $3$; Zweierpotenzen haben nur den
|
|
Primfaktor $2$. Also ist kein $c_i'$ eine Zweierpotenz -- die Instanz liegt in
|
|
$L$.
|
|
|
|
\textbf{Beweis SubsetSum nach Variante:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i = K$.
|
|
\item Dann gilt $\sum_{i\in S} c_i' = 3 \sum_{i\in S} c_i = 3K = K'$.
|
|
\item Also ist $S$ eine Lösung der neuen Instanz.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis Variante nach SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $S$ mit $\sum_{i\in S} c_i' = K'$.
|
|
\item Das heißt $3 \sum_{i\in S} c_i = 3K$.
|
|
\item Division durch $3$ liefert $\sum_{i\in S} c_i = K$.
|
|
\item Also ist $S$ eine SubsetSum-Lösung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Jede der $n$ Zahlen und $K$ mit $3$ multiplizieren --
|
|
$O(n)$.
|
|
|
|
Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp L$ gilt
|
|
und $L \in \NP$, ist $L$ NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Vollständigkeit zeigen für AtMostTwoPerSize-SubsetSum}
|
|
\textbf{Problem \problem{AtMostTwoPerSize-SubsetSum}:} Gegeben ein Zielwert
|
|
$T > 0$ und $n$ Items mit Größen $a_i \in \mathbb{N}_{>0}$, wobei jede Größe
|
|
höchstens zweimal auftritt. Entscheide: Gibt es $S$ mit $\sum_{i\in S} a_i =
|
|
T$? Zeigen Sie NP-Vollständigkeit. \emph{Hinweis: Bei \problem{3-ExactCover}
|
|
sind ein Universum $U$ mit $|U| = 3m$ und Dreiermengen $S_1, \dots, S_n
|
|
\subseteq U$ gegeben; gesucht ist eine Auswahl, die jedes Element genau einmal
|
|
überdeckt. Reduzieren Sie \problem{3-ExactCover}.}
|
|
|
|
\lsg
|
|
\textbf{$\in$ NP:} Eingabe: Größen $a_1, \dots, a_n$, Zielwert $T$ und
|
|
Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt:
|
|
\begin{itemize}
|
|
\item Prüfe für jede Größe, ob sie unter $a_1, \dots, a_n$ höchstens zweimal
|
|
vorkommt; lehne sonst ab.
|
|
\item Prüfe $\sum_{i\in S} a_i = T$; lehne sonst ab.
|
|
\item Sonst akzeptiere.
|
|
\end{itemize}
|
|
\textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, dann
|
|
ist diese ein akzeptiertes Zertifikat; sonst wird jedes Zertifikat abgelehnt.
|
|
|
|
\textbf{Laufzeit:} Häufigkeiten per Paarvergleich $O(n^2)$ und Summe bilden
|
|
$O(n)$ -- gesamt $O(n^2)$. Also gilt $\problem{AtMostTwoPerSize-SubsetSum} \in
|
|
\NP$.
|
|
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{3-ExactCover} \redp \problem{AtMostTwoPerSize-SubsetSum}.
|
|
\]
|
|
\problem{3-ExactCover} ist bereits als NP-schwer bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $(U, S_1, \dots, S_n)$ eine
|
|
\problem{3-ExactCover}-Instanz mit $U = \{u_1, \dots, u_{3m}\}$, o.B.d.A.\ die
|
|
$S_j$ paarweise verschieden (Duplikate vorab löschen). Kodiere jede Menge als
|
|
Ziffernzahl in Basis $n+1$:
|
|
\begin{itemize}
|
|
\item $c_j := \sum_{u_i \in S_j} (n+1)^{i-1}$ für $j = 1, \dots, n$ -- Ziffer
|
|
$1$ an den drei Stellen der Elemente von $S_j$
|
|
\item $T := \sum_{j=0}^{3m-1} (n+1)^j$ -- an jeder der $3m$ Stellen eine $1$
|
|
\end{itemize}
|
|
Verschiedene Mengen setzen verschiedene Potenzen, also sind $c_1, \dots, c_n$
|
|
paarweise verschieden -- jede Größe tritt nur einmal auf, die Instanz ist
|
|
gültig.
|
|
|
|
\textbf{Beweis 3-ExactCover nach AtMostTwoPerSize-SubsetSum:}
|
|
\begin{itemize}
|
|
\item Sei $\mathcal{S}$ eine exakte Überdeckung.
|
|
\item Jedes Element $u_i$ wird von genau einer Menge in $\mathcal{S}$
|
|
überdeckt.
|
|
\item Also kommt in $\sum_{S_j \in \mathcal{S}} c_j$ jede Potenz
|
|
$(n+1)^{i-1}$ genau einmal vor.
|
|
\item Damit gilt $\sum_{S_j \in \mathcal{S}} c_j = \sum_{j=0}^{3m-1} (n+1)^j
|
|
= T$.
|
|
\item Also ist $\mathcal{S}$ eine Lösung der SubsetSum-Instanz.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis AtMostTwoPerSize-SubsetSum nach 3-ExactCover:}
|
|
\begin{itemize}
|
|
\item Sei $S$ eine Auswahl mit $\sum_{j\in S} c_j = T$.
|
|
\item An jeder Ziffernstelle addieren sich höchstens $n$ Einsen, da es nur $n$
|
|
Mengen gibt.
|
|
\item Da die Basis $n+1$ ist, entsteht beim Addieren kein Übertrag.
|
|
\item In $T$ hat jede der $3m$ Stellen den Wert $1$.
|
|
\item Also trägt zu jeder Stelle genau eine gewählte Menge bei.
|
|
\item Damit überdecken die gewählten Mengen jedes Element genau einmal -- eine
|
|
exakte Überdeckung.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Duplikate per Paarvergleich der $n$ Mengen entfernen --
|
|
$O(n^2)$; pro Menge drei Potenzen von $n+1$ und $T$ aus $3m$ Potenzen
|
|
aufaddieren -- $O(n + m)$ Additionen.
|
|
|
|
Da das Problem in $\NP$ liegt und NP-schwer ist, folgt:
|
|
\problem{AtMostTwoPerSize-SubsetSum} ist NP-vollständig. \hfill$\square$
|
|
|
|
|
|
\aufg{NP-Schwere zeigen für HALT$_{\text{TM}}$}
|
|
$\mathrm{HALT}_{\mathrm{TM}} := \{\langle M, w\rangle \mid M \text{ ist eine
|
|
DTM und hält auf } w\}$. Zeigen Sie, dass $\mathrm{HALT}_{\mathrm{TM}}$
|
|
NP-schwer ist, und begründen Sie, warum $\mathrm{HALT}_{\mathrm{TM}} \notin
|
|
\NP$. \emph{Hinweis: Reduzieren Sie \problem{SAT}.}
|
|
|
|
\lsg
|
|
\textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion
|
|
\[
|
|
\problem{SAT} \redp \mathrm{HALT}_{\mathrm{TM}}.
|
|
\] \problem{SAT} ist bereits
|
|
als NP-schwer bekannt.
|
|
|
|
\textbf{Konstruktion:} Sei $\varphi$ eine \problem{SAT}-Instanz über den
|
|
Variablen $x_1, \dots, x_n$. Gib die Instanz $\langle M, w \rangle$ aus:
|
|
\begin{itemize}
|
|
\item $w := \langle \varphi \rangle$ -- die Kodierung von $\varphi$.
|
|
\item $M$ ist eine feste DTM, die auf Eingabe $\langle \varphi \rangle$ so
|
|
arbeitet: probiere nacheinander alle $2^n$ Belegungen der Variablen; halte,
|
|
sobald eine Belegung $\varphi$ erfüllt; gehe in eine Endlosschleife, falls
|
|
keine der $2^n$ Belegungen erfüllt.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis SAT nach HALT:}
|
|
\begin{itemize}
|
|
\item Sei $\varphi \in \problem{SAT}$.
|
|
\item Dann existiert eine erfüllende Belegung.
|
|
\item $M$ probiert alle Belegungen, findet diese und hält auf $w$.
|
|
\item Also $\langle M, w \rangle \in \mathrm{HALT}_{\mathrm{TM}}$.
|
|
\end{itemize}
|
|
|
|
\textbf{Beweis HALT nach SAT:}
|
|
\begin{itemize}
|
|
\item Sei $\langle M, w \rangle \in \mathrm{HALT}_{\mathrm{TM}}$, also hält
|
|
$M$ auf $w$.
|
|
\item $M$ hält nur, wenn es eine erfüllende Belegung findet.
|
|
\item Denn ohne erfüllende Belegung geht $M$ in die Endlosschleife.
|
|
\item Also existiert eine erfüllende Belegung für $\varphi$.
|
|
\item Damit $\varphi \in \problem{SAT}$.
|
|
\end{itemize}
|
|
|
|
\textbf{Laufzeit:} Nur $\varphi$ kodieren und die feste Maschine $M$ ausgeben
|
|
-- $O(|\varphi|)$. Ob $M$ auf $w$ hält, spielt für die Reduktion keine Rolle.
|
|
|
|
Da \problem{SAT} NP-schwer ist und
|
|
$\problem{SAT} \redp \mathrm{HALT}_{\mathrm{TM}}$ gilt, ist
|
|
$\mathrm{HALT}_{\mathrm{TM}}$ NP-schwer.
|
|
|
|
\textbf{Warum $\mathrm{HALT}_{\mathrm{TM}} \notin \NP$:}
|
|
$\mathrm{HALT}_{\mathrm{TM}}$ ist das Halteproblem und damit unentscheidbar.
|
|
Jede Sprache in $\NP$ ist jedoch entscheidbar: Ein Verifizierer liefert durch
|
|
Absuchen aller polynomiell langen Zertifikate ein Entscheidungsverfahren.
|
|
Eine unentscheidbare Sprache kann also nicht in $\NP$ liegen. Somit ist
|
|
$\mathrm{HALT}_{\mathrm{TM}}$ NP-schwer, aber nicht NP-vollständig.
|
|
\hfill$\square$
|
|
|
|
\clearpage
|
|
\section{Approximative Algorithmen}
|
|
\aufg{Güte zeigen für ListScheduling}
|
|
$P\,\|\,C_{\max}$: $n$ Jobs mit Zeiten $p_1,\dots,p_n$ auf $m$ Maschinen,
|
|
minimiere den Makespan. \emph{Hinweis:} ListScheduling legt jeden Job der
|
|
Reihe nach auf die aktuell am wenigsten belastete Maschine. Zeigen Sie die
|
|
Güte $2-\frac1m$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{LS}(I) \;\le\; \Bigl(2-\tfrac1m\Bigr)\,\mathrm{OPT}(I) .
|
|
\]
|
|
O.\,B.\,d.\,A.\ trage Maschine $M_1$ am Ende die höchste Last
|
|
$L=\mathrm{LS}(I)$, und sei $J_k$ der \emph{letzte} Job, der auf $M_1$ gelegt
|
|
wurde.
|
|
|
|
\textbf{Kritischer Moment.} Als $J_k$ zugeteilt wurde, war $M_1$ die
|
|
leerste Maschine mit Last $L-p_k$. Also trugen zu diesem Zeitpunkt alle $m$
|
|
Maschinen mindestens Last $L-p_k$, woraus für die Gesamtarbeit folgt
|
|
\[
|
|
\sum_{i=1}^{n} p_i \;\ge\; m\,(L-p_k) + p_k .
|
|
\]
|
|
|
|
\textbf{Untere Schranken für das Optimum.} Die Gesamtarbeit verteilt sich auf
|
|
$m$ Maschinen, und jeder Job läuft irgendwo, also
|
|
\[
|
|
\mathrm{OPT}(I) \;\ge\; \frac1m\sum_{i=1}^n p_i
|
|
\qquad\text{und}\qquad
|
|
\mathrm{OPT}(I) \;\ge\; p_k .
|
|
\]
|
|
|
|
\textbf{Kombination.} Erst die Durchschnittsschranke mit der
|
|
Kernbeobachtung verbinden:
|
|
\[
|
|
\mathrm{OPT}(I) \;\ge\; \frac1m\sum_{i=1}^n p_i
|
|
\;\ge\; \frac{m(L-p_k)+p_k}{m}
|
|
\;=\; L - p_k + \frac{p_k}{m}
|
|
\;=\; L-\Bigl(1-\tfrac1m\Bigr)p_k .
|
|
\]
|
|
Nach $L$ aufgelöst:
|
|
\[
|
|
\mathrm{LS}(I) \;=\; L \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)p_k .
|
|
\]
|
|
Nun $p_k \le \mathrm{OPT}(I)$ einsetzen:
|
|
\[
|
|
\mathrm{LS}(I) \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)\mathrm{OPT}(I)
|
|
\;=\; \Bigl(2-\tfrac1m\Bigr)\mathrm{OPT}(I) .
|
|
\]
|
|
Somit hat ListScheduling die Güte $2-\frac1m$.
|
|
|
|
|
|
\aufg{Güte zeigen für LPT}
|
|
$P\,\|\,C_{\max}$ wie zuvor. \emph{Hinweis:} LPT sortiert die Jobs zuerst
|
|
\emph{absteigend} nach Laufzeit und wendet darauf ListScheduling an. Zeigen
|
|
Sie die Güte $\frac43-\frac1{3m}$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{LPT}(I) \;\le\; \Bigl(\tfrac43-\tfrac1{3m}\Bigr)\,\mathrm{OPT}(I) .
|
|
\]
|
|
Nummeriere absteigend, $p_1\ge\dots\ge p_n$. Sei $J_n$ der Job, der den
|
|
Makespan setzt (der kleinste Job auf der vollsten Maschine).
|
|
|
|
\textbf{Kritischer Moment.} Als $J_n$ platziert wurde, hatte seine Maschine
|
|
die kleinste Last $s$. Wie bei ListScheduling folgt
|
|
$s \le \mathrm{OPT}(I) - p_n/m$, also
|
|
\[
|
|
\mathrm{LPT}(I) \;=\; s+p_n \;\le\; \mathrm{OPT}(I) + \Bigl(1-\tfrac1m\Bigr)p_n .
|
|
\]
|
|
|
|
\textbf{Fallunterscheidung nach $p_n$.}
|
|
\begin{itemize}
|
|
\item Ist $p_n \le \mathrm{OPT}(I)/3$, so liefert Einsetzen direkt
|
|
$\mathrm{LPT}(I) \le (\tfrac43-\tfrac1{3m})\,\mathrm{OPT}(I)$.
|
|
\item Ist $p_n > \mathrm{OPT}(I)/3$, dann sind \emph{alle} Jobs
|
|
$> \mathrm{OPT}(I)/3$. Im Optimum trägt jede Maschine höchstens zwei
|
|
Jobs. Für diesen Fall ist bekannt, dass LPT sogar optimal ist
|
|
($\mathrm{LPT}(I) = \mathrm{OPT}(I)$).
|
|
\end{itemize}
|
|
In beiden Fällen gilt die Schranke, also hat LPT die Güte
|
|
$\frac43-\frac1{3m}$.
|
|
|
|
|
|
\aufg{Güte zeigen für RoundRobin}
|
|
$P\,\|\,C_{\max}$ wie zuvor. \emph{Hinweis:} RoundRobin sortiert die Jobs
|
|
absteigend und verteilt sie reihum, d.\,h.\ $J_j$ kommt auf Maschine
|
|
$((j-1)\bmod m)+1$. Zeigen Sie die Güte $2$ (die Rate wird im Worst Case bis
|
|
$2-\frac1m$ ausgereizt).
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{RR}(I) \;\le\; 2\,\mathrm{OPT}(I) .
|
|
\]
|
|
Angenommen, es gälte $\mathrm{RR}(I)>2\,\mathrm{OPT}(I)$. Sei $M_i$ die
|
|
Maschine mit maximaler Last; sie trägt die Jobs $J_i,J_{i+m},J_{i+2m},\dots$
|
|
|
|
\textbf{Blockschranke.} Wegen der absteigenden Sortierung ist
|
|
$p_{i+lm}\le p_j$ für jedes $j\le lm$; insbesondere ist $p_{i+lm}$ höchstens so
|
|
groß wie der Durchschnitt des vorangehenden $m$-er-Blocks:
|
|
\[
|
|
p_{i+lm} \;\le\; \frac1m\sum_{j=(l-1)m+1}^{lm} p_j \qquad (l\ge1).
|
|
\]
|
|
|
|
\textbf{Aufsummieren.} Summation über $l\ge1$ ergibt
|
|
\[
|
|
\mathrm{RR}(I)-p_i \;=\; \sum_{l\ge1}p_{i+lm}
|
|
\;\le\; \frac1m\sum_{j} p_j \;\le\; \mathrm{OPT}(I).
|
|
\]
|
|
|
|
\textbf{Kombination.} Mit $p_i\le p_1\le\mathrm{OPT}(I)$ folgt
|
|
$\mathrm{RR}(I)\le 2\,\mathrm{OPT}(I)$ -- im Widerspruch zur Annahme.
|
|
|
|
Somit hat RoundRobin die Güte $2$; die Familie aus einem Job der Größe $m$ und
|
|
$m(m-1)$ Einser-Jobs treibt die Rate gegen $2-\frac1m$.
|
|
|
|
|
|
\aufg{Güte zeigen für Parallel-Task-ListScheduling}
|
|
Beim Parallel-Task-Scheduling belegt Job $j$ während seiner Laufzeit $p_j$
|
|
\emph{gleichzeitig} $q_j\in[m]$ Maschinen. \emph{Hinweis:} ListScheduling
|
|
platziert jeden Job zum frühestmöglichen Zeitpunkt auf den $q_j$ am wenigsten
|
|
belasteten Maschinen. Zeigen Sie für alle Instanzen mit
|
|
$\frac m3<q_j\le\frac m2$:
|
|
$\mathrm{LS}(I)\le\mathrm{OPT}(I)+\frac12\,p_{\max}$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{LS}(I) \;\le\; \mathrm{OPT}(I)+\tfrac12\,p_{\max}.
|
|
\]
|
|
Sei $j$ ein Job, der den Makespan bestimmt, mit Startzeit
|
|
$s=\mathrm{LS}(I)-p_j$.
|
|
|
|
\textbf{In $[0,s)$ laufen stets genau zwei Jobs.} Zu jedem Zeitpunkt $t<s$
|
|
sind weniger als $q_j\le\frac m2$ Maschinen frei -- sonst wäre $j$ früher
|
|
gestartet worden --, also mehr als $\frac m2$ belegt. Da jeder Job höchstens
|
|
$\frac m2$ Maschinen belegt, laufen mindestens zwei Jobs; da jeder Job mehr als
|
|
$\frac m3$ belegt, laufen höchstens zwei (drei bräuchten $>m$ Maschinen). Also
|
|
laufen genau zwei, und
|
|
\[
|
|
2s \;=\; \int_0^s \#\{\text{laufende Jobs}\}\;dt
|
|
\;\le\; \sum_i p_i - p_j .
|
|
\]
|
|
|
|
\textbf{Schranke für das Optimum.} Auch im Optimum laufen nie drei Jobs
|
|
gleichzeitig (sie bräuchten $>3\cdot\frac m3=m$ Maschinen), also
|
|
$\sum_i p_i\le 2\,\mathrm{OPT}(I)$. Einsetzen:
|
|
\[
|
|
s \;\le\; \tfrac12\Bigl(\sum_i p_i-p_j\Bigr)
|
|
\;\le\; \mathrm{OPT}(I)-\tfrac12 p_j .
|
|
\]
|
|
|
|
\textbf{Kombination.} Mit $\mathrm{LS}(I)=s+p_j$ folgt
|
|
\[
|
|
\mathrm{LS}(I) \;\le\; \mathrm{OPT}(I)+\tfrac12 p_j
|
|
\;\le\; \mathrm{OPT}(I)+\tfrac12 p_{\max}.
|
|
\]
|
|
Somit gilt die behauptete Schranke.
|
|
|
|
|
|
\aufg{Güte zeigen für ModifiedGreedy}
|
|
\problem{Knapsack}: Gegenstände mit Gewichten $w_i$, Profiten $p_i$,
|
|
Kapazität $B$; maximiere den Profit. \emph{Hinweis:} Greedy sortiert
|
|
absteigend nach Profitdichte $p_i/w_i$ und packt in dieser Reihenfolge jeden
|
|
Gegenstand ein, der noch passt; ModifiedGreedy (MGA) gibt das Bessere aus
|
|
Greedy-Lösung und profitreichstem Einzel-Gegenstand aus. Zeigen Sie die Güte
|
|
$2$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{OPT}(I) \;\le\; 2\,\mathrm{MGA}(I).
|
|
\]
|
|
Nummeriere nach Dichte, $p_1/w_1\ge\dots\ge p_n/w_n$, und sei $k+1$ der erste
|
|
Gegenstand, den Greedy nicht mehr einpacken kann.
|
|
|
|
\textbf{Schritt 1 (Relaxierung).} Erlaubt man, Gegenstände \emph{anteilig}
|
|
einzupacken, wächst der Lösungsraum; das fraktionale Optimum $\mathrm{OPT}_f$
|
|
erfüllt daher $\mathrm{OPT}(I)\le\mathrm{OPT}_f(I)$.
|
|
|
|
\textbf{Schritt 2 (fraktionales Optimum).} Die beste fraktionale Lösung füllt
|
|
den Rucksack in Dichte-Reihenfolge: die Gegenstände $1,\dots,k$ ganz, vom
|
|
Gegenstand $k+1$ einen Bruchteil $\le1$. Also
|
|
$\mathrm{OPT}_f(I)\le p_1+\dots+p_k+p_{k+1}$. Da Greedy die Gegenstände
|
|
$1,\dots,k$ ebenfalls einpackt, ist $p_1+\dots+p_k\le\mathrm{GA}(I)$, mithin
|
|
\[
|
|
\mathrm{OPT}_f(I) \;\le\; \mathrm{GA}(I)+p_{k+1}.
|
|
\]
|
|
|
|
\textbf{Schritt 3 (Kombination).} Mit $p_{k+1}\le p_{\max}$ und
|
|
$\mathrm{MGA}(I)=\max\{\mathrm{GA}(I),p_{\max}\}$ folgt
|
|
\[
|
|
\mathrm{OPT}(I) \;\le\; \mathrm{GA}(I)+p_{\max}
|
|
\;\le\; 2\max\{\mathrm{GA}(I),p_{\max}\}
|
|
\;=\; 2\,\mathrm{MGA}(I).
|
|
\]
|
|
Somit hat ModifiedGreedy die Güte $2$.
|
|
|
|
|
|
\aufg{Güte zeigen für Sahni}
|
|
\problem{Knapsack} wie zuvor. \emph{Hinweis:} Sahni ($k$-Enumeration)
|
|
probiert jede Vorauswahl von höchstens $k$ Gegenständen als festen Grundstock,
|
|
füllt den Rest mit Greedy (Dichte-Reihenfolge) auf und gibt die beste
|
|
gefundene Packung aus. Zeigen Sie die Güte $1+\frac1k$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{OPT}(I) \;\le\; \Bigl(1+\tfrac1k\Bigr)\,\mathrm{Sahni}(I).
|
|
\]
|
|
Sei $O$ eine optimale Auswahl mit Profit $\mathrm{OPT}(I)=p(O)$.
|
|
|
|
\textbf{Fall $|O|\le k$.} Sahni probiert $O$ selbst als Vorauswahl. Also
|
|
$\mathrm{Sahni}(I)\ge p(O)=\mathrm{OPT}(I)$.
|
|
|
|
\textbf{Fall $|O|>k$.} Sei $H\subseteq O$ die Menge der $k$ profitreichsten
|
|
Gegenstände aus $O$. Betrachte die Iteration mit Vorauswahl $H$.
|
|
\begin{itemize}
|
|
\item Greedy füllt mit den restlichen Gegenständen auf. Es verliert
|
|
höchstens den ersten übersprungenen Gegenstand $o^\star \in O$:
|
|
$\mathrm{Sahni}(I) \ge \mathrm{OPT}(I) - p_{o^\star}$.
|
|
\item $o^\star$ und die $k$ Gegenstände aus $H$ sind $k+1$ Gegenstände aus
|
|
$O$, jeder mit Profit $\ge p_{o^\star}$. Also
|
|
$(k+1)\,p_{o^\star} \le \mathrm{OPT}(I)$, d.\,h.\
|
|
$p_{o^\star} \le \mathrm{OPT}(I)/(k+1)$.
|
|
\end{itemize}
|
|
Kombiniert:
|
|
\[
|
|
\mathrm{Sahni}(I) \;\ge\; \mathrm{OPT}(I)-\frac{\mathrm{OPT}(I)}{k+1}
|
|
\;=\; \frac{k}{k+1}\,\mathrm{OPT}(I),
|
|
\]
|
|
also $\mathrm{OPT}(I)\le(1+\tfrac1k)\,\mathrm{Sahni}(I)$. Somit hat Sahni die
|
|
Güte $1+\frac1k$.
|
|
|
|
|
|
\aufg{Güte widerlegen für Greedy}
|
|
\problem{Knapsack} wie zuvor. \emph{Hinweis:} Greedy sortiert absteigend nach
|
|
Profitdichte $p_i/w_i$ und packt jeden noch passenden Gegenstand ein. Zeigen
|
|
Sie, dass Greedy keine konstante Güte hat: Für kein $c$ gilt
|
|
$\mathrm{OPT}(I)\le c\cdot\mathrm{GA}(I)$ für alle Instanzen.
|
|
|
|
\lsg
|
|
Zu zeigen: Die Rate $\mathrm{OPT}(I)/\mathrm{GA}(I)$ ist unbeschränkt.
|
|
|
|
\textbf{Instanzfamilie.} Für einen Parameter $B\ge2$ betrachte zwei
|
|
Gegenstände mit Kapazität $B$:
|
|
\[
|
|
(w_1,p_1)=(1,1), \qquad (w_2,p_2)=(B,\,B-1).
|
|
\]
|
|
Die Dichten sind $\frac{p_1}{w_1}=1$ und $\frac{p_2}{w_2}=\frac{B-1}{B}<1$.
|
|
|
|
\textbf{Greedy.} Nach Dichte kommt der erste Gegenstand zuerst; er passt und
|
|
wird eingepackt. Danach bleibt Restkapazität $B-1<B$, sodass der zweite nicht
|
|
mehr passt. Also $\mathrm{GA}(I)=1$.
|
|
|
|
\textbf{Optimum.} Der zweite Gegenstand allein hat Gewicht $B\le B$ und Profit
|
|
$B-1$, also $\mathrm{OPT}(I)\ge B-1$.
|
|
|
|
\textbf{Rate.} Damit
|
|
\[
|
|
\frac{\mathrm{OPT}(I)}{\mathrm{GA}(I)} \;\ge\; \frac{B-1}{1} \;=\; B-1
|
|
\;\xrightarrow{\;B\to\infty\;}\; \infty .
|
|
\]
|
|
Zu jedem $c$ liefert also schon $B=c+2$ eine Instanz mit
|
|
$\mathrm{OPT}>c\cdot\mathrm{GA}$. Somit besitzt Greedy keine konstante Güte.
|
|
|
|
|
|
\aufg{Güte zeigen für $\Delta$TSP1}
|
|
Metrisches TSP: vollständiger Graph mit symmetrischen Distanzen, die die
|
|
Dreiecksungleichung $d(u,v)\le d(u,w)+d(w,v)$ erfüllen; gesucht eine kürzeste
|
|
Rundreise. \emph{Hinweis ($\Delta$TSP1):} (1) MST $T$ berechnen; (2) alle
|
|
MST-Kanten verdoppeln; (3) Eulerkreis; (4) Abkürzen (schon besuchte Knoten
|
|
überspringen). Zeigen Sie die Güte $2$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
d(R) \;\le\; 2\,\mathrm{OPT}(I)
|
|
\]
|
|
für die berechnete Tour $R$, in drei Schritten.
|
|
|
|
\textbf{Schritt 1 ($w(T)\le\mathrm{OPT}$).} Entfernt man aus einer optimalen
|
|
Rundreise eine Kante, bleibt ein aufspannender Baum. Sein Gewicht ist
|
|
$\le\mathrm{OPT}(I)$, und da $T$ ein \emph{minimaler} Spannbaum ist, gilt
|
|
$w(T)\le\mathrm{OPT}(I)$.
|
|
|
|
\textbf{Schritt 2 (Eulerkreis).} Durch das Verdoppeln haben alle Knoten
|
|
geraden Grad, es existiert ein Eulerkreis. Er benutzt jede MST-Kante genau
|
|
zweimal, hat also Länge
|
|
\[
|
|
2\,w(T) \;\le\; 2\,\mathrm{OPT}(I).
|
|
\]
|
|
|
|
\textbf{Schritt 3 (Abkürzen).} Beim Überspringen bereits besuchter Knoten
|
|
wird eine Teilfolge $u\to w\to v$ durch die direkte Kante $u\to v$ ersetzt.
|
|
Nach der Dreiecksungleichung ist $d(u,v)\le d(u,w)+d(w,v)$, das Abkürzen
|
|
verlängert die Tour also nicht:
|
|
\[
|
|
d(R) \;\le\; 2\,w(T) \;\le\; 2\,\mathrm{OPT}(I).
|
|
\]
|
|
Somit hat $\Delta$TSP1 die Güte $2$.
|
|
|
|
|
|
\aufg{Güte zeigen für Christofides}
|
|
Metrisches TSP wie zuvor. \emph{Hinweis ($\Delta$TSP2, Christofides):} (1) MST
|
|
$T$; (2) $X=$ Knoten mit ungeradem Grad in $T$; (3) minimales perfektes
|
|
Matching $M$ auf $X$; (4) Eulerkreis im Multigraphen $T+M$; (5) Abkürzen.
|
|
Zeigen Sie die Güte $\frac32$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
d(R) \;\le\; \tfrac32\,\mathrm{OPT}(I).
|
|
\]
|
|
|
|
\textbf{Schritt 1 ($w(T)\le\mathrm{OPT}$).} Wie bei $\Delta$TSP1: Entfernt man
|
|
aus einer optimalen Rundreise eine Kante, entsteht ein Spannbaum; sein Gewicht
|
|
ist $\le\mathrm{OPT}(I)$, und da $T$ ein minimaler Spannbaum ist, gilt
|
|
$w(T)\le\mathrm{OPT}(I)$.
|
|
|
|
\textbf{Schritt 2 ($w(M)\le\mathrm{OPT}/2$).} Die Zahl $|X|$ der
|
|
ungerad-gradigen Knoten ist gerade. Kürzt man eine optimale Rundreise auf die
|
|
Knoten aus $X$ ab (alle übrigen überspringen), so entsteht nach der
|
|
Dreiecksungleichung ein Kreis $C$ auf $X$ mit $d(C)\le\mathrm{OPT}(I)$. Ein
|
|
Kreis über die gerade Knotenzahl $|X|$ zerfällt in zwei disjunkte perfekte
|
|
Matchings $M_1,M_2$ (die abwechselnden Kanten). Wegen
|
|
$w(M_1)+w(M_2)=d(C)\le\mathrm{OPT}(I)$ ist das billigere höchstens
|
|
$\mathrm{OPT}(I)/2$, und das minimale perfekte Matching erfüllt
|
|
\[
|
|
w(M) \;\le\; \min\{w(M_1),w(M_2)\} \;\le\; \tfrac12\,\mathrm{OPT}(I).
|
|
\]
|
|
|
|
\textbf{Schritt 3 (Eulerkreis und Abkürzen).} In $T+M$ hat jeder Knoten
|
|
geraden Grad, es existiert ein Eulerkreis der Länge $w(T)+w(M)$. Das Abkürzen
|
|
verlängert wegen der Dreiecksungleichung nicht, also
|
|
\[
|
|
d(R) \;\le\; w(T)+w(M) \;\le\; \mathrm{OPT}(I)+\tfrac12\,\mathrm{OPT}(I)
|
|
\;=\; \tfrac32\,\mathrm{OPT}(I).
|
|
\]
|
|
Somit hat Christofides die Güte $\frac32$.
|
|
|
|
|
|
\aufg{Güte zeigen für 2ApproxVC}
|
|
\problem{VertexCover}: kleinste Knotenmenge $C$, die jede Kante abdeckt.
|
|
\emph{Hinweis:} 2ApproxVC durchläuft alle Kanten; sind beide Endpunkte noch
|
|
nicht in $C$, werden \emph{beide} zu $C$ hinzugefügt. Zeigen Sie die Güte $2$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
|C| \;\le\; 2\,|C^\ast|
|
|
\]
|
|
für ein minimales Vertex Cover $C^\ast$. Sei $A$ die Menge der Kanten, bei
|
|
denen beide Endpunkte aufgenommen wurden; dann ist $|C|=2|A|$.
|
|
|
|
\textbf{$A$ ist ein Matching.} Hätten zwei Kanten aus $A$ einen gemeinsamen
|
|
Endpunkt, so wäre bei der später betrachteten dieser Endpunkt bereits in $C$
|
|
gewesen -- sie wäre nicht aufgenommen worden. Also sind die Kanten aus $A$
|
|
paarweise knotendisjunkt.
|
|
|
|
\textbf{Schranke für das Optimum.} $C^\ast$ deckt jede Kante aus $A$ mit
|
|
mindestens einem Endpunkt ab; da die Kanten aus $A$ knotendisjunkt sind,
|
|
braucht jede einen \emph{eigenen} Knoten, also $|C^\ast|\ge|A|$.
|
|
|
|
\textbf{Kombination.}
|
|
\[
|
|
|C| \;=\; 2|A| \;\le\; 2|C^\ast|.
|
|
\]
|
|
Somit hat 2ApproxVC die Güte $2$.
|
|
|
|
|
|
\aufg{Güte zeigen für MAX-3-SAT}
|
|
\problem{MAX-3-SAT}: Formel $\varphi$ in KNF mit drei Literalen pro Klausel;
|
|
gesucht eine Belegung, die die Anzahl $v(\cdot)$ der erfüllten Klauseln
|
|
maximiert. \emph{Hinweis:} Algorithmus $A$ wertet $\beta_0$ (alle
|
|
\false) und $\beta_1$ (alle \true) aus und gibt die bessere Belegung
|
|
zurück. Zeigen Sie die Güte $2$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
v(A(\varphi)) \;\ge\; \tfrac12\,v(\mathrm{OPT}(\varphi)).
|
|
\]
|
|
Sei $\varphi$ eine Formel mit $m$ Klauseln.
|
|
|
|
\textbf{Jede Klausel zählt einmal.} Unter $\beta_0$ ist jedes negative
|
|
Literal wahr, unter $\beta_1$ jedes positive. Da jede Klausel mindestens ein
|
|
Literal enthält und jedes Literal positiv oder negativ ist, wird jede Klausel
|
|
von $\beta_0$ oder von $\beta_1$ erfüllt. Somit
|
|
\[
|
|
v(\beta_0)+v(\beta_1) \;\ge\; m .
|
|
\]
|
|
|
|
\textbf{Obere Schranke für das Optimum.} Es können höchstens alle $m$ Klauseln
|
|
erfüllt sein, also $v(\mathrm{OPT}(\varphi))\le m$.
|
|
|
|
\textbf{Kombination.} $A$ wählt die bessere der beiden Belegungen, daher
|
|
\[
|
|
v(A(\varphi)) \;=\; \max\{v(\beta_0),v(\beta_1)\}
|
|
\;\ge\; \frac{v(\beta_0)+v(\beta_1)}{2}
|
|
\;\ge\; \frac m2 \;\ge\; \frac{v(\mathrm{OPT}(\varphi))}{2}.
|
|
\]
|
|
Somit hat $A$ die Güte $2$.
|
|
|
|
\aufg{Güte zeigen für ApproximateSubsetSum}
|
|
\problem{ApproximateSubsetSum}: Zahlen $a_1,\dots,a_n\le T$ mit $\sum_i a_i>T$;
|
|
maximiere $\sum_{j\in S}a_j$ unter $\sum_{j\in S}a_j\le T$. \emph{Hinweis:} GA
|
|
sortiert absteigend, nimmt der Reihe nach jedes noch passende Element und
|
|
\emph{stoppt} beim ersten nicht mehr passenden. Zeigen Sie die Güte $2$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{GA}(I) \;\ge\; \tfrac12\,\mathrm{OPT}(I).
|
|
\]
|
|
Sei $a_\ell$ das erste Element, das nicht mehr passte; es existiert wegen
|
|
$\sum_i a_i>T$.
|
|
|
|
\textbf{Überlauf-Schranke.} Zum Stoppzeitpunkt hätte $a_\ell$ die Kapazität
|
|
überschritten:
|
|
\[
|
|
\mathrm{GA}(I)+a_\ell \;>\; T \;\ge\; \mathrm{OPT}(I).
|
|
\]
|
|
|
|
\textbf{Größe des gestoppten Elements.} Wegen der absteigenden Sortierung ist
|
|
jedes bereits gewählte Element $\ge a_\ell$, also enthält die GA-Auswahl ein
|
|
Element $a_j\ge a_\ell$ und damit $\mathrm{GA}(I)\ge a_\ell$.
|
|
|
|
\textbf{Kombination.} Einsetzen liefert
|
|
\[
|
|
2\,\mathrm{GA}(I) \;\ge\; \mathrm{GA}(I)+a_\ell \;>\; T \;\ge\; \mathrm{OPT}(I),
|
|
\]
|
|
also $\mathrm{GA}(I)\ge\mathrm{OPT}(I)/2$. Somit hat GA die Güte $2$.
|
|
|
|
|
|
\aufg{Güte zeigen für Strip Packing: NFDH}
|
|
\problem{StripPacking}: Rechtecke mit Höhen $h(r_i)\le1$, absteigend nach Höhe
|
|
sortiert, in einen Streifen der Breite $1$ packen und die Höhe minimieren.
|
|
\emph{Hinweis:} NFDH packt stufenweise von links; passt ein Rechteck nicht
|
|
mehr, beginnt eine neue Stufe (deren Höhe die ihres ersten, also höchsten
|
|
Rechtecks ist). Zeigen Sie $\mathrm{NFDH}(L)\le 2\,\mathrm{OPT}(L)+h_{\max}$.
|
|
|
|
\lsg
|
|
Zu zeigen:
|
|
\[
|
|
\mathrm{NFDH}(L) \;\le\; 2\,\mathrm{OPT}(L)+h_{\max}.
|
|
\]
|
|
Sei $H_i$ die Höhe der Stufe $i$ (Höhe ihres ersten Rechtecks), $W_i$ ihre
|
|
belegte Gesamtbreite und $A_i$ ihre Rechteck-Gesamtfläche.
|
|
|
|
\textbf{Erstens (Fläche einer Stufe).} Jedes Rechteck der Stufe $i$ hat wegen
|
|
der absteigenden Sortierung Höhe $\ge H_{i+1}$; die Rechtecke der Stufe $i$
|
|
haben zusammen Breite $W_i$, also
|
|
\[
|
|
A_i \;\ge\; W_i\,H_{i+1}.
|
|
\]
|
|
|
|
\textbf{Zweitens (das überlaufende Rechteck).} Das erste Rechteck der Stufe
|
|
$i{+}1$ passte nicht mehr auf Stufe $i$, hat also Breite $>1-W_i$ und Höhe
|
|
$H_{i+1}$, mithin Fläche $>(1-W_i)\,H_{i+1}$.
|
|
|
|
\textbf{Kombination.} Zerlege $H_{i+1}$ und setze beide Schranken ein:
|
|
\[
|
|
H_{i+1} \;=\; W_i H_{i+1}+(1-W_i)H_{i+1}
|
|
\;<\; A_i + \bigl(\text{Fläche des ersten Rechtecks von Stufe } i{+}1\bigr).
|
|
\]
|
|
|
|
\textbf{Summierung.} Summation über $i\ge1$; dabei zählt jede Stufe höchstens
|
|
zweimal (einmal als $A_i$, einmal über ihr erstes Rechteck), und die
|
|
Gesamtfläche passt in einen Streifen der Breite $1$, also
|
|
$\text{Gesamtfläche}\le\mathrm{OPT}(L)$:
|
|
\[
|
|
\sum_{i\ge2} H_i \;<\; 2\cdot\text{Gesamtfläche} \;\le\; 2\,\mathrm{OPT}(L).
|
|
\]
|
|
|
|
\textbf{Fazit.} Die erste Stufe hat Höhe $H_1=h_{\max}$. Damit
|
|
\[
|
|
\mathrm{NFDH}(L) \;=\; \sum_i H_i \;\le\; 2\,\mathrm{OPT}(L)+h_{\max}.
|
|
\]
|
|
Somit gilt die behauptete Schranke.
|
|
|
|
\clearpage
|
|
\section{ETH}
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für VertexCover}
|
|
\textbf{Problem \problem{VertexCover}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k$.\\
|
|
\textbf{Entscheide:} Gibt es $S \subseteq V$ mit $|S| \le k$, sodass
|
|
$v \in S$ oder $u \in S$ für jede Kante $\{v,u\} \in E$?
|
|
|
|
Betrachten Sie die Reduktion $\problem{Clique} \redp \problem{VertexCover}$.
|
|
Aus $(G = (V,E), k)$ wird die Instanz $(G' = (V, \bar E), k')$ mit:
|
|
\begin{itemize}
|
|
\item $\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$
|
|
\item $k' = |V| - k$
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V'|$, $|E'|$ und $k'$ der VC-Instanz in Abhängigkeit der
|
|
Clique-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{VertexCover} bzgl.\ $|V'|$,
|
|
$|E'|$ und $k'$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{Clique} nicht in
|
|
$2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V'| = |V|$, \quad
|
|
$|E'| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$, \quad $k' = |V| - k \le |V|$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{VertexCover} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)} \cdot |I|^{O(1)}$-Algorithmus
|
|
für \problem{Clique}.
|
|
\item Widerspruch zur ETH.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{VertexCover} wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|E'| \le |V|^2$ ist $\sqrt{|E'|} \le |V|$, also $\sqrt{|E'|} = O(|V|)$.
|
|
\item Daraus wird ein $2^{o(|V|)}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zur ETH.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $k'$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{VertexCover} wäre in $2^{o(k')} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $k' \le |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zur ETH.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|E'|})}$, kein $2^{o(k')}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für HittingSet}
|
|
\textbf{Problem \problem{HittingSet}:}\\
|
|
\textbf{Gegeben:} Eine Menge $U$, Teilmengen $F_1, \dots, F_r \subseteq U$
|
|
und eine Zahl $k$.\\
|
|
\textbf{Entscheide:} Gibt es $S \subseteq U$ mit $|S| \le k$ und
|
|
$S \cap F_i \ne \emptyset$ für alle $i \in [r]$?
|
|
|
|
Betrachten Sie die Reduktion $\problem{3-SAT} \redp \problem{HittingSet}$.
|
|
Aus einer 3-SAT-Instanz mit Variablen $x_1, \dots, x_n$ und Klauseln
|
|
$C_1, \dots, C_m$ wird:
|
|
\begin{itemize}
|
|
\item $U = \{x_i, \bar x_i \mid i \in [n]\}$
|
|
\item $F_i = \{x_i, \bar x_i\}$ für jede Variable $i \in [n]$
|
|
\item $F_{n+j} = C_j$ für jede Klausel $j \in [m]$
|
|
\item $k = n$
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|U|$, die Mengenzahl $r$ und $k$ in Abhängigkeit von $n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{HittingSet} bzgl.\ $|U|$, $r$
|
|
und $k$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in
|
|
$2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in
|
|
$2^{o(m)} \cdot |I|^{O(1)}$.
|
|
|
|
\lsg
|
|
\textbf{a)} $|U| = 2n$, \quad $r = n + m$, \quad $k = n$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|U|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{HittingSet} wäre in $2^{o(|U|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|U| = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Direkter Widerspruch zur ETH.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $r$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{HittingSet} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $r = n + m$ und $n \le 3m$ ist $r = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $k$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{HittingSet} wäre in $2^{o(k)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $k = n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Direkter Widerspruch zur ETH.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|U|)}$, kein $2^{o(r)}$, kein $2^{o(k)}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für $k$-Clique}
|
|
\textbf{Problem $k$-\problem{Clique}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k \ge 1$.\\
|
|
\textbf{Entscheide:} Gibt es eine Clique $C \subseteq V$ mit $|C| \ge k$, d.h.\
|
|
$\{v,u\} \in E$ für alle $v, u \in C$ mit $v \ne u$?
|
|
|
|
Betrachten Sie die Reduktion $\problem{3-SAT} \redp k\text{-}\problem{Clique}$.
|
|
Aus einer 3-SAT-Instanz mit Klauseln $F_1, \dots, F_m$ wird ($y_{ij}$ sei das
|
|
$j$-te Literal der Klausel $i$):
|
|
\begin{itemize}
|
|
\item $V = \{[i,j] \mid \text{$j$-tes Literal in Klausel } i\}$
|
|
\item $E = \{\{[i,j],[i',j']\} \mid i \ne i',\ y_{ij} \ne \neg y_{i'j'}\}$
|
|
\item $k = m$
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V|$, $|E|$ und $k$ der Clique-Instanz in Abhängigkeit von
|
|
$n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{Clique} bzgl.\ $|V|$,
|
|
$|E|$ und $k$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH
|
|
nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V| = O(m)$ (je Klausel $\le 3$ Literale), \quad $|E| = O(m^2)$, \quad $k = m$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{Clique} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{Clique} wäre in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|E| = O(m^2)$ ist $\sqrt{|E|} = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $k$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{Clique} wäre in $2^{o(k)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $k = m$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V|)}$, kein $2^{o(\sqrt{|E|})}$, kein $2^{o(k)}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für $k$-IndependentSet}
|
|
\textbf{Problem $k$-\problem{IS}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k$.\\
|
|
\textbf{Entscheide:} Gibt es $S \subseteq V$ mit $|S| \ge k$, sodass
|
|
$\{v,u\} \notin E$ für alle $v, u \in S$ mit $v \ne u$?
|
|
|
|
Betrachten Sie die Reduktion
|
|
$k\text{-}\problem{Clique} \redp k\text{-}\problem{IS}$. Aus $(G = (V,E), k)$
|
|
wird die Instanz $(G' = (V, \bar E), k')$ mit:
|
|
\begin{itemize}
|
|
\item $\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$
|
|
\item $k' = k$
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V'|$, $|E'|$ und $k'$ der IS-Instanz in Abhängigkeit der
|
|
Clique-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{IS} bzgl.\ $|V'|$, $|E'|$
|
|
und $k'$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist $k$-\problem{Clique} weder in
|
|
$2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ noch in
|
|
$2^{o(k)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V'| = |V|$, \quad $|E'| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$, \quad $k' = k$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{IS} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Ein unabhängiges Set in $\bar G$ ist eine Clique in $G$; via Komplementbildung
|
|
löst der Algorithmus \problem{Clique}.
|
|
\item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{IS} wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|E'| \le |V|^2$ ist $\sqrt{|E'|} = O(|V|)$.
|
|
\item Via Komplementbildung wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $k'$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{IS} wäre in $2^{o(k')} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $k' = k$ wird daraus ein $2^{o(k)}$-Algorithmus für $k$-\problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|E'|})}$, kein $2^{o(k')}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für 3-DM}
|
|
\textbf{Problem \problem{3-DM}:}\\
|
|
\textbf{Gegeben:} Mengen $U, V, W$ mit $|U| = |V| = |W|$ und eine
|
|
Tripelmenge $T \subseteq U \times V \times W$.\\
|
|
\textbf{Entscheide:} Gibt es $M \subseteq T$ mit $|M| = |U|$, sodass je zwei
|
|
verschiedene Tripel aus $M$ in allen drei Koordinaten verschieden sind?
|
|
|
|
Betrachten Sie die Reduktion $\problem{SAT} \redp \problem{3-DM}$ (Vorlesung),
|
|
angewandt auf 3-SAT-Instanzen: Sie erzeugt drei gleich große Grundmengen mit
|
|
$|U| = |V| = |W| = O(m^2)$ und eine Tripelmenge mit $|T| = O(m^4)$.
|
|
Beweisen Sie die ETH-Schranken für \problem{3-DM} bzgl.\ $|U|$ und $|T|$
|
|
basierend auf der Reduktion.
|
|
|
|
\emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH
|
|
nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{Bzgl.\ $|U|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{3-DM} wäre in $2^{o(\sqrt{|U|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|U| = O(m^2)$ ist $\sqrt{|U|} = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|T|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{3-DM} wäre in $2^{o(\sqrt[4]{|T|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|T| = O(m^4)$ ist $\sqrt[4]{|T|} = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(\sqrt{|U|})}$, kein $2^{o(\sqrt[4]{|T|})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für 3-ExactCover}
|
|
\textbf{Problem \problem{3-EC}:}\\
|
|
\textbf{Gegeben:} Eine Grundmenge $U$ und eine Familie
|
|
$F = \{S_1, \dots, S_n\}$ von Teilmengen mit $|S_j| = 3$ für alle $j$.\\
|
|
\textbf{Entscheide:} Gibt es eine Teilfamilie $F' \subseteq F$, deren Mengen
|
|
paarweise disjunkt sind und $U$ überdecken ($\bigcup_{S \in F'} S = U$)?
|
|
|
|
Betrachten Sie die Reduktion $\problem{3-DM} \redp \problem{3-EC}$:
|
|
\problem{3-DM} ist ein Spezialfall von \problem{3-EC}. Eine 3-DM-Instanz mit
|
|
Tripelmenge $T$ wird direkt zur 3-EC-Instanz mit:
|
|
\begin{itemize}
|
|
\item Grundmenge $U$ = Vereinigung der drei 3-DM-Mengen
|
|
\item $F = \{\{v,w,u\} \mid (v,w,u) \in T\}$
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|U|$ und die Zahl der Mengen $|F|$ der 3-EC-Instanz in
|
|
Abhängigkeit der 3-DM-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{3-EC} bzgl.\ $|U|$ und $|F|$
|
|
basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{3-DM} weder in
|
|
$2^{o(\sqrt{|V|})} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt[4]{|T|})} \cdot |I|^{O(1)}$
|
|
lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|U| = O(|V|)$, \quad $|F| = |T|$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|U|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{3-EC} wäre in $2^{o(\sqrt{|U|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Jede \problem{3-DM}-Instanz ist eine \problem{3-EC}-Instanz mit $|U| = O(|V|)$,
|
|
also $\sqrt{|U|} = O(\sqrt{|V|})$.
|
|
\item Daraus wird ein $2^{o(\sqrt{|V|})}$-Algorithmus für \problem{3-DM}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|F|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{3-EC} wäre in $2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|F| = |T|$ löst der Algorithmus jede \problem{3-DM}-Instanz.
|
|
\item Daraus wird ein $2^{o(\sqrt[4]{|T|})}$-Algorithmus für \problem{3-DM}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(\sqrt{|U|})}$, kein $2^{o(\sqrt[4]{|F|})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für SubsetSum}
|
|
\textbf{Problem \problem{SubsetSum}:}\\
|
|
\textbf{Gegeben:} Zahlen $c_1, \dots, c_n$ und ein Zielwert $K$.\\
|
|
\textbf{Entscheide:} Gibt es $S \subseteq \{1, \dots, n\}$ mit
|
|
$\sum_{j \in S} c_j = K$?
|
|
|
|
Betrachten Sie die Reduktion $\problem{3-EC} \redp \problem{SubsetSum}$: Jede
|
|
Menge $S_j \in F$ der 3-EC-Instanz liefert ein Item $c_j$ (Bitvektor über $U$),
|
|
also $n = |F|$ Items.
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie die Itemzahl $n$ der SubsetSum-Instanz in Abhängigkeit der
|
|
3-EC-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranke für \problem{SubsetSum} bzgl.\ $n$
|
|
basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{3-EC} nicht in
|
|
$2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $n = |F|$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $n$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{SubsetSum} wäre in $2^{o(\sqrt[4]{n})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $n = |F|$ wird daraus ein $2^{o(\sqrt[4]{|F|})}$-Algorithmus für \problem{3-EC}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bound: kein $2^{o(\sqrt[4]{n})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für $k$-Color}
|
|
\textbf{Problem $k$-\problem{Color}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl $k \ge 1$.\\
|
|
\textbf{Entscheide:} Gibt es eine Färbung $f : V \to [k]$ mit $f(v) \ne f(u)$
|
|
für alle $\{v,u\} \in E$?
|
|
|
|
Betrachten Sie die Reduktion $\problem{3-SAT} \redp k\text{-}\problem{Color}$
|
|
mit:
|
|
\begin{itemize}
|
|
\item $V = \{x_i, \bar x_i, v_i \mid i \in [n]\} \cup \{C_j \mid j \in [m]\}
|
|
\cup \{z\}$
|
|
\item $E$: die Kanten des Vorlesungs-Gadgets
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V|$ und $|E|$ der Color-Instanz in Abhängigkeit von $n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für $k$-\problem{Color} bzgl.\ $|V|$ und $|E|$
|
|
basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH
|
|
nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V| = 3n + m + 1$; wegen $n \le 3m$ also $|V| = O(m)$. \quad
|
|
$|E| = O(n^2 + nm + m) = O(m^2)$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{Color} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $k$-\problem{Color} wäre in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|E| = O(m^2)$ ist $\sqrt{|E|} = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V|)}$, kein $2^{o(\sqrt{|E|})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für CoverClique}
|
|
\textbf{Problem \problem{CoverClique}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl
|
|
$k \in \mathbb{N}_{\ge 1}$.\\
|
|
\textbf{Entscheide:} Existieren $k$ paarweise disjunkte Cliquen
|
|
$C_1, \dots, C_k \subseteq V$, die alle Knoten überdecken?
|
|
|
|
Betrachten Sie die Reduktion
|
|
$k\text{-}\problem{Color} \redp \problem{CoverClique}$. Aus $(G = (V,E), k)$
|
|
wird die Instanz $(G' = (V, \bar E), k)$ mit
|
|
$\bar E = \{\{v,u\} \mid v \ne u,\ \{v,u\} \notin E\}$.
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V'|$ und $|\bar E|$ der CoverClique-Instanz in Abhängigkeit
|
|
der Color-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{CoverClique} bzgl.\ $|V'|$
|
|
und $|\bar E|$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist $k$-\problem{Color} nicht in
|
|
$2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V'| = |V|$, \quad $|\bar E| = \tfrac12|V|(|V|-1) - |E| \le |V|^2$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{CoverClique} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Color}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|\bar E|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{CoverClique} wäre in $2^{o(\sqrt{|\bar E|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|\bar E| \le |V|^2$ ist $\sqrt{|\bar E|} = O(|V|)$.
|
|
\item Daraus wird ein $2^{o(|V|)}$-Algorithmus für $k$-\problem{Color}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|\bar E|})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für $\Delta$Cover}
|
|
\textbf{Problem $\Delta$\problem{Cover}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und
|
|
$k \in \mathbb{N}_0$.\\
|
|
\textbf{Entscheide:} Gibt es $C_\Delta \subseteq V$ mit $|C_\Delta| \le k$,
|
|
sodass $\{v,u,w\} \cap C_\Delta \ne \emptyset$ für jedes Dreieck $\{v,u,w\}$
|
|
(also $\{v,u\},\{v,w\},\{u,w\} \in E$) gilt?
|
|
|
|
Reduktion $\problem{VertexCover} \redp \Delta\problem{Cover}$: Aus
|
|
$(G = (V,E), k)$ wird $(G' = (V',E'), k)$ mit
|
|
\begin{itemize}
|
|
\item $V' = V \cup \{v_e \mid e \in E\}$,
|
|
\item $E' = E \cup \{\{v_e, e_1\}, \{v_e, e_2\} \mid e = \{e_1, e_2\} \in E\}$
|
|
(je Kante ein aufgesetztes Dreieck),
|
|
\item $k$ unverändert.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V'|$ und $|E'|$ der $\Delta$Cover-Instanz in Abhängigkeit
|
|
der VC-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für $\Delta\problem{Cover}$ bzgl.\ $|V'|$
|
|
und $|E'|$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{VertexCover} weder in
|
|
$2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V'| = |V| + |E|$, \quad $|E'| = |E| + 2|E| = 3|E|$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $\Delta\problem{Cover}$ wäre in $2^{o(\sqrt{|V'|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V'| = |V| + |E| \le |V| + |V|^2 = O(|V|^2)$ ist $\sqrt{|V'|} = O(|V|)$.
|
|
\item Daraus wird ein $2^{o(|V|)}$-Algorithmus für \problem{VertexCover}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E'|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, $\Delta\problem{Cover}$ wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|E'| = 3|E| = O(|E|)$ ist $\sqrt{|E'|} = O(\sqrt{|E|})$.
|
|
\item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{VertexCover}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(\sqrt{|V'|})}$, kein $2^{o(\sqrt{|E'|})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für NAE-4-SAT}
|
|
\textbf{Problem \problem{NAE-4-SAT}:}\\
|
|
\textbf{Gegeben:} Variablen $x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ mit
|
|
$|C_i| \le 4$ für alle $i \in [m]$.\\
|
|
\textbf{Entscheide:} Gibt es eine Belegung $\varphi$, sodass jede Klausel $C_i$
|
|
zwei Literale $y, z \in C_i$ mit $\varphi(y) \ne \varphi(z)$ enthält?
|
|
|
|
Reduktion $\problem{3-SAT} \redp \problem{NAE-4-SAT}$: Aus Variablen
|
|
$x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird
|
|
\begin{itemize}
|
|
\item die Variablenmenge $\{x_1, \dots, x_n, w\}$ mit frischer Variable $w$,
|
|
\item pro Klausel $C_i$ die NAE-Klausel $C_i \cup \{w\}$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie die Variablenzahl $n'$ und die Klauselzahl $m'$ der
|
|
NAE-4-SAT-Instanz in Abhängigkeit von $n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{NAE-4-SAT} bzgl.\ $n'$ und
|
|
$m'$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in
|
|
$2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in
|
|
$2^{o(m)} \cdot |I|^{O(1)}$.
|
|
|
|
\lsg
|
|
\textbf{a)} $n' = n + 1$, \quad $m' = m$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $n'$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{NAE-4-SAT} wäre in $2^{o(n')} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $n' = n + 1$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Direkter Widerspruch zur ETH.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $m'$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{NAE-4-SAT} wäre in $2^{o(m')} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $m' = m$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(n')}$, kein $2^{o(m')}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für SetSplitting}
|
|
\textbf{Problem \problem{SetSplitting}:}\\
|
|
\textbf{Gegeben:} Eine Grundmenge $S$ und Teilmengen
|
|
$F_1, \dots, F_r \subseteq S$.\\
|
|
\textbf{Entscheide:} Gibt es eine Partition $S = S_1 \mathbin{\dot\cup} S_2$ mit
|
|
$F_i \cap S_1 \ne \emptyset \ne F_i \cap S_2$ für alle $i \in [r]$?
|
|
|
|
Reduktion $\problem{NAE-4-SAT} \redp \problem{SetSplitting}$: Aus $n$ Variablen
|
|
$x_1, \dots, x_n$ und $m$ Klauseln $C_1, \dots, C_m$ wird
|
|
\begin{itemize}
|
|
\item die Grundmenge $S = \{x_i, \bar x_i \mid i \in [n]\}$,
|
|
\item pro Variable $i \in [n]$ die Teilmenge $\{x_i, \bar x_i\} \subseteq S$,
|
|
\item pro Klausel $C_i$ die Teilmenge $C_i \subseteq S$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|S|$ und die Mengenzahl $r$ der SetSplitting-Instanz in
|
|
Abhängigkeit von $n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{SetSplitting} bzgl.\ $|S|$
|
|
und $r$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} \problem{NAE-4-SAT} ist unter der ETH weder in
|
|
$2^{o(n)} \cdot |I|^{O(1)}$ noch in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|S| = 2n$, \quad $r = n + m$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|S|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{SetSplitting} wäre in $2^{o(|S|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|S| = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{NAE-4-SAT}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $r$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{SetSplitting} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $\le 4$ Literalen je Klausel ist $n \le 4m + 1$, also $r = n + m = O(m)$.
|
|
\item Daraus wird ein $2^{o(m)}$-Algorithmus für \problem{NAE-4-SAT}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|S|)}$, kein $2^{o(r)}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für DominatingSet}
|
|
\textbf{Problem \problem{DominatingSet}:}\\
|
|
\textbf{Gegeben:} Ein ungerichteter Graph $G = (V,E)$ und
|
|
$k \in \mathbb{N}_{\ge 1}$.\\
|
|
\textbf{Entscheide:} Gibt es eine Menge $M \subseteq V$ mit $|M| \le k$, sodass
|
|
jeder Knoten $v \in V$ in $M$ liegt oder zu einem Knoten in $M$ benachbart ist?
|
|
|
|
Reduktion $\problem{3-SAT} \redp \problem{DominatingSet}$: Aus Variablen
|
|
$x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird
|
|
\begin{itemize}
|
|
\item pro Variable $x_i$ die Knoten $x_i, \bar x_i, d_i$ mit den Dreieckskanten
|
|
$\{x_i, \bar x_i\}, \{x_i, d_i\}, \{d_i, \bar x_i\}$,
|
|
\item pro Klausel $C_j$ ein Knoten $C_j$ mit Kanten $\{C_j, \ell\}$ zu jedem
|
|
Literal $\ell \in C_j$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $|V|$ und $|E|$ der DominatingSet-Instanz in Abhängigkeit von
|
|
$n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{DominatingSet} bzgl.\ $|V|$
|
|
und $|E|$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Mit dem Sparsification-Lemma ist \problem{3-SAT} unter der ETH
|
|
nicht in $2^{o(m)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|V| = 3n + m$; wegen $n \le 3m$ also $|V| = O(m)$. \quad
|
|
$|E| = 3n + 3m = O(m)$ (linear in $m$).
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|V|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{DominatingSet} wäre in $2^{o(|V|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|V| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $|E|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{DominatingSet} wäre in $2^{o(|E|)} \cdot |I|^{O(1)}$ lösbar
|
|
(ohne Wurzel, da $|E|$ nur linear wächst).
|
|
\item Wegen $|E| = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|V|)}$, kein $2^{o(|E|)}$ (ohne Wurzel). \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für GridTiling}
|
|
\textbf{Problem \problem{GridTiling}:}\\
|
|
\textbf{Gegeben:} Zahlen $k, N \in \mathbb{N}$ und je $(i,j) \in [k]^2$ eine
|
|
Menge $S_{i,j} \subseteq [N]^2$.\\
|
|
\textbf{Entscheide:} Gibt es Tupel $(e_{i,j})_{(i,j) \in [k]^2}$ mit
|
|
$e_{i,j} \in S_{i,j}$, sodass für $e_{i,j} = (a,b)$, $e_{i,j+1} = (a',b')$ stets
|
|
$a = a'$ und für $e_{i,j} = (a,b)$, $e_{i+1,j} = (a',b')$ stets $b = b'$ gilt?
|
|
|
|
Reduktion $\problem{Clique} \redp \problem{GridTiling}$ mit $N := |V|$ und
|
|
$c \cdot N \le k \le N$: Aus $(G = (V,E), k)$ mit $V = \{1, \dots, N\}$
|
|
ohne isolierte Knoten wird
|
|
\begin{itemize}
|
|
\item $S_{i,i} = \{(a,a) \mid a \in V\}$ (Diagonale),
|
|
\item $S_{i,j} = \{(a,b) \mid a \ne b,\ \{a,b\} \in E\}$ für $i \ne j$,
|
|
\item $k$ unverändert.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $X = \sum_{(i,j)} |S_{i,j}|$ und $Y = \max_{(i,j)} |S_{i,j}|$
|
|
in Abhängigkeit von $N$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{GridTiling} bzgl.\ $X$ und $Y$
|
|
basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{Clique} nicht in
|
|
$2^{o(N)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $|S_{i,i}| = N$, $|S_{i,j}| = 2|E| \le N^2$ und $k = \Theta(N)$, also
|
|
$X \le k \cdot N + k^2 \cdot N^2 = O(N^4)$ und $Y \le \max(N, N^2) = O(N^2)$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $X$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{GridTiling} wäre in $2^{o(\sqrt[4]{X})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $X = O(N^4)$ ist $\sqrt[4]{X} = O(N)$.
|
|
\item Daraus wird ein $2^{o(N)}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $Y$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{GridTiling} wäre in $2^{o(\sqrt{Y})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $Y = O(N^2)$ ist $\sqrt{Y} = O(N)$.
|
|
\item Daraus wird ein $2^{o(N)}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(\sqrt[4]{X})}$, kein $2^{o(\sqrt{Y})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für SetCover}
|
|
\textbf{Problem \problem{SetCover}:}\\
|
|
\textbf{Gegeben:} Eine Menge $U$, Teilmengen $F_1, \dots, F_r \subseteq U$ und
|
|
$k \in \mathbb{N}$.\\
|
|
\textbf{Entscheide:} Gibt es $S \subseteq \{1, \dots, r\}$ mit $|S| \le k$ und
|
|
$\bigcup_{i \in S} F_i = U$?
|
|
|
|
Reduktion $\problem{SetCover} \redp \problem{HittingSet}$ (Rollentausch,
|
|
involutorisch): Aus $(U, F_1, \dots, F_r, k)$ wird
|
|
\begin{itemize}
|
|
\item die Grundmenge $U' = \{1, \dots, r\}$ (ein Element je Menge $F_i$),
|
|
\item pro $w \in U$ die Menge $F'_w = \{v \mid w \in F_v\}$,
|
|
\item $k' = k$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie die Mengenzahl $r'$ und die Elementzahl $|U'|$ der erzeugten
|
|
HittingSet-Instanz in Abhängigkeit der SetCover-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{SetCover} bzgl.\ $|U|$ und $r$
|
|
basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{HittingSet} weder in
|
|
$2^{o(r')} \cdot |I|^{O(1)}$ noch in $2^{o(|U'|)} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} $r' = |U|$, \quad $|U'| = r$ (der Rollentausch ist involutorisch).
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $|U|$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{SetCover} wäre in $2^{o(|U|)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $r' = |U|$ wird daraus über den Rollentausch ein
|
|
$2^{o(r')}$-Algorithmus für \problem{HittingSet}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $r$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{SetCover} wäre in $2^{o(r)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $|U'| = r$ wird daraus ein $2^{o(|U'|)}$-Algorithmus für \problem{HittingSet}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(|U|)}$, kein $2^{o(r)}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für Scheduling $2\,|\,\mathrm{prec}, p_i \in \{1,2\}\,|\,C_{\max}$}
|
|
\textbf{Problem $2\,|\,\mathrm{prec},\ p_i \in \{1,2\}\,|\,C_{\max}$:}\\
|
|
\textbf{Gegeben:} Jobs $\mathcal{J}$ (je Job $p_J \in \{1,2\}$) auf $2$
|
|
Maschinen, Präzedenzen als DAG $G = (\mathcal{J}, A)$ und
|
|
$T \in \mathbb{N}_0$.\\
|
|
\textbf{Entscheide:} Gibt es einen Schedule (Start- und Maschinenzuweisung
|
|
je Job), sodass Jobs einer Maschine sich nicht überlappen, $(j,k) \in A$ den
|
|
Start von $k$ erst nach dem Ende von $j$ erlaubt und der Makespan $\le T$ ist?
|
|
|
|
Reduktion $k\text{-}\problem{Clique} \redp$ Scheduling (zusammenhängender
|
|
Clique-Graph): Aus $(G = (V,E), k)$ wird
|
|
\begin{itemize}
|
|
\item ein Knoten-Job $J_i$ mit $p_i = 1$ je $i \in V$,
|
|
\item ein Kanten-Job $J_{\{i,j\}}$ mit $p_{\{i,j\}} = 2$ je $\{i,j\} \in E$,
|
|
\item $3|V| + 2|E|$ Dummy-Jobs mit $p = 1$, also $n = 4|V| + 3|E|$ Jobs,
|
|
\item Präzedenzen $(J_i, J_{\{i,j\}})$ für alle $i \in V,\ \{i,j\} \in E$
|
|
(sowie innerhalb der Dummy-Jobs),
|
|
\item Makespan $T = 2|V| + 2|E|$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie $n$ und $T$ der Scheduling-Instanz in Abhängigkeit der
|
|
Clique-Instanz an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für das Scheduling-Problem bzgl.\ $n$
|
|
und $T$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{Clique} (zusammenhängend) weder in
|
|
$2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$ lösbar.
|
|
|
|
\lsg
|
|
\textbf{a)} Wegen $|V| \le |E| + 1$: \quad $n = 4|V| + 3|E| = O(|E|)$, \quad
|
|
$T = 2|V| + 2|E| = O(|E|)$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $n$:}
|
|
\begin{itemize}
|
|
\item Angenommen, das Scheduling-Problem wäre in $2^{o(\sqrt{n})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $n = O(|E|)$ ist $\sqrt{n} = O(\sqrt{|E|})$.
|
|
\item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $T$:}
|
|
\begin{itemize}
|
|
\item Angenommen, das Scheduling-Problem wäre in $2^{o(\sqrt{T})} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $T = O(|E|)$ ist $\sqrt{T} = O(\sqrt{|E|})$.
|
|
\item Daraus wird ein $2^{o(\sqrt{|E|})}$-Algorithmus für \problem{Clique}.
|
|
\item Widerspruch zum Hinweis.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(\sqrt{n})}$, kein $2^{o(\sqrt{T})}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
\aufg{ETH-Schranke zeigen für ILP-Feasibility}
|
|
\textbf{Problem \problem{ILP-Feasibility}:}\\
|
|
\textbf{Gegeben:} Eine Matrix $A \in \mathbb{Z}^{M \times N}$ und eine rechte
|
|
Seite $b \in \mathbb{Z}^M$.\\
|
|
\textbf{Entscheide:} Gibt es einen Vektor $x \in \mathbb{Z}^N_{\ge 0}$ mit
|
|
$Ax \le b$?
|
|
|
|
Reduktion $\problem{3-SAT} \redp \problem{ILP-Feasibility}$: Aus Variablen
|
|
$x_1, \dots, x_n$ und Klauseln $C_1, \dots, C_m$ wird
|
|
\begin{itemize}
|
|
\item $N = 2n$ ILP-Variablen, je eine $x_\ell$ pro Literal $\ell$,
|
|
\item pro Klausel $C_i$ die Ungleichung $-\sum_{\ell \in C_i} x_\ell \le -1$,
|
|
\item pro Variable $v$ die Ungleichungen $x_v + x_{\bar v} \le 1$ und
|
|
$-x_v - x_{\bar v} \le -1$.
|
|
\end{itemize}
|
|
\begin{enumerate}
|
|
\item[a)] Geben Sie die Zeilenzahl $M$ und die Spaltenzahl $N$ der ILP-Instanz in
|
|
Abhängigkeit von $n$ und $m$ an.
|
|
\item[b)] Beweisen Sie die ETH-Schranken für \problem{ILP-Feasibility} bzgl.\ $M$
|
|
und $N$ basierend auf der Reduktion.
|
|
\end{enumerate}
|
|
\emph{Hinweis:} Unter der ETH ist \problem{3-SAT} nicht in
|
|
$2^{o(n)} \cdot |I|^{O(1)}$ lösbar, mit dem Sparsification-Lemma auch nicht in
|
|
$2^{o(m)} \cdot |I|^{O(1)}$.
|
|
|
|
\lsg
|
|
\textbf{a)} $M = m + 2n$; wegen $n \le 3m$ also $M = O(m)$. \quad $N = 2n$.
|
|
|
|
\textbf{b)}
|
|
|
|
\textbf{Bzgl.\ $M$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{ILP-Feasibility} wäre in $2^{o(M)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $M = O(m)$ wird daraus ein $2^{o(m)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Widerspruch zur ETH nach dem Sparsification-Lemma.
|
|
\end{itemize}
|
|
|
|
\textbf{Bzgl.\ $N$:}
|
|
\begin{itemize}
|
|
\item Angenommen, \problem{ILP-Feasibility} wäre in $2^{o(N)} \cdot |I|^{O(1)}$ lösbar.
|
|
\item Wegen $N = 2n$ wird daraus ein $2^{o(n)}$-Algorithmus für \problem{3-SAT}.
|
|
\item Direkter Widerspruch zur ETH.
|
|
\end{itemize}
|
|
Bounds: kein $2^{o(M)}$, kein $2^{o(N)}$. \hfill$\square$
|
|
|
|
|
|
% ==================================================================
|
|
|
|
\end{document}
|