alg-fuer-np.tex

\documentclass{cheat-sheet}

\pdfinfo{
  /Title (Zusammenfassung Algorithmen für NP-harte Probleme)
  /Author (Tim Baumann)
}

\usepackage{tikz}
\usetikzlibrary{matrix}
\usepackage{dashbox}

\usepackage{nicefrac}

\newcommand{\Instances}{\mathcal{X}} % set of instances (of an optimization problem)
\newcommand{\Feasible}{\mathcal{F}} % set of feasible solutions (of an optimization problem)
\newcommand{\ObjFun}{Z} % objective function (of an optimization problem)
\newcommand{\Goal}{\odot} % whether to minimize or maximize
\newcommand{\OptTuple}{(\Instances{}, \Feasible{}, \ObjFun{}, \Goal)} % tuple defining an optimization problem
\newcommand{\MinOptTuple}{(\Instances{}, \Feasible{}, \ObjFun{}, \min)} % tuple defining an optimization problem where the goal is to minimize the objective function
\DeclareMathOperator{\Opt}{Opt} % optimal value
\newcommand{\size}[1]{\abs{#1}} % Größe (eines Terms)
\DeclareMathOperator{\NPO}{NPO} % non-deterministic polynomial-time optimization problem
\DeclareMathOperator{\PO}{PO} % polynomial-time optimization problem
\DeclareMathOperator{\APX}{APX} % polynomial-time approximable optimization problem
\DeclareMathOperator{\NP}{NP} % nondeterministic polynomial-time problems
\let\P\relax % undefine \P
\DeclareMathOperator{\P}{P} % polynomial-time problems
\DeclareMathOperator{\PTAS}{PTAS} % polynomial-time approximation schema, class of problems in NPO that possess such
\DeclareMathOperator{\APTAS}{APTAS} % asymptotic polynomial-time approximation schema, class of problems in NPO that possess such
\DeclareMathOperator{\FPTAS}{FPTAS} % fully polynomial-time approximation schema, class of problems in NPO that possess such
\DeclareMathOperator{\AFPTAS}{AFPTAS} % asymptotic fully polynomial-time approximation schema, class of problems in NPO that possess such
\DeclareMathOperator{\PCP}{PCP} % probabilistically checkable proofs
\newcommand{\Prob}{\mathcal{P}} % Optimierungsproblem
\newcommand{\ManyOneRed}{\leq_m} % Many-To-One-Reduzierbarkeit
\newcommand{\TuringRed}{\leq_T} % Turing-Reduzierbarkeit
\newcommand{\TuringEq}{\equiv_T} % Turing-Äquivalenz
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\Powerset}{\mathcal{P}} % Potenzmenge
\renewcommand{\O}{\mathcal{O}} % Landau-Notation
\newcommand{\ceil}[1]{\lceil #1 \rceil} % Aufrunden
\newcommand{\floor}[1]{\lfloor #1 \rfloor} % Abrunden
\DeclareMathOperator{\Neighbors}{Neighbors} % Nachbarknoten (in einem Graphen)
\DeclareMathOperator{\treewidth}{tw} % Baumweite
\newcommand{\boundary}{\partial} % topologischer Rand

\newcommand{\KCircle}{\tikz{\draw (0,0) circle (2pt);}}
\newcommand{\KSquare}{\tikz{\draw (0,0) rectangle (4pt, 4pt);}}
\newcommand{\KCircleUnsel}{\tikz{\draw [fill=black] (0,0) circle (2pt);}}
\newcommand{\KSquareUnsel}{\tikz{\draw [fill=black] (0,0) rectangle (4pt, 4pt);}}
\newcommand{\KCircleSel}{\tikz{\draw [fill=red] (0,0) circle (2pt);}}
\newcommand{\KSquareSel}{\tikz{\draw [fill=red] (0,0) rectangle (4pt, 4pt);}}

\newcommand{\IndentState}[1]{\State \quad #1}

\definecolor{YoutubeColor}{rgb}{0.7019607843,0.0705882352941182,0.090196078431373} % https://www.youtube.com/yt/brand/en/color.html
\newcommand{\Youtube}[1]{\href{https://www.youtube.com/watch?v=#1}{\textcolor{YoutubeColor}{$\blacktriangleright$}}}

% Hervorhebung von Algorithmen und Problemen
\definecolor{AlgorithmColor}{rgb}{0.7,0.2,0.0}
\newcommand{\Algorithm}[1]{\textcolor{AlgorithmColor}{\textbf{#1}}}
\definecolor{ProblemColor}{rgb}{0.1,0.5,0.4}
\newcommand{\Problem}[1]{\textcolor{ProblemColor}{\textbf{#1}}}
\definecolor{DefinitionColor}{rgb}{1,0.255,0.212}
\newcommand{\Defn}[1]{\textcolor{DefinitionColor}{#1}}
\newcommand{\scriptSection}[1]{\textcolor{gray}{#1}\enspace}

\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}

% Kleinere Klammern
\delimiterfactor=701

\setlength{\tabcolsep}{2pt}

\begin{document}

\raggedcolumns % stretche Inhalt nicht über die gesamte Spaltenhöhe

\maketitle{Algorithmen für NP-harte Probleme}

Dies ist eine Zusammenfassung zur gleichnamigen Vorlesung von Professor Dr. Torben Hagerup im Sommersemester 2017.

\section{\scriptSection{1} Allgemeine Definitionen}

% §1. Introduction

% §2. Basic Definitions

% §2.1. Basic Definitions

% 2.1
\begin{defn}
  Ein \emph{Optimierungsproblem} ist ein Tupel $\OptTuple$ wobei
  \begin{itemize}
    \item $\Instances \subseteq \{0,1\}^{*}$ eine Menge von \emph{Instanzen},
    \item $\Feasible$ eine Abb.\ ist, die jeder Inst.~$x \in \Instances$ eine Menge $\Feasible(x) \subseteq \{0,1\}^{*}$ von \emph{möglichen} (oder \textit{zulässigen}) \emph{Lösungen} zuordnet,
    \item $\ObjFun$ eine Abbildung (die \emph{Zielfunktion}) ist, die jedem $x \in \Instances$ und $y \in \Feasible(x)$ einen \textit{Zielwert} $Z(x, y) \in \R$ zuordnet und
    \item $\Goal \in \{ \min, \max \}$ angibt, ob die Zielfunktion minimiert oder maximiert werden soll.
  \end{itemize}
\end{defn}

% 2.2
\begin{defn}
  Eine \emph{optimale Lösung} eines Optimierungsproblems $\OptTuple$ zu einer Instanz~$x \in \Instances$ ist ein $y \in \Feasible(x)$ mit
  \[ \ObjFun(x, y) = \Goal_{y \in \Feasible(x)} Z(x, y) =: \Opt(x). \]
\end{defn}

% 2.3
\begin{defn}
  Ein Algorithmus \emph{löst} ein Optimierungsproblem~$\OptTuple$, falls er für jedes $x \in \Instances$
  \begin{itemize}
    \item eine optimale Lösung $y \in \Feasible(x)$ berechnet, falls solch eine existiert,
    \item "`unmöglich"' ausgibt, falls keine Lösung existiert oder
    \item "`möglich, aber keine optimale Lösung"' sonst.
  \end{itemize}
\end{defn}

% 2.4
\begin{defn}
  \Defn{$\NPO$} ist die Klasse aller Opt.-Probleme~$\OptTuple$ mit
  \begin{itemize}
    \item $\Instances{} \in P$
    \item Es gibt ein Polynom~$p$, sodass für alle $x \in X$
    \begin{itemize}
      \item $\size{y} \leq p(\size{x})$ für alle $y \in \Feasible(x)$ und
      \item für alle Wörter~$w$ der Länge $\size{w} \leq p(\size{x})$ in polynomieller Zeit~(in~$\size{x}$) entscheidbar ist, ob $w \in \Feasible(x)$.
    \end{itemize}
    \item Die Funktion $\ObjFun$ ist in polynomieller Zeit berechenbar.
  \end{itemize}
\end{defn}

\begin{bem}
  Ist $\Prob \in \NPO$, so ist für jede Instanz $x \in \Instances$ die Menge der zulässigen Lösungen endlich.
  Somit gibt es entweder eine optimale Lösung oder nicht einmal eine zulässige Lösung.
\end{bem}

\begin{samepage}

% 2.5
\begin{defn}
  $\Defn{\PO} \subseteq \NPO$ ist die Subklasse für die ein Lösungsalgorithmus existiert, der in Polynomialzeit läuft.
\end{defn}

% 2.6
\begin{beob}
  $\P \neq \NP \implies \PO \neq \NPO$
\end{beob}

% §2.2. Evaluation and Decision Problems
\subsection{\scriptSection{1.1} Auswertungs- und Entscheidungsproblem}

% 2.7
\begin{defn}
  Sei $\Prob = \MinOptTuple$ ein Optimierungsproblem.
  \begin{itemize}
    \item Das zugeh. \emph{Auswertungsproblem}~$\Prob_E$ ist: Gegeben $x \in \Instances$,
    \begin{itemize}
      \item berechne $\Opt(x)$, falls $x$ eine optimale Lösung besitzt,
      \item gib "`zul. Lösungen, aber keine optimale"' aus, falls dies zutrifft,
      \item oder gib "`unmöglich"' aus, falls keine zulässige Lösung existiert.
    \end{itemize}
    \item Das zugeh. \emph{Entscheidungsproblem}~$\Prob_D$ ist: Gegeben $x \in \Instances$ und $k \in \Q$, gibt es eine Lösung $y \in \Feasible(x)$ mit $Z(x, y) \leq k$?
  \end{itemize}
\end{defn}

\end{samepage}

% 2.8
\begin{lem}
  $\Prob \in \NPO \implies \Prob_D \in \mathrm{NP}$
\end{lem}

% 2.9
\begin{defn}
  \begin{itemize}
    \item Ein Entscheidungsproblem~$\Prob_1$ ist (in Polynomialzeit) auf ein Entscheidungsproblem~$\Prob_2$ \emph{many-to-one-reduzierbar} (notiert $\Prob_1 \ManyOneRed \Prob_2$) falls eine (in Polynomialzeit) berechenbare Funktion $f : \{ \text{Instanzen von~$\Prob_1$} \} \to \{ \text{Instanzen von~$\Prob_2$} \}$ existiert, sodass die Antwort auf eine Instanz~$x$ von~$\Prob_1$ gleich der Antwort auf die Instanz $f(x)$ von~$\Prob_2$ ist.
    \item Ein Problem $\Prob_1$ ist (in Polynomialzeit) auf ein Problem~$\Prob_2$ \emph{Turing-reduzierbar} (notiert $\Prob_1 \TuringRed \Prob_2$) falls ein Algorithmus existiert, der unter Verwendung eines Orakels für~$\Prob_2$ das Problem~$\Prob_1$ (in Polynomialzeit) löst.
  \end{itemize}
\end{defn}

% 2.12
\begin{beob}
  $
    \Prob_1 \ManyOneRed \Prob_2 \implies
    \Prob_1 \TuringRed \Prob_2
  $
\end{beob}

% 2.10
\begin{beob}
  Sei $\Prob \in \NPO$.
  Dann gilt $\Prob_D \TuringRed \Prob_E \TuringRed \Prob$.
\end{beob}

% 2.11 und 2.13
\begin{satz}
  Sei $\Prob = \OptTuple \in \NPO$ mit $\im(Z) \subseteq \Z$.
  \begin{itemize}
    \item Es gilt $\Prob_D \TuringEq \Prob_E$.
    \item Angenommen, $\Prob_D$ ist NP-vollständig. Dann gilt $\Prob \TuringEq \Prob_D$.
  \end{itemize}
\end{satz}

\begin{beweisskizze}
  \begin{itemize}
    \item
      Es gilt $\abs{Z(x, y)} \leq 2^{q(\size{x})}$ für ein Polynom~$x$. \\
      Der optimale Wert lässt sich durch binäre Suche unter Verw.\ des Orakels in der Menge möglicher Werte bestimmen.
    \item
      O.\,B.\,d.\,A. seien die zul. Lösungen als natürliche Zahlen kodiert, sodass ein ganzzahliges Polynom $q$ existiert mit $y < q(\size{x})$ für alle $x \in \Instances{}$ und $y \in \Feasible(x)$.
      Betrachte nun $\Prob' = (\Instances{}, \Feasible{}, \ObjFun{}', \Goal{})$ mit $\ObjFun'(x, y) \coloneqq 2^{q(\size{x})} \cdot Z(x, y) + y \in \Z$.
      Sei $\theta$ der Optimalwert von~$\Prob'$ zur Instanz~$x \in \Instances$.
      Dann ist $y = \theta \,\mathrm{mod}\, q(\size{x})$ eine optimale Lösung der Instanz~$x$ von~$\Prob$.
      Dies zeigt $\Prob \TuringRed \Prob_E$.
      Es gilt nun
      \[
        \Prob \TuringRed
        \Prob'_E \TuringRed
        \Prob'_D \TuringRed
        \Prob_D \TuringRed
        \Prob,
      \]
      wobei die zweite Reduktion aus Punkt~1 und die dritte aus der NP-Vollständigkeit von $\Prob_D$ folgt.
  \end{itemize}
\end{beweisskizze}

\begin{samepage}

% 2.14
\begin{defn}
  Ein Optimierungsproblem~$\Prob$ heißt \emph{NP-hart}, falls $\Prob' \TuringRed \Prob$ für jedes Entscheidungsproblem $\Prob'$ in~$\NP$.
\end{defn}

% 2.15
\begin{beob}
  $\Prob \in \NPO$, $\Prob_D$ NP-vollständig $\implies$ $\Prob$ NP-hart
\end{beob}

\subsection{\scriptSection{4.1, 4.2} Approximationslösungen und -fehler}

% 4.1
\begin{defn}
  Ein \emph{Approximationsalgorithmus} für ein Optimierungsproblem~$\OptTuple$ ist ein Algorithmus, der für jedes $x \in \Instances$ eine zulässige Lösung $y \in \Feasible(x)$ produziert.
\end{defn}

% 4.2
\begin{defn}
  Sei $x \in \Instances$ eine Instanz, für die $\Opt(x)$ existiert. \\
  Der \emph{absolute Fehler} von $y \in \Feasible(x)$ ist $\abs{Z(x, y) - \Opt(x)}$.
  % ausgelassen: zweiter Teil der Definition
\end{defn}

\end{samepage}

% 4.5
\begin{defn}
  Gelte $Z \geq 0$.
  Der \emph{relative Fehler} von $y \in \Feasible(x)$ zu~$x \in \Instances$ ist
  \[
    \begin{cases}
      0 & \text{falls } \Goal = \min, \ObjFun(x, y) = \Opt(x) = 0, \\
      (\ObjFun(x, y) - \Opt(x)) / \ObjFun(x, y) & \text{falls } \Goal = \min, Z(x, y) > 0, \\
      (\Opt(x) - \ObjFun(x, y)) / \Opt(x) & \text{falls } \Goal = \max.
    \end{cases}
  \]
\end{defn}

\begin{bem}
  Der relative Fehler ist eine Zahl in~$\cinterval{0}{1}$.
  Eine Lösung ist genau dann optimal, falls ihr relativer Fehler $= 0$ ist.
\end{bem}

% 4.5
\begin{defn}
  Ein \emph{$\epsilon$-Approximationsalgorithmus} ($\epsilon \in \cinterval{0}{1}$) für~$\Prob$ ist ein Algorithmus, der für jedes $x \in \Instances$ ein $y \in \Feasible(x)$ mit relativem Fehler $\leq \epsilon$ berechnet.
  Das Problem~$\Prob$ heißt \emph{$\epsilon$-approximierbar}, falls ein solcher Alg.\ mit polynomieller Laufzeit existiert.
\end{defn}

% 4.6
\begin{defn}
  Sei $\Prob = \OptTuple$ ein Optimierungsproblem mit $Z \geq 0$. \\
  Das \emph{Approximationsverhältnis} von $y \in \Feasible(x)$ zu $x \in \Instances$ ist
  \[
    \begin{cases}
      1 & \text{falls } \ObjFun(x, y) = \Opt(x) = 0, \\
      \Opt(x) / \ObjFun(x, y) \in \cinterval{1}{\infty} & \text{falls } \Goal = \min, \Opt(x) > 0, \\
      \ObjFun(x, y) / \Opt(x) \in \cinterval{1}{\infty} & \text{falls } \Goal = \max, \ObjFun(x, y) > 0.
    \end{cases}
  \]
\end{defn}

\begin{bem}
  Das Approximationsverh.\ ist eine Zahl in~$\cinterval{1}{\infty}$.
  Eine Lösung ist genau dann optimal, falls ihr Approximationsverh. $= 1$ ist.
\end{bem}

\begin{defn}
  Ein Alg.\ heißt \emph{$r$-Approximationsalgorithmus} ($r \in \ocinterval{1}{\infty}$), falls er für jedes $x \in \Instances$ ein $y \in \Feasible(x)$ mit Approximationsverhältnis $\leq r$ liefert.
  Das Problem~$\Prob$ heißt \emph{$r$-approximierbar}, falls ein solcher Algorithmus mit polynomieller Laufzeit existiert.
\end{defn}

\begin{bem}
  Für das Approximationsverhältnis~$r$ und den relativen Fehler~$\epsilon$ von $y \in \Feasible(x)$ gilt
  \[
    r = 1 / (1-\epsilon), \qquad
    \epsilon = 1 - 1/\epsilon.
  \]
\end{bem}

% 4.7
\begin{defn}
  $\Defn{\APX}$ ist die Klasse aller Probleme in NPO, die $r$-approximierbar für ein $r > 1$ sind.
\end{defn}

\subsection{\scriptSection{7} Polynomialzeit-Approximationsschemata}

% 7.2
\begin{defn}
  Ein \emph{Polynomialzeit-Approximationsschema} (PTAS) für $\Prob \in \NPO$ ist ein Algorithmus, der für jede Instanz~$x$ von~$\Prob$ und $\epsilon > 0$ eine mögliche Lösung in~$\Feasible(x)$ mit relativem Fehler $\leq \epsilon$ liefert und dessen Laufzeit für jedes fixe $\epsilon > 0$ polynomiell in~$\size{x}$ ist.
\end{defn}

\begin{defn}
  $\Defn{\PTAS} \coloneqq \Set{\Prob \in \NPO}{\text{$\Prob$ hat ein PTAS}}$
\end{defn}

% 7.5
\begin{defn}
  Ein \emph{asymptot. Polynomialzeit-Approximationsschema} (APTAS) für $\OptTuple{}$ ist ein Algorithmus, der für alle $x \in \Instances{}$ und $\epsilon > 0$ eine mögliche Lösung $y \in \Feasible(x)$ mit
  \[ \abs{Z(x, y) - \Opt(x)} \leq \epsilon \cdot \max \{ Z(x,y), \Opt(x) \} + K \]
  für eine Konstante~$K$ berechnet und dessen Laufzeit für alle festen~$\epsilon$ polynomiell in $\size{x}$ ist.
\end{defn}

\begin{defn}
  Ein (asympt.) \emph{Voll-Polynomialzeit-Approx'schema} ((A)FPTAS) für $\Prob{}$ ist ein (A)PTAS für~$\Prob{}$, dessen Laufzeit für die Instanz $(x, \epsilon)$ durch ein Polynom in $\size{x}$ und in~$1/\epsilon$ beschränkt ist.
\end{defn}

\begin{defn}
  $\Defn{\mathrm{(A)(F)PTAS}} \coloneqq \Set{\Prob \in \APX}{\text{$\Prob$ hat ein (A)(F)PTAS}}$
\end{defn}

\begin{center}
  \begin{tikzpicture}
    \matrix (mat) [matrix of nodes, column sep=0.5cm, row sep=0.3cm]{
      && \node (PTAS) {$\PTAS$}; \\
      \node (PO) {$\PO$}; &
      \node (FPTAS) {$\FPTAS$}; &&
      \node (APTAS) {$\APTAS$}; &
      \node (APX) {$\APX$}; &
      \node (NPO) {$\NPO$}; \\
      && \node (AFPTAS) {$\AFPTAS$}; \\
    };
    \draw (PO) to (FPTAS);
    \draw (FPTAS) to (PTAS);
    \draw (FPTAS) to (AFPTAS);
    \draw (PTAS) to (APTAS);
    \draw (AFPTAS) to (APTAS);
    \draw (APTAS) to (APX);
    \draw (APX) to (NPO);
  \end{tikzpicture}
\end{center}

\section{Optimierungsprobleme (in $\NPO$)}

\subsection{Überdeckungsprobleme}

\begin{problem}[\Problem{Minimum Vertex Cover}, MVC]
  Geg.\ einen unger. Graphen~$G = (V, E)$, berechne eine \textit{Knotenüberdeckung}~$C$, \dh{}
  \[
    \fa{v, w \in V} \{v, w\} \in E \implies v \in C \vee w \in C,
  \]
  die minimale Größe~$\size{C}$ unter allen Knotenüberdeckungen besitzt.
\end{problem}

\begin{problem}[\Problem{Minimum Weighted Vertex Cover}]
  Geg.\ einen unger. Graphen~$G = (V, E)$ und eine \textit{Kostenfunktion} $c : V \to \R_{\geq 0}$, berechne eine \textit{Knotenüberdeckung}~$C$, die minimale \textit{Kosten} ${\sum}_{v \in C} c(v)$ unter allen Knotenüberdeckungen besitzt.
\end{problem}

\begin{problem}[\Problem{Maximum Independent Set}, MIS]
  Geg.\ einen unger. Graphen~$(V, E)$, berechne eine \textit{unabh. Menge}~$M \subseteq V$, \dh{}
  \[
    \fa{v \in M} \fa{w \in V} (v, w) \in E \implies w \not\in M,
  \]
  die maximale Größe~$\size{M}$ unter allen unabhängigen Mengen besitzt.
\end{problem}

\begin{bem}
  Für einen Graphen $(V, E)$ und eine Teilmenge $S \subseteq V$ gilt: \\
  $S$ ist (max.) unabh. Menge $\iff$ $V \setminus S$ ist (min.) Vertex Cover \\
\end{bem}

\begin{problem}[\Problem{Minimum Set Cover}]
  Gegeben seien $n \in \N$ und $\mathcal{C}_0 \subseteq \Powerset(\{ 1, \ldots, n \})$.
  Die Menge der möglichen Lösungen ist
  \[ \Feasible \coloneqq \Set{\mathcal{C} \subseteq \mathcal{C}_0}{{\bigcup}_{S \in \mathcal{C}} S = {\bigcup}_{S \in \mathcal{C}_0} S} \]
  Aufgabe: Finde $\mathcal{C} \in \Feasible$ mit minimalem $\size{\mathcal{C}}$!
\end{problem}

\begin{bem}
  Minimum Set Cover verallgemeinert Minimum Vertex Cover, (Black-and-White) Dominating Set und Edge Dominating Set.
\end{bem}

\subsection{Graphenfärbungen}

\begin{problem}[\Problem{Minimum Vertex Coloring}, \Youtube{4FE79y_JkCE}]
  Gegeben sei ein unger. Graph~$G = (V, E)$.
  Die Menge der \textit{Eckenfärbungen} ist
  \[
    \Feasible \coloneqq \Set{\text{Abbildungen } c : V \to \N}{\fa{\{v, w\} \in E} c(v) \neq c(w)}.
  \]
  Ziel: Finde $c \in \Feasible$ mit minimaler Anzahl $\max c(V)$ an Farben.
\end{problem}

\begin{problem}[\Problem{Minimum Edge Coloring}]
  Gegeben sei ein unger. Graph~$G = (V, E)$.
  Die Menge der \textit{Kantenfärbungen} ist
  \[
    \Feasible \coloneqq \Set{\text{Abb. } c : E \to \N}{\fa{e_1 \neq e_2 \in E} e_1 \cap e_2 \neq \emptyset \implies c(e_1) \neq c(e_2)}
  \]
  Ziel: Finde $c \in \Feasible$ mit minimaler Anzahl $\max c(V)$ an Farben.
\end{problem}

\subsection{Dominierende Mengen (in Graphen)}

\begin{problem}[\Problem{Minimum Dominating Set}]
  Gegeben sei ein Graph $G \!=\! (V, E)$.
  Mengen $D \subseteq V$ mit $V = D \cup \Neighbors_G(D)$ heißen \emph{dominierend}.
  Ziel: finde domin. Menge~$D$ kleinster Größe~$\size{D}$!
\end{problem}

\begin{problem}[\Problem{Black-and-White Dominating Set}]
  Gegeben einen unger. Graph $G = (B \cup W, E)$ mit $B \cap W = \emptyset$, finde ein $D \subseteq B \cup W$ minimaler Größe, sodass $B \subseteq D \cup \Neighbors_G(D)$.
\end{problem}

\begin{problem}[\Problem{Edge Dominating Set}]
  Gegeben einen unger. Graph $G$ und $k \in \N$.
  Frage: Gibt es eine Kantendominierung der Größe $\leq k$, \dh{} gibt es ein $D \subseteq E$ mit $\size{D} \leq k$, sodass jede Kante in~$E$ mindestens einen Endpunkt mit einer Kante aus~$D$ gemeinsam hat?
\end{problem}

\subsection{Probleme in unger. Graphen mit Kantengewichten}

\begin{problem}[\Problem{Minimum TSP}]
  Gegeben sei ein vollständiger unger. Graph $G = (V, E)$ und eine Abb. $c : E \to \R_{\geq 0}$.
  % Gegeben sei eine endliche Menge $V$ und eine Abb. $c : V \times V \to \R_{\geq 0}$ mit $c(x, y) = c(y, x)$ für alle $x, y \in V$.
  Gesucht ist eine zyklische Permutation $\sigma$ von~$V$ (eine \textit{Tour}), sodass die \textit{Länge} ${\sum}_{v \in V} c(\{ v, \sigma(v) \})$ minimal wird.
\end{problem}

\begin{problem}[\Problem{Minimum $\Delta$-TSP}]
  Gegeben sei ein endlicher metrischer Raum~$(V, c)$.
  Gesucht ist eine zyklische Permutation $\sigma$ von~$V$ (eine \textit{Tour}), sodass die \textit{Länge} ${\sum}_{v \in V} c(v, \sigma(v))$ minimal wird.
\end{problem}

\begin{problem}[\Problem{Minimum Steiner Forest}]
  Geg.\ sei ein unger. Graph $G = (V, E)$ eine \textit{Kostenfktn} $c : E \to \R_{\geq 0}$ und eine Abb. $r : V \to \N$.
  Mögliche Lsgn sind Teilmengen $F \subseteq E$ von~$G$, sodass alle $u, v \in V$ mit $r(u) = r(v)$ durch einen Pfad mit Kanten in~$F$ verbunden sind.
  Gesucht ist ein solcher Subgraph, der ${\sum}_{e \in E_F} c(e)$ minimiert.
\end{problem}

\subsection{Satisfiability}

\begin{problem}[\Problem{$k$-SAT(isfiability)}] \mbox{} \\
  Gegeben sei eine Formel in konjunktiver Normalform, etwa
  \[ (x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_3} \vee x_4 \vee \overline{x_5}) \wedge (x_2 \vee x_5) \wedge (x_3 \vee \overline{x_4}). \]
  Die Maximalzahl an \textit{Literalen} in einer \textit{Clause} sei dabei $\leq k$.
  Entscheide, ob die Formel \emph{erfüllbar} ist,\dh{} ob es eine Zuweisung der Variablen gibt, sodass die Formel wahr ist.
\end{problem}

\begin{samepage}

\begin{problem}[\Problem{MaxSAT}]
  Geg.\ eine Formel in KNF, finde eine Variablenzuweisung, die die Anzahl der gültigen Clauses maximiert.
\end{problem}

\subsection{Packungs- und Scheduling-Probleme}

\begin{problem}[\Problem{Minimum Makespan Scheduling}]
  Seien $p, n \in \N$ und $l_1, \ldots, l_n \in \R_{> 0}$ gegeben.
  Für $f : \{ 1, \ldots, n \} \to \{ 1, \ldots, p \}$ setze
  \[ t(f) \coloneqq \max_{1 \leq i \leq p} \sum_{j \in f^{-1}(i)} l_j. \]
  Berechne das~$f$, für das $t(f)$ minimal wird!
\end{problem}

\end{samepage}

\begin{interp}
  $p$ ist die Anzahl von \textit{Arbeitern},
  $l_1, \ldots, l_n$ sind die Längen von zu erledigenden \textit{Jobs}
  und $t(f)$ ist die \textit{Gesamtdauer} bei der durch~$f$ gegebenen Verteilung der Jobs auf die Arbeiter an.
\end{interp}

\begin{bem}
  MMS ist NP-hart, da das zugeh. Entscheidungsproblem Bin Packing bekannterweise NP-hart ist.
\end{bem}

\begin{problem}[\Problem{Maximum Knapsack}]
  Seien $n \in \N$ und $v_1, \ldots, v_n$, $w_1, \ldots, w_n, W \in \R_{> 0}$ gegeben.
  Die Menge der möglichen Lsgn sei
  \[ \Feasible \coloneqq \Set{S \subseteq \{ 1, \ldots, n \}}{{\sum}_{i \in S} w_i \leq W}. \]
  Gesucht: ${\argmax}_{S \in \Feasible} {\sum}_{i \in S} v_i$
\end{problem}

\begin{interp}
  Man wählt unter $n$ Sachen mit jeweils einem \textit{Gewicht}~$w_i$ und einem \textit{Nutzwert}~$v_i$ diejenigen aus, die man in einen Rucksack packt, sodass das Gesamtgewicht eine festgelegte Grenze~$W$ nicht übersteigt und der Nutzen maximal wird.
\end{interp}

\begin{problem}[\Problem{Maximum Integer Knapsack}] \mbox{}\\
  Wie Maximum Knapsack aber mit $v_1, \ldots, v_n \in \N_{> 0}$.
\end{problem}

\begin{problem}[\Problem{Minimum Bin Packing}]
  Gegeben seien \textit{Objektgrößen} $v_1, \ldots, v_n \in \cinterval{0}{1}$.
  \textit{Packungen} sind Abbildungen $f : \{ 1, \ldots, n \} \to \N$, die jedem \textit{Objekt} einen \textit{Behälter} (mit Volumen 1) zuweisen, sodass
  \[
    {\sum}_{i \in f^{-1}(j)} v_i \leq 1 \quad
    \text{für alle $j \in \N$.}
  \]
  Gesucht ist ein~$f$ mit minimaler Anzahl $\max \im(f)$ von Behältern.
\end{problem}

\section{Übersicht}

\begin{description}
  \item[Vertex Cover]
    für Intervallgraphen in~$\PO$ (§3.2), \\
    lösbar in $\O(\alpha_0^n \cdot m + n)$ mit $\alpha_0 \approx 1,325$ (§5.4), \\
    Parametrisierung mit Zeit $\O(k^2 \cdot \alpha_0^k + n + m)$ möglich (§8.1), \\
    mit Baumzerl.\ der Weite $\leq k$ lösbar in $\O(k 2^k n + k m)$ (§9.4), \\
    2-approximierbar (sogar mit Gewichten, §10.2), \\
    für bipartite Graphen in~$\PO$ (§12), \\
    linearer Kernel berechenbar in~$\O(n+m)$ (§12)

  \item[Independent Set]
    für Intervallgraphen in~$\PO$ (§3.2), \\
    für planare Graphen Param.\ mit Zeit $\O(6^k \cdot n)$ möglich (§9.2), \\
    mit Baumzerl.\ der Weite $\leq k$ lösbar in $\O(k 2^k n + k m)$ (§9.4), \\
    für planare Graphen gibt es PTAS mit $\tfrac{k}{k+1}$-Approx.\ in Zeit~$\O(k^2 2^{3 k} n)$ (§9.4), \\
    für bipartite Graphen in~$\PO$ (§12),

  \item[Set Cover]
    $H_n$-approximierbar (§3.5)

  \item[Vertex Coloring]
    $\O(n / \log n)$-approximierbar (§4.4), \\
    bei planaren Graphen mit 5 Farben möglich (und Absolutfehler $\leq 2$, ÜA 9.5)

  \item[Edge Coloring]
    approximierbar mit abs. Fehler~$1$ (§4.1)

  \item[Dominating Set]
    für planare Graphen Parametrisierung mit Zeit $\O(7^k \cdot n)$ wobei $k \leq n/28$ möglich (§9.2)

  \item[TSP]
    $\not\in \APX$ (falls $\P \neq \NP$, §4.3)

  \item[$\Delta$-TSP]
    $(3/2)$-approximierbar (§4.3)

  \item[Steiner Forest]
    2-approximierbar (§10.4)

  \item[3-SAT]
    lösbar in $\O(\abs{F} \cdot \alpha_0^n)$ mit $\alpha_0 \approx 1,84$ (§5.3)

  \item[MaxSAT]
    $\not\in \PTAS$ (falls $\P \not \in \NP$, §11), \\
    trivial $1/2$-approximierbar (§8.2), \\
    Parametrisierung mit Zeit $\O(k^2 \phi^k + \abs{F})$ möglich (§8.2), \\
    im Erwartungswert $3/4$-approximierbar (§10.3)

  \item[Makespan Scheduling]
    $(3/4)$-approximierbar (§3.3)

  \item[Knapsack]
    $(1/2)$-approximierbar (§3.4), \\
    Integer Knapsack pseudopolynomiell in~$\O(n V)$ (§6.1), \\
    FPTAS mit~$\O(n^3 / \epsilon)$ (§7),

  \item[Bin Packing]
    $\not\in \PTAS$ (falls $\P \neq \NP$, §7), \\
    lösbar mit $r$ versch. Größen in~$\O(n^{2r + 2})$ (§6.2), \\
    APTAS mit $(1+\delta) z^* + 1$ Bins in Zeit $\O(n^{8 / \delta^2 + 2})$ (§7)
\end{description}

\newpage

\section{Algorithmen für Probleme in~$\NPO$}

% §3. The Greedy Strategy

% §3.1 A cabin manager's problem
\subsection{\scriptSection{3.2} Gieriges \Problem{Cabin Manager's Problem}}

\begin{defn}
  Ein \emph{Intervallmodell} eines Graphen $G = (V, E)$ ist eine Abbildung $\phi : E \to \Set{\cinterval{a}{b}}{a, b \in \Q}$, sodass
  \[
    \fa{v \neq w \in V} \enspace
    (v, w) \in E \iff \phi(v) \cap \phi(w) \neq \emptyset.
  \]
  Ein Graph heißt \emph{Intervallgraph}, falls er ein Intervallmodell besitzt.
\end{defn}

\begin{problem}[\textit{Cabin Manager's Problem}]
  MIS auf Intervallgraphen
\end{problem}

% §3.2 Maximum Independent Set for Interval Models

\begin{alg}
  Beginne mit $C \coloneqq \emptyset$, füge dann wiederholt gierig das vom aktuellen~$C$ unabhängige Intervall mit dem kleinsten Endpunkt zu~$C$ hinzu, bis es kein solches Intervall mehr gibt.
\end{alg}

\begin{satz}
  Dieser Algorithmus berechnet tatsächlich ein MIS\@.
\end{satz}

% §3.3. Minimum Makespan Scheduling
\subsection{\scriptSection{3.3} Gieriges \Problem{Minimum Makespan Scheduling}}

\begin{alg}
  Gehe die Jobs in nach Dauer absteigender Reihenfolge durch, weise jeden Job dem Arbeiter zu, der bisher am wenigsten ausgelastet ist.
\end{alg}

\begin{satz}
  Das Approximationsverhältnis der berechneten zul. Lösung ist
  \[ \leq \nicefrac{4}{3} - \nicefrac{1}{3 p}. \]
\end{satz}

\begin{beweisskizze}
  Sei $t$ die Länge des letzten Jobs des am längsten beschäftigten Arbeiters und $z^*$ die minimale Gesamtdauer.
  \begin{itemize}
    \item Falls $t > z^*/3$, so hat der Alg. sogar eine optimale Lsg gefunden.
    \item Falls $t \leq z^*/3$, so folgt die Behauptung durch geeign. Abschätzen.
  \end{itemize}
\end{beweisskizze}

\begin{kor}
  Minimum Makespan Scheduling ist $(1/4)$-approximierbar.
\end{kor}

% §3.4. Maximum Knapsack
\subsection{\scriptSection{3.4} Gieriges \Problem{Maximum Knapsack Packing}}

\begin{alg}
  Gehe die Sachen absteigend nach ihrem Nutzen-Kosten-Verhältnis~$\nicefrac{v_i}{w_i}$ durch und packe jede Sache ein, die noch in den Rucksack passt.
  Sei~$z$ der Gesamtnutzen des so zusammengestellten Sets.
  Falls eine Sache mit Nutzen $v_i > z$ (und $w_i \leq W$) nicht eingepackt wurde, so räume den Rucksack wieder aus und packe als einziges diese Sache ein.
\end{alg}

\begin{satz}
  Der relative Fehler der durch diesen Algorithmus berechneten Approximationslösung ist $\leq 1/2$.
\end{satz}

\begin{beweisskizze}
  Sei $z^*$ der Gesamtnutzen einer optimalen Lösung und $j$ der Index der ersten vom gierigen Alg.\ nicht eingepackten Sache.
  Dann gilt $z^* \leq z + v_j \leq 2 \cdot \max \{ z, v_j \}$.
\end{beweisskizze}

\begin{kor}
  Maximum Knapsack ist $(1/2)$-approximierbar.
\end{kor}

% §3.5. Minimum Set Cover
\subsection{\scriptSection{3.5} Gieriges \Problem{Minimum Set Cover}}

\begin{alg}
  Beginne mit $\mathcal{C} \coloneqq \emptyset$, füge dann immer ein $T \in \mathcal{C}_0$ zu~$\mathcal{C}$ hinzu, welches
  \[ T \cap \left( {\bigcup}_{S \in \mathcal{C}_0} S \setminus {\bigcup}_{S \in \mathcal{C}} S \right) \]
  maximiert, bis ${\bigcup}_{S \in \mathcal{C}_0} S = {\bigcup}_{S \in \mathcal{C}} S =: U$.
\end{alg}

% 3.5
\begin{satz}
  Sei $n \coloneqq {\max}_{S \in \mathcal{C}_0} \size{S}$.
  Die vom Greedy-Alg.\ berechnete Lösung~$\mathcal{C}$ ist maximal um den Faktor $H_n \coloneqq {\sum}_{j=1}^n \nicefrac{1}{j} \leq 1 + \ln n$ größer als die optimale Lösung.
\end{satz}

\begin{beweisskizze}
  Seien $S_1, \ldots, S_t \in \mathcal{C}_0$ die vom Algorithmus nacheinander ausgewählten Mengen.
  Setze $T_i \coloneqq S_i \setminus (S_1 \cup \ldots \cup S_{i-1})$ für $i = 1, \ldots, t$.
  Für $x \in U$ sei
  \[
    w(x) \coloneqq 1/\size{T_i}, \quad
    \text{wobei $i$ dasjenige mit $x \in T_i$ ist.}
  \]
  Dann gilt für alle $S \in \mathcal{C}_0$, dass ${\sum}_{x \in S} w(x) \leq H_{\size{S}}$.
  Es folgt
  \[
    \size{\mathcal{C}} = t = \sum_{x \in U} w(x) \leq \sum_{S \in \mathcal{C}^*} \sum_{x \in S} w(x) \leq \size{\mathcal{C}^*} \cdot H_n.
  \]
\end{beweisskizze}

\begin{kor}
  Minimum Set Cover ist $(\ln n / (1 + \ln n))$-approximierbar (bei Eingabegröße~$n$).
\end{kor}

\begin{resultat}
  Der Worst-Case des Greedy-Algorithmus kann asympt.\ nicht verbessert werden:
  Es gibt keinen determ. Polynomialzeit-Alg.\ für MSC, der ein Approx'verh.\ von $\ln n - \epsilon$ mit $\epsilon > 0$ erreicht.
\end{resultat}

% §4 Approximation Algorithms

% §4.1 Absolute Approximation
\subsection{\scriptSection{4.1} Ein Approx'alg.\ für \Problem{Minimum Edge Coloring}}

% 4.3
\begin{satz}[\Algorithm{Vizings Algorithmus}, \Youtube{otky1bBhwgM}]
  Es gibt einen Algorithmus, der für jeden Graph $G = (V, E)$ eine Kantenfärbung mit höchstens $\Delta + 1$ Farben, wobei $\Delta \coloneqq {\max}_{v \in V} \deg_G(v)$, berechnet.
\end{satz}

\begin{alg}
  Sei $e_0 = \{ u, v_0 \} \in E$ beliebig.
  Induktiv dürfen wir annehmen, dass $c : E \setminus \{ e_0 \} \to \{ 0, \ldots, \Delta \}$ eine Kantenfärbung von $G - \{ e_0 \}$ ist.
  Setze $i \coloneqq 0$.
  Führe folgendende Schritte wiederholt aus, bis Fall A oder B eintrifft:

  \begin{enumerate}
    \item Sei $c_{i+1}$ eine Farbe, die an $v_i$ frei ist.
    \item Sei $e_{i+1} = \{ u, v_{i+1} \} \in E$ die Kante mit $c(e) = c_{i+1}$ (eine solche existiert, da A nicht gegeben ist).
    \item Erhöhe $i$ um eins.
  \end{enumerate}

  Abbruchbedingungen:
  \begin{enumerate}
    \item[A.] Falls ein minimales $j = 0, \ldots, i$ existiert, für das es eine Farbe $\tilde{c}$ gibt, die an~$v_j$ und~$u$ frei ist, so färbe wie folgt um und ein:
    \[
      c'(e_j) \coloneqq \tilde{c}, \enspace
      c'(e_{j-1}) \coloneqq c_j, \enspace
      \ldots, \enspace
      c'(e_1) \coloneqq c_2, \enspace
      c'(e_0) \coloneqq c_1
   \]
    \item[B.]
      Ansonsten, falls eine Farbe $c_k$ mit $0 \leq k < i$ an $v_i$ frei ist: \\
      Sei $d$ eine Farbe, die an~$u$ frei ist.
      Vertausche $c_k \leftrightarrow d$ in dem $\{ c_k, d \}$-Pfad, der~$v_i$ als Endpunkt enthält. \\
      Durch Fallunterscheidung über den anderen Endpunkt sieht man, dass danach Fall A anwendbar ist.
  \end{enumerate}
\end{alg}

\begin{kor}
  Es gibt einen Polynomialzeit-Approximationsalg.\ für Minimum Edge Coloring mit Absolutfehler~$\leq 1$.
\end{kor}

% Blatt 4, ÜA 4.1
\begin{kor}
  Minimum Edge Coloring ist $4/3$-approximierbar
\end{kor}

% §4.3. The Traveling Salesman Problem
\subsection{\scriptSection{4.3} Ein Approximationsalg.\ für \Problem{$\Delta$-TSP}}

\begin{erinnerung}
  Minimale Spannbäume für einen gewichteten ungerichteten Graphen können in polynomieller Zeit mit Kruskals oder mit Prims Algorithmus berechnet werden.
\end{erinnerung}

\begin{satz}
  Minimum $\Delta$-TSP ist 2-approximierbar.
\end{satz}

\begin{beweisskizze}
  Sei $(V, c)$ eine Instanz und $z^*$ die minimale Länge einer Tour.
  Berechne einen minimalen Spannbaum.
  Dessen Kanten haben eine Gesamtlänge von $\leq z^*$.
  Führe Tiefensuche im Spannbaum durch und liste jeden neu entdeckten Knoten auf.
  Die so erhaltene Tour hat (wegen der Dreiecksungleichung) Länge $\leq 2 z^*$.
\end{beweisskizze}

\begin{defn}
  Ein unger. Multigraph heißt \em{Eulersch}, falls er eine \textit{Eulertour} besitzt, also eine Tour, die jede Kante nur ein Mal benutzt.
\end{defn}

% 2.12
\begin{lem}
  Ein zshgder ungerichteter Multigraph ist genau dann Eulersch, wenn alle seine Knoten geraden Grad haben. \\
  In dem Fall kann man eine Eulertour in Polynomialzeit finden.
\end{lem}

\begin{kor}
  Sei $(V, c)$ eine Instanz des Minimum $\Delta$-TSP. \\
  Aus jedem Eulerschen Multigraph auf der Knotenmenge~$V$ mit Gesamtkantengewicht $C$ kann man eine TSP-Tour der Gesamtlänge~$\leq C$ in Polynomialzeit berechnen.
\end{kor}

% 4.13
\begin{defn}
  Sei $G = (V, E)$ ein unger. Graph.
  Ein \emph{Matching} in~$G$ ist eine Teilmenge $E' \subseteq E$, sodass $e \cap e' = \emptyset$ für alle $e, e' \in E'$ mit $e \neq e'$.
  Ein Matching heißt \emph{perfekt}, falls $V = \cup_{e \in E'} e$.
  Die \textit{Kosten} eines Matchings bzgl. einer Kostenfunktion $c : E \to \R_{\geq 0}$ sind ${\sum}_{e \in E'} c(e)$.
\end{defn}

% 4.14
\begin{satz}
  Ein Matching maximaler Größe mit minimalen Kosten (unter den Matchings maximaler Größe) kann für einen geg. Graphen~$G$ mit~$n$ Knoten in Zeit $n^{O(1)}$ berechnet werden.
\end{satz}

% 4.15
\begin{satz}[\emph{Christofides}]
  Minimum $\Delta$-TSP ist $3/2$-approximierbar.
\end{satz}

\begin{samepage}

\begin{beweisskizze}
  Sei $(V, c)$ eine Instanz und $z^*$ die minimale Länge einer Tour.
  Berechne einen min.\ Spannbaum.
  Berechne ein perfektes Matching mit minimalen Kosten auf den Knoten des Spannbaums mit ungeradem Grad.
  Die Kosten dieses Matchings sind $\leq z^* / 2$. \\
  Der Multigraph auf~$V$ bestehend aus den Kanten des Matchings und denen des Spannbaums ist Eulersch mit Gesamtkosten $\leq 3/2 z^*$. \\
  Aus diesem erhalten wir eine TSP-Tour der Länge $\leq 3/2 z^*$.
\end{beweisskizze}

\subsection{\scriptSection{4.4} Ein Approx'alg.\ für \Problem{Min. Vertex Coloring}}

\begin{alg}[\Algorithm{Greedy Vertex Coloring}] \mbox{}\\
  Wiederhole folgende Schritte, bis alle Knoten gefärbt sind:
  \begin{enumerate}
    \item
      Bestimme ein nicht-vergrößerbares IS~$I$ in~$G$ wie folgt: Setze $H \coloneqq G$, $I \coloneqq \emptyset$, dann führe folgende Schritte aus, solange $H \neq \emptyset$:
      \begin{enumerate}
        \item Wähle einen Knoten~$v$ minimalen Grades aus~$H$ aus.
        \item Füge $v$ zu~$I$ hinzu.
        \item Lösche $v$ und seine Nachbarknoten aus~$H$.
      \end{enumerate}
    \item Färbe alle Knoten in~$I$ in einer noch unbenutzten Farbe.
    \item Lösche die Knoten in~$I$ aus~$G$.
  \end{enumerate}
\end{alg}

\end{samepage}

\begin{satz}
  Greedy Vertex Coloring ist (für Graphen mit $n$~Knoten) ein $\O(n / \log n)$-Approximationsalgorithmus.
\end{satz}

\begin{beweisskizze}
  Sei $k$ die optimale Zahl an benötigten Farben. \\
  Sei $m_i$ ($i \geq 0$) die Anzahl der Knoten in~$H$ am Beginn der $i$-ten Iteration der inneren Schleife.
  Dann gibt es ein IS der Größe $\geq m_i/k$ in~$H$ und folglich ist in~$H$ der Minimalgrad $\leq m_i - m_i/k$. \\
  Somit ist $m_{i+1} \geq m_i/k - 1$.
  Durch Induktion folgt $m_i \geq m_0/k^i - 2$. \\
  Also gilt dann $\abs{I} = \min \Set{i}{m_i = 0} \geq \log(m_0/2) / \log(k)$. \\
  Daraus kann man eine Schranke für die benötigten Iterationen der äußeren Schleife, was der Anzahl Farben entspricht, herleiten.
\end{beweisskizze}

% aus §3.6. Minimum Vertex Coloring:
\begin{bem}
  Der naive Greedy-Algorithmus für MVC, der die Knoten absteigend nach Grad sortiert und dann in der Reihenfolge in der jeweils kleinsten verfügbaren Farbe färbt, hat ein Worst-Case-Approximationsverhältnis von $\Omega(n)$.
\end{bem}

% §5. Tree-Search Strategies
\subsection{\scriptSection{5} Idee: Baumsuche}

% §5.1. Erschöpfende Suche

% §5.2. Branch and Bound

\begin{strategie}[\emph{Branch and Bound} für Minimierungsprobleme]
  Organisiere den Suchraum als Baum, der zunächst nur eine Wurzel enthält, wobei mögliche Lösungen aus~$\Feasible(x)$ Blätter sind und "`partielle Lösungen"' (die zu einer möglichen Lösung erweitert werden können oder auch nicht) die Verzweigungen bilden.
  Es ist nicht praktikabel, den gesamten Baum zu durchsuchen.
  Darum mache folgendes:
  Beschrifte die Verzweigungen mit einer (kostengünstig) berechneten unteren Schranke für die Kosten einer Lösung, die Erweiterung der partiellen Lösung ist.
  Expandiere dann wiederholt eine Verzweigung im Baum, \dh{} berechne seine Kindknoten und beschrifte sie mit einer unteren Schranke der Kosten.
  Verzweigungen, deren untere Schranke mindestens so groß ist wie die Kosten einer bisher gefundenen zulässigen Lösung müssen nicht expandiert werden.
  Gibt es keine Verzweigung mehr, die expandiert werden muss, so ist die bisher gefundene zulässige Lösung mit minimalen Kosten eine optimale Lösung.
\end{strategie}

\begin{bem}
  Der Algorithmus kann auch früher abgebrochen werden, etwa wenn die unteren Schranken nur etwas kleiner sind als die Kosten der besten bisher gefundenen Lösung und wenn man mit einer approximativen Lösung zufrieden ist.
\end{bem}

\begin{bsp}
  Für das TSP auf $(V, E)$ sind partielle Lösungen Pfade $p = u_0 \cdots u_m$ beginnend bei einem Startknoten~$u_0$.
  Eine untere Kostenschranke für Touren, die Erweiterung des Pfades~$p$ sind, ist
  \[
    \arraycolsep=1pt
    d \coloneqq
    \begin{array}[t]{r l}
      & \min \Set{c(u_0, v)}{v \in V \setminus \{ u_0, \cdots, u_k \}} \\
      +& \min \Set{c(u_k, v)}{v \in V \setminus \{ u_0, \cdots, u_k \}} \\
      +& \text{Summe der Kosten der $n-k-1$ kostengünstigsten} \\
      & \text{Kanten zwischen Knoten in } \{ u_0, \cdots, u_k \}
    \end{array}
  \]
\end{bsp}

\begin{samepage}

\begin{bem}
  In der Praxis schaffen Branch-and-Bound-Algorithmen oft eine drastische Verkleinerung des Suchraums.
  Theoretisch haben sie jedoch für gew.\ dieselbe asympt. Laufzeit wie erschöpfende Suche.
\end{bem}

% §5.3. 3-Satisfiability
\subsection{\scriptSection{5.3} \Problem{3-SATisfiability} mit Baumsuche}

\begin{nota}
  Für eine Formel~$F$ (in KNF) und ein Literal~$l$ sei $F|_{l=i}$ ($i \!\in\! \{0,1\}$) die Formel, die man erhält, wenn man~$x$ durch $i$ (bzw. $1 \!-\! i$) ersetzt, wobei $l \!=\! x$ (bzw. $l \!=\! \overline{x}$) für eine Var.~$x$ und vereinfacht.
\end{nota}

\begin{satz}
  Eine Instanz $F$ von 3-SAT kann in Zeit $\O(\abs{F} \cdot \alpha_0^n)$ entschieden werden, wobei $\alpha_0 \approx 1.84$ und $\abs{F} = \#\text{Literale in~$F$}$.
\end{satz}

\end{samepage}

\begin{algorithmic}
  \Function{Decide}{$F$}
    \If{\text{$F$ hat keine Clauses}}
      \Return true
    \EndIf
    \State wähle eine Clause $l_1 \vee \cdots \vee l_k$ in $F$ (mit $k \in \{ 0, 1, 2, 3 \}$)
    \For{$i := 1, \ldots, k$}
      \If{\Call{Decide}{$F|_{l_1=0,\ldots,l_{i-1}=0,l_i=1}$}}
        \Return true
      \EndIf
    \EndFor
    \State \Return false
  \EndFunction
\end{algorithmic}

\begin{beweisskizze}
  Sei $f(n)$ die maximale Anzahl an Blättern im Rekursionsbaum für eine Formel mit $n$~Variablen. \\
  Dann kann man $f(n) \leq \alpha^n$ mit allen $\alpha > 1$ zeigen, für die gilt:
  \[
    \alpha^{n-1} + \alpha^{n-2} + \alpha^{n-3} \leq \alpha^n \iff
    \alpha^{-1} + \alpha^{-2} + \alpha^{-3} \leq 1
  \]
\end{beweisskizze}

% ÜA 5.1
\begin{lem}
  Sei $F$ eine Formel in 3-KNF und $F' = F|_{l_1=a_1, \ldots, l_k=a_k}$ mit Literalen $l_1, \ldots, l_k$ und $a_1, \ldots, a_k \in \{ 0, 1 \}$.
  Falls $F'$ keine Clause der Länge $< 3$ hat, so gilt: $F$ ist erfüllbar $\iff$ $F'$ ist erfüllbar
\end{lem}

% ÜA 5.1
\begin{satz}
  Eine Instanz $F$ von 3-SAT kann in Zeit $\O(\size{F} \cdot \beta^n)$ entschieden werden, wobei $\beta \approx 1,73$ die Wurzel von $x^5 - x^3 - 2 x^2  - 2 x - 1 = 0$ ist.
\end{satz}

% §5.4. Minimum Vertex Cover
\subsection{\scriptSection{5.4} \Problem{Minimum Vertex Cover} mit Baumsuche}

% 5.2
\begin{satz}
  Instanzen von Minimum Vertex Cover mit $n$~Knoten und $m$~Kanten können in Zeit $\O(3^{n/2} \cdot m + n)$ gelöst werden.
\end{satz}

\begin{nota}
  $G - W$ ist der Graph~$G = (V, E)$ mit den Knoten in $W \subseteq V$ und den an~$W$ inzidenten Kanten gelöscht.
  %Für einen Graphen $G = (V, E)$ und Knoten $W \subseteq V$ sei $G - W$ der Graph $(V', \Set{\{u, w\} \in E}{u, w \in V'})$ mit $V' \coloneqq V \setminus W$, der durch Löschen von~$W$ entsteht.
\end{nota}

\begin{algorithmic}
  \Function{ComputeMVC}{$G = (V, E)$}
    \If{$G = \emptyset$} \Return $\emptyset$ \EndIf
    \If{$G$ hat isolierten Knoten $u$}
      \State \Return $\Call{ComputeMVC}{G - \{ u \}}$
    \EndIf
    \If{$G$ hat Knoten $u$ vom Grad~1 mit Nachbar $v$}
      \State \Return $\{ v \} \cup \Call{ComputeMVC}{G - \{ u, v \}}$
    \EndIf
    \If{$G$ hat Dreieck mit Eckknoten $u$, $v$, $w$}
      \State $C_{u,v} \coloneqq \{u, v\} \cup \Call{ComputeMVC}{G - \{ u, v \}}$
      \State $C_{u,w} \coloneqq \{u, w\} \cup \Call{ComputeMVC}{G - \{ u, w \}}$
      \State $C_{v,w} \coloneqq \{v, w\} \cup \Call{ComputeMVC}{G - \{ v, w \}}$
      \State \Return kleinste der Überdeckungen $C_{u,v}$, $C_{u,w}$ und $C_{v,w}$
    \EndIf
    \If{$G$ hat einfachen Pfad $u$ --- $v$ --- $w$ --- $z$}
      \State $C_{u,w} \coloneqq \{u, w\} \cup \Call{ComputeMVC}{G - \{ u, w \}}$
      \State $C_{v,w} \coloneqq \{v, w\} \cup \Call{ComputeMVC}{G - \{ v, w \}}$
      \State $C_{v,z} \coloneqq \{v, z\} \cup \Call{ComputeMVC}{G - \{ v, z \}}$
      \State \Return kleinste der Überdeckungen $C_{u,w}$, $C_{v,w}$ und $C_{v,z}$
    \EndIf
  \EndFunction
\end{algorithmic}

\begin{samepage}

\begin{bem}
  In der Umgebung jedes Knoten eines Graphen tritt einer der vier Fälle auf.
  Es kann daher in konstanter Zeit einer der vier Fälle ausgewählt werden.
  Auf Reihenfolge muss nicht geachtet werden!
\end{bem}

Wir sagen, ein Fall \textit{verzweigt gemäß} $A_1, \ldots, A_k$, falls er den Algorithmus rekursiv mit Argumenten $G - A_1$, \ldots, $G - A_k$ aufruft.
Die Multimenge $\{ \size{A_1}, \ldots, \size{A_k} \}$ heißt zugehörige \textit{Verzweigungs- multimenge}.
Für eine solche Multimenge $\{ a_1, \ldots, a_k \}$ setzen wir
\[ \alpha(a_1, \ldots, a_k) \coloneqq \text{das eindeutige $x \geq 1$ mit } x^{-a_1} + \ldots + x^{-a_k} = 1. \]

\end{samepage}

Schaffen wir es, einen Algorithmus mit $m$~Fällen mit Verzweigungs- multimengen $\mathcal{A}_1, \ldots, \mathcal{A}_m$ anzugeben (sodass in konstanter Zeit entschieden werden kann, welcher Fall vorliegt), so läuft der Algorithmus in Zeit $\O(\alpha_0^n \cdot m + n)$, wobei $\max \, \Set{\alpha(\mathcal{A}_i)}{i = 1, \ldots, m}$

% 5.3
\begin{satz}
  Instanzen von Minimum Vertex Cover mit $n$~Knoten und $m$~Kanten können in Zeit $\O(\alpha_0^n \cdot m + n)$ gelöst werden, wobei $\alpha_0 \approx 1,325$ die Wurzel von $x^3 - x - 1$ ist.
\end{satz}

\begin{beweisidee}
  Richtig krasse Fallunterscheidung
\end{beweisidee}

% §6. Dynamic Programming

% §6.1. Maximum Integer Knapsack
\subsection{\scriptSection{6.1} \Problem{Maximum Integer Knapsack} mit dyn. Progr.}

% 6.1
\begin{satz}
  Sei $P = (v_1, \ldots, v_n, w_1, \ldots, w_n)$ eine Instanz von Maximum Integer Knapsack.
  Setze $V \coloneqq v_1 + \ldots + v_n$.
  Dann kann $P$ in Zeit $\O(n V)$ gelöst werden.
\end{satz}

\begin{alg}
  Löse mit dynamischer Programmierung die Unterprobleme $(P_{j,v})_{1 \leq j \leq n, 1 \leq v \leq V}$ mit
  \[
    P_{j,v} \coloneqq
      \begin{array}[t]{l}
        \text{finde $S \subseteq \{ 1, \ldots, j \}$ mit ${\sum}_{i \in S} v_i = v$ und} \\
        \text{${\sum}_{i \in S} w_i$ minimal unter allen solchen Teilmengen!}
      \end{array}
  \]
  Die Lösung ergibt sich aus den Lösungen von $P_{n,1}, \ldots, P_{n,V}$.
\end{alg}

\begin{bem}
  Die Laufzeit ist \emph{pseudopolynomiell}: Sie hängt polynomiell von den in der Eingabe enthaltenen Zahlen ab.
\end{bem}

% §6.2 Minimum Bin Packing
\subsection{\scriptSection{6.2} \Problem{Minimum Bin Packing} mit dyn. Progr.}

% 6.2
\begin{satz}
  Instanzen~$P$ von Minimum Bin Packing mit $n$~Objekten in $r$~versch. Größen können in Zeit~$\O(n^{2r+2})$ gelöst werden.
\end{satz}

\begin{alg}
  Seien $s_1, \ldots, s_r$ die verschiedenen Größen. \\
  Wir nennen einen Vektor $A = (a_1, \ldots, a_r) \in \N^r$ einen \textit{Packungstyp}, falls ${\sum}_{i=1}^r a_i s_i \leq 1$.
  Sei $\{ A_1, \ldots, A_t \}$ die Menge aller Packungstypen.
  Löse mit dyn. Programmierung die Unterprobleme
  \[
    P_{j,B} \coloneqq
      \begin{array}[t]{l}
        \text{finde $f : \{ 1, \ldots, j \} \to \N$ mit ${\sum}_{i=1}^j f(i) \cdot A_i = B$ und} \\
        \text{${\sum}_{i=1}^j f(i)$ ist minimal unter all solchen $f$.}
      \end{array}
  \]
  mit $1 \leq j \leq t$ und $B \in \N^r$ mit $B \leq P$.
  Das urspr.\ Problem ist $P_{t,P}$.
\end{alg}

% §7. Polynomial Time Approximation Schemes

\subsection{\scriptSection{7} Ein FPTAS für \Problem{Maximum Knapsack}}

% 7.1
\begin{satz}
  Es gibt einen Algorithmus, der für jedes $\epsilon > 0$ und jede Instanz $(v_1, \ldots, v_n, w_1, \ldots, w_n, W)$ von Maximum Knapsack in Zeit $\O(n^3 / \epsilon)$ eine $\epsilon$-approximative Lösung liefert.
\end{satz}

\begin{alg}
  (O.\,B.\,d.\,A.\ sei $w_i \leq W$ für alle~$i$.)
  \begin{enumerate}
    \item Setze $K \coloneqq \epsilon V / n^2$, wobei $V \coloneqq v_1 + \ldots + v_n$.
    \item Löse die Instanz $(v_1', \ldots, v_n', w_1, \ldots, w_n, W)$ mit $v_i' \coloneqq \floor{v_i/K}$ von Maximum \textit{Integer} Knapsack mit dem Algorithmus basierend auf dynamischer Programmierung.
    \item Die Lösung dieses geänderten Problems ist eine $\epsilon$-Approximation des ursprünglichen Problems.
  \end{enumerate}
\end{alg}

\begin{beweisskizze}
  Sei $S^*$ eine optimale Lösung.
  Dann gilt:
  \[
    \sum_{i \in S} v_i
    \geq K \sum_{i \in S} v_i'
    \geq K \sum_{i \in S^*} v_i'
    \geq K \sum_{i \in S^*} (\frac{v_i}{K} - 1)
    \geq \sum_{i \in S^*} v_i - K n
  \]
  \[
    \implies \quad
    \frac{{\sum}_{i \in S^*} v_i - {\sum}_{i \in S} v_i}{{\sum}_{i \in S^*} v_i}
    \leq \epsilon \frac{V}{n {\sum}_{i \in S^*} v_i}
    \leq \epsilon.
  \]
\end{beweisskizze}

\subsection{\scriptSection{7} Ein APTAS für \Problem{Minimum Bin Packing}}

% 7.3
\begin{lem}
  Es gibt einen Algorithmus, der für jede Instanz von \textit{Minimum Bin Packing} mit $n$~Objekten der Größe~$\geq \delta$ eine Packung der Objekte in $(1 + \delta) z^* + 1$ Behälter in Zeit $\O(n^{2/\delta^2 + 2})$ berechnet, wobei $z^*$ die optimale Zahl der Behälter ist.
\end{lem}

\begin{alg}
  Setze $k \coloneqq \ceil{\delta^2 n}$.
  Sortiere die Objekte absteigend nach Größe und bilde Gruppen mit je~$k$ Objekten.
  Benutze je einen eigenen Bin für jedes Objekt der ersten Gruppe.
  Ersetze in den anderen Gruppen jedes Objekt durch eine Kopie des kleinsten Objekts der vorhergehenden Gruppe.
  Finde mit dem Algorithmus aus §6.2 die opt. Anzahl $k'$ von Bins für die so durch "`Aufrunden"' vergrößerte Instanz.
  Dann gilt:
  \[
    z' + k \leq z^* + \delta^2 n + 1 \leq (1 + \delta) z^* + 1.
  \]
\end{alg}

% 7.4
\begin{satz}
  Es gibt einen Algorithmus, der für jede Instanz von \textit{Minimum Bin Packing} mit $n$~Objekten eine Packung der Objekte in $(1 + \delta) z^* + 1$ Behälter in Zeit $\O(n^{8/\delta^2 + 2})$ berechnet.
\end{satz}

\begin{alg}
  Setze $\delta \coloneqq \epsilon / 2$.
  Packe die großen ($\geq \delta$) Objekte wie im vorhergehenden Lemma.
  Fülle dann mit den kleinen ($< \delta$) auf und eröffne neue Bins, falls nötig.
\end{alg}

\begin{bem}
  Somit MBP $\in \APTAS$.
  Es gilt sogar MBP $\in \AFPTAS$.
\end{bem}

% §8. Parametrization
\subsection{\scriptSection{8} Idee: Parametrisierung}

\begin{vorgehen}
  Füge einen weiteren Parameter (zusätzlich zu den Größenparametern) für Probleminstanzen ein, suche nach einem Algorithmus, dessen Laufzeit wesentlich von diesem Parameter abhängt, sodass Instanzen, die einen kleinen Wert für den Parameter haben, in akzeptabler Zeit gelöst werden können.
\end{vorgehen}

% §8.1. Minimum Vertex Cover
\subsection{\scriptSection{8.1} Parametrisiertes \Problem{Minimum Vertex Cover}}

% 8.1
\begin{satz}
  Es gibt einen Algorithmus, der gegeben einen Graphen~$G$ mit $n$~Ecken und $m$~Kanten und ein $k \geq 0$ in Zeit $\O(n \cdot 1,325^{k} + m)$ ein Minimum Vertex Cover der Größe $\leq k$ berechnet, falls es ein solches gibt (ansonsten soll der Algorithmus "`keine Lösung"' zurückgeben).
\end{satz}

\begin{idee}
  Verwende den rekursiven Baumsuche-Algorithmus für Minimum-Vertex-Cover, aber breche die Rekursion ab, wenn das sich in Konstruktion befindende Cover Größe $> k$ erreicht.
  Außerdem optimiere rekursive Aufrufe dadurch, dass der Graph nicht für den Aufruf kopiert wird.
\end{idee}

% 8.3
\begin{satz}
  Es gibt einen Algorithmus, der gegeben einen Graphen~$G$ mit $n$~Ecken und $m$~Kanten und ein $k \geq 0$ in Zeit $\O(k^2 \cdot 1,325^{k} + n + m)$ ein MVC der Größe $\leq k$ berechnet, falls ein solches existiert.
\end{satz}

\begin{idee}
  Füge jeden Knoten mit Grad $\geq k$ zum Cover hinzu (da jedes Cover der Größe $\leq k$ diese enthalten muss).
  Wir können somit annehmen, dass~$G$ Maximalgrad $\leq k$ hat.
  Lösche alle isolierten Knoten aus~$G$.
  Es gilt: Falls $G$ nun mehr als $k^2$ Kanten oder mehr als $k^2 + k$ Ecken hat, so besitzt $G$ kein Vertex Cover der Größe $\leq k$ und wir können "`keine Lösung"' ausgeben.
  Ansonsten verwende den Algorithmus vom letzten Satz.
\end{idee}

\begin{bem}
  Wir haben damit die Probleminstanz auf einen kleineren \text{Kern} reduziert.
  Diese Technik heißt \textit{kernelization}.
\end{bem}

% §8.2. MaxSAT
\subsection{\scriptSection{8.2} Parametrisiertes \Problem{MaxSAT}}

% ausgelassen: Lemma 8.4 und 8.5

% 8.7
\begin{lem}
  Für eine Formel~$F$ in konj. NF, in der jede Variable, die in positiver wie negativer Form vorkommt, genau zwei mal vorkommt, kann in Zeit $\O(\size{F})$ eine Zuweisung von Variablen gefunden werden, die die Anzahl der erfüllten Clauses maximiert.
\end{lem}

\begin{alg}
  Wiederhole die folgenden Schritte:
  \begin{itemize}
    \item Setze alle nur pos. / neg.\ vorkommenden Variablen auf~1 / 0.
    \item Mache Unit-Propagation wo möglich.
    \item Falls beides nicht möglich, so setze willkürlich eine Variable auf~1.
  \end{itemize}
\end{alg}

\begin{beob}
  Sei $F$ eine Formel in KNF mit $m$~Clauses und $\alpha$ eine bel. Zuweisung.
  Dann erfüllt $\alpha$ oder $1 - \alpha$ mindestens $\ceil{m/2}$ Clauses.
\end{beob}

% 8.8
\begin{satz}
  Es gibt einen Algorithmus, der gegeben einer Formel in konj. NF und $k \in \N$ in Zeit $\O(k^2 \phi^k + \size{F})$, wobei $\phi = (1 + \sqrt{5}) / 2$, eine Zuweisung der Variablen in~$F$ berechnet, sodass $k$ Clauses erfüllt sind, oder entscheidet, dass es keine solche Zuweisung gibt.
\end{satz}

Folgender Alg.\ entscheidet bloß, ob es eine solche Zuweisung gibt (eine Variante davon berechnet auch eine Zuweisung):

\begin{algorithmic}
  \Function{DecideMaxSAT}{$F$, $k$}
    \State entferne überflüssige Literale aus allen Clauses
    \State $m \coloneqq $ Anzahl von Clauses in~$F$
    \If{$m < k$} \Return false \EndIf
    \If{$k \leq \ceil{m/2}$} \Return true \EndIf
    \State $F_S \coloneqq $ Konjunktion der \textit{short Clauses} mit $< k$ Literalen in~$F$
    \State $m_L \coloneqq $ Anzahl von \textit{long Clauses} mit $\geq k$ Literalen in~$F$
    \State \Return $\Call{Search}{F_S, k - m_L}$
  \EndFunction

  \Function{Search}{$F'$, $j$}
    \If{$j \leq 0$} \Return true \EndIf
    \If{$F'$ hat $< j$ Clauses} \Return false \EndIf
    \If{keine Variable tritt positiv und negativ in $F'$ auf}
      \State \Return true
    \EndIf
    \State Wähle unter den Variablen, die positiv und negativ auftreten,
    \State \quad eine Variable $x$, die am öftesten auftritt
    \State $m_0 \coloneqq $ Anzahl der negativen Vorkommen von~$x$
    \State $m_1 \coloneqq $ Anzahl der positiven Vorkommen von~$x$
    \If{$m_0 = m_1 = 1$}
      \State $k' \coloneqq $ max. Anzahl von erfüllb. Clauses in $F'$ (siehe Lem.)
      \State \Return $k' \geq j$
    \EndIf
    \If{$\Call{Search}{F'|_{x=0}, j - m_0}$}
      \Return true
    \EndIf
    \Return $\Call{Search}{F'|_{x=1}, j - m_1}$
  \EndFunction
\end{algorithmic}

\begin{beweisidee}
  Die Rekurrenzrelation für die Anzahl der Blätter im Rekursionsbaum von~$\Call{Search}{}$ ist $f(n) \leq f(n-1) + f(n-2)$.
\end{beweisidee}

Mit einer einfacheren $\Call{Search}{}$-Prozedur kann man schon zeigen:

% 8.6
\begin{satz}
  Es gibt einen Algorithmus, der gegeben einer Formel in konj. NF und $k \in \N$ in Zeit $\O(k^2 2^k + \size{F})$ eine Zuweisung der Variablen in~$F$ berechnet, sodass $k$ Clauses erfüllt sind, oder entscheidet, dass es keine solche Zuweisung gibt.
\end{satz}

% §8.3. Treewidth
\subsection{\scriptSection{8.3} Parametrisierung durch Baumweite}

% Übungsaufgabe 8.3
\begin{motivation}
  Auf Graphen, die Bäume sind, können folgende Probleme in polynomieller Zeit gelöst werden:
  \begin{itemize}
    \item Maximum Independent Set (bzw. Minimum Vertex Cover)
    \item Minimum Dominating Set
  \end{itemize}
  Dies ist auch möglich für Graphen mit beschränkter \textit{Baumweite}. \\
  Für MIS wird in §9.4 ein solcher Algorithmus vorgestellt.
\end{motivation}

% 8.9, 8.11
\begin{defn}
  \begin{itemize}
    \item
      Ein \emph{$k$-Baum} ist ein unger. Graph, der aus einer $k$-Clique durch wiederholtes Anwenden der folgenden Operation entsteht:
      Füge einen neuen Knoten mit Kanten zu den Knoten einer bestehenden $k$-Clique zum Graphen hinzu.
    \item Ein \emph{partieller $k$-Baum} ist ein Subgraph eines $k$-Baums.
  \end{itemize}
\end{defn}

\begin{bspe}
  \begin{minipage}[t]{0.8 \linewidth}
    Ein $1$-Baum ist ein gewöhnlicher Baum, \\
    ein $2$-Baum ein "`Baum von Dreiecken"'.
  \end{minipage}
\end{bspe}

\begin{lem}
  Maximum Independent Set kann auf $2$-Bäumen in linearer Zeit gelöst werden.
\end{lem}

% 8.10
\begin{lem}
  \begin{minipage}[t]{0.8 \linewidth}
    Ein $k$-Baum mit $n$ Knoten enthält genau \\
    $\tbinom{k}{2} + (n-k) k = k n - \tbinom{k+1}{2}$ Kanten.
  \end{minipage}
\end{lem}

% 8.12
\begin{defn}
  Eine \emph{Baumzerlegung} eines unger. Graphen~$G = (V, E)$ ist ein Paar $(T, B)$, wobei $T = (X, F)$ ein Baum ist und $B : X \to \Powerset(V)$ jedem Knoten $x \in X$ seinen \textit{Sack} $B(x) \subseteq V$ zuordnet, sodass
  \begin{itemize}
    \item $\cup_{x \in X} B(x) = V$
    \item $\fa{\{ u, v \} \in E} \ex{x \in X} \{ u, v \} \subseteq B(x)$
    \item Zus'hang: $\fa{x, y, z \in X} \text{$y$ liegt auf Pfad zw. $x$ und~$z$ in~$T$} \implies B(x) \cap B(z) \subseteq B(y)$.
  \end{itemize}
  Die \emph{Weite} einer Baumzerlegung~$(T, B)$ ist ${\max}_{x \in X} \size{B(x)} - 1$. \\
  Die \emph{Baumweite} $\treewidth(G)$ von~$G$ ist die kleinstmögliche Weite einer Baumzerlegung von~$G$.
\end{defn}

%\begin{bem}
%  Jeder Graph $G$ mit $n$~Knoten hat eine Baumzerlegung der Weite $n-1$.
%\end{bem}

% 8.13
\begin{defn}
  Eine Baumzerlegung $((X, F), B)$ heißt \emph{$k$-normal}, falls
  \begin{itemize}
    \item $\size{B(x)} = k + 1$ für alle $x \in X$ und
    \item $\size{B(x) \setminus B(y)} = 1$ für alle $\{ x, y \} \in F$.
  \end{itemize}
\end{defn}

% 8.14
\begin{lem}
  Jeder Graph der Weite~$\leq k$ mit $\geq k + 1$ Knoten hat eine $k$-normale Baumzerlegung.
\end{lem}

% Beweisidee: Bastle aus einer bel. Baumzerlegung eine k-normale Baumzerlegung durch "Auffüllen" der Säcke und Unterteilung der Kanten.

% ausgelassen: Lemma 8.15

% 8.16
\begin{lem}
  Sei $((X,F), B)$ eine Baumzerlegung von~$G = (V, E)$ und $C \subseteq V$ die Knoten einer Clique in~$G$.
  Dann $C \subseteq B(x)$ für ein $x \in X$.
\end{lem}

% 8.17
\begin{satz}
  Für jedes $k \in \N$ und jeden Graphen~$G$ sind äquivalent:
  \begin{center}
    $G$ ist ein $k$-partieller Graph $\iff$ $G$ hat Baumweite $\leq k$
  \end{center}
\end{satz}

% 8.18
\begin{lem}
  Jeder partielle $k$-Baum kann aus einem $k$-Baum durch Löschen von Kanten aus einem gewonnen werden.
\end{lem}

% 8.19
\begin{lem}
  Jeder unger. Graph der Baumweite $\leq k$ hat $\leq k n$ Kanten.
\end{lem}

% §8.4. Berechnung von Baumzerlegungen
% (ausgelassen in der Vorlesung)
\subsection{\scriptSection{8.4} Berechnung von Baumzerlegungen}

\begin{bem}
  Entscheiden, ob für ein Tupel $(G, k)$ mit einem Graphen~$G$ und $k \in \N$ der Graph $G$ Baumweite $\leq k$ besitzt, ist NP-vollständig.
\end{bem}

% 8.20
\begin{lem}[\textit{Bodlaender und Kloks}]
  Für alle Konstanten $l \in \N$ und $m, n \in \Z$ kann das folgende Problem in Zeit~$\O(m)$ gelöst werden:
  Gegeben eine Baumzerlegung mit $m$~Knoten mit Weite $\leq l$ eines Graphen~$G$ mit $n$~Knoten, berechne eine Baumzerlegung von~$G$ minimaler Weite mit $\leq n$ Knoten.
\end{lem}

\begin{bem}
  Der Alg.\ von B.\ und K.\ ist in der Praxis viel zu langsam.
\end{bem}

% 8.21
\begin{lem}
  Der Graph $G'$ entstehe aus~$G$ durch Zusammenziehen einer Kante.
  Dann gilt:
  \[
    \treewidth(G') \leq \treewidth(G)
    \quad \text{und} \quad
    \treewidth(G) \leq \treewidth(G') + 1.
  \]
\end{lem}

% 8.22
\begin{lem}
  Der Graph $G'$ entstehe aus~$G$ durch Zusammenziehen der Kanten eines Matchings.
  Dann gilt:
  \[
    \treewidth(G') \leq \treewidth(G)
    \quad \text{und} \quad
    \treewidth(G) \leq 2 \treewidth(G') + 1.
  \]
  Außerdem kann für bel. $k, m \in \N$ aus einer Baumzerlegung von~$G'$ der Weite~$k$ eine Baumzerlegung von~$G$ der Weite $\leq 2 k + 1$ in Zeit $\O(k m)$ konstruiert werden.
\end{lem}

\begin{defn}
  Ein Matching~$M$ in einem Graphen~$G$ heißt \emph{maximal}, falls es kein Matching $M'$ mit $M \subsetneq M'$ gibt.
\end{defn}

\begin{acht}[\Youtube{03PUwWef2Dg}, \Youtube{bOJC93XxoFc}]
  Jedes ``maximum matching'' ist ein ``maximal matching'', aber nicht andersherum.
\end{acht}

\begin{bem}[\Youtube{jtgBCGVux-8}]
  Maximale Matchings können gierig in linearer Zeit berechnet werden.
\end{bem}

% 8.24
\begin{satz}[\emph{Bodlaender}]
  Sei $k \in \N_0$ konstant.
  Für jeden Graphen~$G$ der Baumweite $\leq k$ mit $n$~Knoten kann eine Baumzerl. minimaler Weite mit $\leq n$ Knoten in Zeit und Platz $\O(n)$ berechnet werden.
\end{satz}

\begin{algorithmic}
  \Function{TreeDecompose}{$G = (V, E)$, $k$}
    \If{$V = \emptyset$} \Return $(T, B)$ wobei $T = (\{ t \}, \emptyset)$ und $B : t \mapsto \emptyset$ \EndIf
    \State $M \coloneqq $ ein maximales Matching $M$ in~$G$
    \State $G' = (U, E') \coloneqq G$ mit den Kanten in $M$ zusammengezogen,
    \IndentState $\phi : V \to U$ die knotenidentifizierende surj. Abbildung
    \State $W \coloneqq \Set{u \in U}{\size{\phi^{-1}(u)} = 2}$
    \State $L = (U, E_L) \coloneqq G'$ mit genau so vielen Kanten bel. entfernt,
    \IndentState dass jeder Knoten in $U \setminus W$ Grad $\leq k + 1$ hat
    \State $G'' \coloneqq (U, E'')$ mit $E'' \coloneqq E' \cup \Set{\{ u, v \}}{u, v \in W, \size{N_{u,v}} \geq k+1}$
    \IndentState wobei $N_{u,v} \coloneqq \Neighbors_L(u) \cap \Neighbors_L(v) \cap (U \setminus W)$
    \State $A \coloneqq \Set{u \in U \setminus W}{\text{Nachbarn von~$u$ in~$G''$ formen Clique in~$G''$}}$
    %\State $G''' \coloneqq (U \setminus A, E''')$ mit $E''' \coloneqq \Set{\{ u, v \} \in E''}{u, v \in U \setminus A}$
    \State $G''' \coloneqq$ Subgraph von~$G''$ mit Knotenmenge $U \setminus A$
    \State $(T = (X, F), B) \coloneqq \Call{TreeDecompose}{G'''}$
    \For{$a \in A$}
      \State finde $x \in X$ mit $\Neighbors_{G''}(a) \subseteq B(x)$
      \State füge zu $T$ einen Blattknoten $l_a$ mit Vaterknoten $x$ hinzu
      \State setze $B(l_a) \coloneqq \{ a \} \cup \Neighbors_{G''}(a)$
    \EndFor
    \State definiere $B' : X \to \Powerset(V)$ durch $B'(x) \coloneqq \phi^{-1}(B(x))$
    \State \Return mit der Schrumpfprozedur von Bodlaender und Kloks
    \IndentState verkleinerte Baumzerlegung $(T, B')$
  \EndFunction
\end{algorithmic}

\begin{bem}
  Man zeigt: Der Graph $G'''$ hat $\leq (1-a) n$ Knoten, wobei $a = 1 / (k^2 + 2)$.
\end{bem}

% §9. Planarität

% §9.1. Planare Graphen
\subsection{\scriptSection{9.1} Grundwissen: Planarität}

% 9.1
\begin{defn}
  Eine \emph{einfache Kurve} in~$\R^n$ mit \textit{Endpunkten} $a, b \in \R^n$ ist eine stetige Abb. $\gamma : \cinterval{0}{1} \to \R^n$ mit $\gamma(0) = a$, $\gamma(1) = b$ und $\gamma(s) \neq \gamma(t)$ für alle $s, t \in \cinterval{0}{1}$ mit $0 < \abs{s - t} < 1$.
  Sie heißt \emph{offen}, falls $a \neq b$, und \emph{geschlossen}, falls $a = b$.
\end{defn}

% 9.2
\begin{defn}[\Youtube{wnYtITkWAYA}]
  Eine \emph{planare Einbettung} $\phi = ((p_v)_{v \in V}, (\gamma_e)_{e \in E})$ eines Graphen $(V, E)$ ist geg. durch einen Punkt $p_v \in \R^2$ für jeden Knoten $v \in V$ und eine einfache Kurve $\gamma_{\{ u, v \}}$ zwischn $p_u$ und~$p_v$ für jede Kante $\{ u, v \} \in E$, sodass für alle $e \neq e' \in E$ gilt:
  \[
    \im \gamma_e \cap \gamma_{e'} = \{ \gamma_e(0), \gamma_e(1) \} \cap \{ \gamma_{e'}(0), \gamma_{e'}(1) \}.
  \]
  Ein Graph heißt \emph{planar}, falls er eine planare Einbettung besitzt.
\end{defn}

\begin{nota}
  $\phi(G) \coloneqq \Set{p_v}{v \in V} \cup {\bigcup}_{e \in E} \im \gamma_e \subseteq \R^2$
\end{nota}

\begin{bem}
  Man kann zeigen (\textit{Satz von Fáry}): Ist ein Graph $(V, E)$ mit $n$ Knoten planar, so gibt es eine planare Einbettung mit
  \begin{itemize}
    \item $p_v \in \{1, \ldots, n\}^2$ für alle $v \in V$ und
    \item $p_{\{u, v\}}(t) = (1-t) p_u + t p_v$ für alle $\{u, v\} \in E$.
  \end{itemize}
\end{bem}

\begin{defn}
  Die \emph{Flächen} einer planaren Einbettung~$\phi$ sind die Zusammenhangskomponenten von $\R^2 \setminus \phi(G)$.
  Alle Flächen bis auf eine sind dabei beschränkt.
  Die beschränkten Flächen heißen \textit{innere} Flächen, die unbeschränkte \textit{äußere} Fläche.
\end{defn}

% 9.4
\begin{satz}[\emph{Euler-Formel}, \Youtube{5ywif1Zpeo4}]
  Sei $G$ ein Graph mit $n$ Knoten, $m$ Kanten und $c$ Zusammenhangskomponenten.
  Angenommen, eine planare Einbettung von~$G$ hat $f$ Flächen.
  Dann gilt
  \[ n - m + f = c + 1. \]
\end{satz}

% 9.5
\begin{defn}
  Der \emph{Rand} einer Fläche~$F$ in einer Einb.~$\phi$ von $G = (V, E)$ ist der Subgraph $G' = (V', E')$ von~$G$ mit $V' = \Set{v \in V}{p_v \in \boundary{F}}$ und $E' = \Set{e \in E}{\gamma_e \subseteq \boundary{F}}$, wobei $\boundary F \subset \R^2$ der topologische Rand ist.
  Die Ecken in~$V'$ bzw. die Kanten in~$E'$ heißen \emph{inzident} an~$F$.
\end{defn}

% 9.6
\begin{lem}[\Youtube{_d_6JvceAwE}]
  \begin{minipage}[t]{0.75 \linewidth}
    Jeder planare Graph mit $n \geq 3$ Ecken hat höchstens $3 n - 6$ Kanten.
  \end{minipage}
\end{lem}

% 9.7
\begin{kor}
  Jeder planare Graph hat einen Knoten vom Grad $\leq 5$.
\end{kor}

% 9.8
\begin{defn}
  Ein Graph heißt \emph{außenplanar}, falls er eine planare Einb. besitzt, bei der alle Knoten inzident zur äußeren Fläche sind.
\end{defn}

% 9.9
\begin{lem}
  \begin{minipage}[t]{0.8 \linewidth}
    Jeder außenplanare Graph mit $\geq 4$ Knoten hat zwei nicht benachbarte Knoten mit Grad jeweils $\leq 2$.
  \end{minipage}
\end{lem}

% 9.10
\begin{lem}
  \begin{minipage}[t]{0.72 \linewidth}
    Jeder außenplanare Graph mit $n \geq 2$ Knoten hat höchstens $2 n - 3$ Kanten.
  \end{minipage}
\end{lem}

% §9.2. Parameterized Dominating Set
\subsection{\scriptSection{9.2} Param. \Problem{Independent Set} für planare Graphen}

% 9.11
\begin{satz}
  Für einen planaren Graphen $G$ und ein $k \in \N$ kann eine unabh. Knotenmenge der Größe $\leq k$ in Zeit $\O(6^k \cdot n)$ berechnet werden (falls eine solche existiert).
\end{satz}

\begin{idee}
  Verwende rekursive Suche und die Tatsache, dass es in einem planaren Graphen einen Knoten mit Grad $\leq 5$ gibt.
\end{idee}

\subsection{\scriptSection{9.2} Param. \Problem{Dominating Set} für planare Graphen}

% 9.12
\begin{lem}
  Ein planarer Graph mit $n$ Knoten, von denen $n_{\leq 2}$ Grad $\leq 2$ besitzen, hat $< 3 n - n_{\leq 2}$ Kanten.
\end{lem}

% 9.13
\begin{lem}
  Sei $G = (V, E)$ ein planarer Graph mit $n$ Knoten und $S \subset V$ mit $\size{S} \leq n/28$.
  Angenommen, jeder Knoten $v \in \Neighbors_G(S) \setminus S$ hat $\geq 2$ Nachbarknoten, die nicht in $W \coloneqq S \cup \Neighbors_G(S)$ liegen.
  Dann gibt es einen Knoten $v \in V \setminus W$ mit $\deg(v) \leq 6$.
\end{lem}

% 9.14
\begin{satz}
  Für einen planaren Graph mit $n$ Ecken und $k \in \{ 0, \ldots, \floor{n / 28} \}$ kann eine dominierende Menge der Größe $\leq k$ in Zeit $\O(7^k \cdot n)$ berechnet werden, falls eine solche existiert.
\end{satz}

\begin{algorithmic}
  \Function{DominatingSet}{$G = (V, E)$, $S \subseteq V$, $k$}
    \If{$\size{S} > k$} \Return ``no solution'' \EndIf
    \State $W \coloneqq S \cup \Neighbors_G(S)$
    \State $G' \coloneqq (V, E')$ mit $E' \coloneqq E \setminus \Set{\{ u, v \}}{u, v \in W}$
    \State $G'' \coloneqq (V'', E' \cap \Powerset(V''))$ mit $V'' \coloneqq V \setminus \Set{v \in W}{\deg_{G'}(v) \leq 1}$
    \State finde $v \in V'' \setminus W$ mit $\deg_{G''}(v) \leq 6$
    \IndentState (möglich dank vorhergehendem Lemma)
    \State $N \coloneqq \{ v \} \cup \Neighbors_{G''}(v)$
    \For{$w \in N$}
      $S_w \coloneqq \Call{DominatingSet}{G, S \cup \{ w \}, k}$
    \EndFor
    \State $C \coloneqq \Set{S_w}{w \in N} \setminus \{ \text{``no solution''} \}$
    \If{$C = \emptyset$} \Return ``no solution'' \EndIf
    \State \Return ${\argmin}_{T \in C} \size{T}$
  \EndFunction
\end{algorithmic}

% ausgelassen: §9.3 Computing Planar Embeddings

% §9.4 Polynomial-Time Approximation Schemes
\subsection{\scriptSection{9.4} Baumzerlegungen von planaren Graphen}

% 9.31
\begin{defn}
  Sei eine geometrische Einbettung eines Graphen~$G$ gegeben.
  Führe folgenden Schritt wiederholt aus, bis der Graph leer ist:

  \hfill\begin{minipage}{0.95 \linewidth}
    Lösche alle Knoten, die inzident zur äußeren Fläche sind.
  \end{minipage}

  Der \textit{Außenplanaritätslevel} eines Knoten ist die Nummer der Iteration, in der er gelöscht worden ist. \\
  Der Graph~$G$ heißt \emph{$k$-außenplanar}, falls er eine Einbettung besitzt, bezüglich der jeder Knoten Außenplanaritätslevel $\leq k$ hat (\dh{} nach $\leq k$ Iterationen war der Graph leer).
\end{defn}

\begin{bem}
  1-Außenplanare Graphen = außenplanare Graphen
\end{bem}

% Übungsaufgabe 9.4
\begin{lem}
  Außenplanare Graphen haben Baumweite $\leq 2$.
\end{lem}

% 9.32 und 9.33
\begin{defn}
  Sei $T \!=\! (V, E_T)$ ein Spannwald eines unger. Gr. $G \!=\! (V, E)$.
  \begin{itemize}
    \item Der \emph{Fundamentalkreis} einer Kante $\{ u, v \} \in E \setminus E_T$ ist ein Kreis bestehend aus $\{ u, v \}$ und dem Pfad von~$u$ nach~$v$ in~$T$.
    \item Für $e \in E$ / $v \in V$ sei $\mu(e)$ $\nu(v)$ die Anzahl der Fundamentalkreise, die $e$ / $v$ enthalten.
    \item Setze $\mu(G, T) \coloneqq {\max}_{e \in E} \mu(e)$ und $\nu(G, T) \coloneqq {\max}_{v \in V} \nu(v)$.
  \end{itemize}
\end{defn}

% 9.34
\begin{lem}
  Sei ein ungerichteter Graph $G = (V, E)$ mit $n$~Knoten und ein Spannwald $T = (V, E_T)$ von~$G$ gegeben.
  Setze
  \[ k \coloneqq \max \{ \mu(G, T) + 1, \nu(G, T) \}. \]
  Dann kann man eine Baumzerlegung von~$G$ mit Baumweite $\leq k$ und $\leq 2n - 1$ Knoten in Zeit $\O(k n)$ berechnen.
\end{lem}

\begin{beweisskizze}
  Ersetze jeden Knoten durch einen Bag, der initial diesen Knoten enthält, und jede Spannwaldkante durch einen Bag, der initial die beiden Endpunkte enthält.
  Für jede Kante $\{ u, v \} \in E \setminus E_T$ füge $u$ (oder $v$) in jeden Bag zwischen dem zu~$u$ gehörenden und dem zu~$v$ gehörenden Bag ein.
\end{beweisskizze}

% 9.35
\begin{lem}
  Sei $G$ ein planarer Graph und $G'$ der aus~$G$ durch Entfernen der mit der Außenfläche inzidenten Knoten erhaltene Graph.
  Sei außerdem $T'$ ein Spannbaum in~$G'$.
  Dann existiert ein Spannbaum $T$ von~$G$, der $T'$ enthält, mit
  \[
    \mu(G, T) \leq \mu(G', T') + 2
    \quad \text{und} \quad
    \nu(G, T) \leq \mu(G', T') + d,
  \]
  wobei $d$ das Maximum über die Anzahl an inzidenten inneren Flächen für alle $v \in V$ ist.
\end{lem}

% 9.36
\begin{kor}
  \begin{itemize}
    \item Jeder außenplanare Graph~$G$ mit Maximalgrad $\leq 3$ hat einen Spannwald~$T$ mit $\mu(G, T) \leq 2$ und $\nu(G, T) \leq 2$.
    \item Jeder $k$-außenplanare Graph mit Maximalgrad $\leq 3$ hat einen Spannwald~$T$ mit $\mu(G, T) \leq 2 k$ und $\nu(G, T) \leq 3 k - 1$.
  \end{itemize}
\end{kor}

% 3.38
\begin{satz}
  Die Baumweite eines $k$-außenplanaren Graphen ist $\leq 3k - 1$.
\end{satz}

\begin{beweisidee}
  Folgt aus dem Korollar nach Ersetzen jedes Knoten vom Grad $d > 3$ durch $d - 2$ Knoten vom Grad~$3$, sodass $k$-Außenplanarität erhalten bleibt.
\end{beweisidee}

\begin{satz}
  %Seien $k, n \in \N$
  Gegeben sei ein zshgder, unger. Graph~$G$ mit $n$~Knoten sowie eine kombinatorische Einbettung von~$G$, die den Graphen als $k$-außenplanar darstellt.
  Dann können wir in Zeit~$\O(k n)$ eine Baum- zerlegung von~$G$ mit Weite $\leq 3 k - 1$ und $\O(n)$ Knoten berechnen.
\end{satz}

\subsection{\scriptSection{9.4} Ein PTAS für \Problem{MIS} auf planaren Graphen}

% 9.40
\begin{lem}
  Gegeben sei ein Graph~$G$ mit $n$ Knoten sowie eine Baumzerlegung von~$G$ der Weite~$k$ mit $m$~Knoten.
  Dann kann ein MIS in~$G$ in Zeit $\O(k 2^k n + k m)$ berechnet werden.
\end{lem}

\begin{beweisskizze}
  Berechne eine $k$-normale Baumzerlegung $(T, B)$.
  Wähle eine Wurzel in~$T$.
  Stelle durch Duplizieren von Knoten sicher, dass jeder Knoten in~$T$ höchstens zwei Kinder hat.
  Berechne dann von den Blättern zur Wurzel für jeden Knoten $x \in T$ und alle $S \subseteq B(x)$ ein MIS~$I$ mit $I \cap B(x) = S$ (falls ein solches existiert).
\end{beweisskizze}

% 9.41
\begin{satz}
  Geg. sei $k \in \N$ und eine kombin. Einbettung eines Graphen~$G$ mit $n$~Knoten.
  Dann kann man in Zeit $\O(k^2 2^{3k} n)$ eine unabh. Menge in~$G$ berechnen, die mind. $\tfrac{k}{k+1}$-mal so groß ist wie ein MIS.
\end{satz}

\begin{alg}[\textit{Baker's Technik}]
  Für $j = 0, \ldots, k$ sei $G_j$ der Graph, den man durch Löschen der Knoten mit Außenplanaritäts- level $\equiv j \enspace (\mathrm{mod } (k+1))$ erhält.
  Bemerke: Alle $G_j$ sind $k$-außenplanar.
  Mit dem vorh. Lemma können wir ein MIS $I_j$ in~$G_j$ für $j = 0, \ldots, k$ berechnen.
  Gib $G_\ell$ zurück, wobei $\size{G_\ell} = {\max}_{0 \leq j \leq k} \size{G_j}$.
\end{alg}

% §10. Linear Programming Methods
\subsection{\scriptSection{10.1} Technik: Redukt.\ auf Lin. Programmierung}

% §10.1. Lineare Programmierung

\begin{defn}
  Ein \emph{Lineares Programm} (LP) ist gegeben durch eine Matrix $A \in \R^{m \times n}$ und Vektoren $b \in \R^m$, $c \in \R^n$.
  Gesucht ist ein Vektor $x \in \R^n$, der $A x \leq b$ erfüllt und $c^T x$ maximiert.
\end{defn}

% 10.1
\begin{resultat}
  Jedes lineare Programm~$P$ (mit ganzzahligen Koeffizienten) kann in Zeit~$\O(\size{P})$ gelöst werden, wobei $\size{P}$ die Anzahl Bits in einer Repräsentation von~$P$ ist.
\end{resultat}

\begin{bem}
  In der Praxis lassen sich die meisten LPs effizient mit dem \textit{Simplex-Verfahren} lösen.
\end{bem}

\begin{defn}
  Ein \emph{Integer Linear Program} (ILP) ist gegeben durch eine Matrix $A \in \Z^{m \times n}$ und Vektoren $b \in \Z^m$, $c \in \Z^n$.
  Gesucht ist ein Vektor $x \in \Z^n$, der $A x \leq b$ erfüllt und $c^T x$ maximiert.
\end{defn}

% §10.2 Minimum Weighted Vertex Cover
\subsection{\scriptSection{10.2} \Problem{Minimum Weighted Vertex Cover} mit (I)LP}

% 10.2
\begin{satz}
  Es gibt einen Polynomialzeit-2-Approximationsalgorithmus für Minimum Weighted Vertex Cover.
\end{satz}

\begin{beweisskizze}
  Wir können das Problem in ein ILP mit Variablen $\{ x_v \in \Z \}_{v \in V}$ übersetzen:
  \[
    \begin{array}{r l l}
      \text{minimiere} & {\sum}_{v \in V} c(v) x_v \\
      \text{unter den NBn} & x_v + x_w \geq 1 & \quad \text{für alle Kanten } \{ v, w \} \in E \\
      & 0 \leq x_v \leq 1 & \quad \text{für alle $v \in V$}
    \end{array}
  \]
  Es ist aufwendig, dieses zu lösen.
  Es ist dagegen leicht, eine optimale Lsg $\{ \hat{x}_v \in \R \}_{v \in V}$ des durch obige Spezifikation geg. LP zu finden.
  Dann ist $C \coloneqq \Set{v \in V}{\hat{x}_v \geq 1/2}$ ein 2-optimales Vertex Cover.
\end{beweisskizze}

% §10.3. MaxSAT and Randomization
\subsection{\scriptSection{10.3} \Problem{MaxSAT} mit (I)LP und Randomisierung}

\begin{alg}[\emph{Randomized Rounding}] \mbox{} \\
  Eingabe: Formel in KNF mit Variablen~$V$ und Clauses $\mathcal{C}$, \\
  Ausgabe: Variablenbelegung $V \to \{ 0, 1 \}$
  \begin{itemize}
    \item Löse das LP mit Variablen $\Set{y_v}{v \in V} \cup \Set{x_C}{C \in \mathcal{C}}$
    \[
      \begin{array}{r l}
        \text{maximiere} & {\sum}_{C \in \mathcal{C}} x_C \\
        \text{unter den NBn}
          & x_C \leq {\sum}_{v \in V^{+}(C)} y_v + {\sum}_{v \in V^{-}(C)} (1 - y_v), \\
          & 0 \leq x_C \leq 1 \quad \text{für alle } C \in \mathcal{C}, \\
          & 0 \leq \makebox[0pt][l]{$y_v$}\phantom{x_C} \leq 1 \quad \text{für alle } v \in V,
      \end{array}
    \]
    wobei $V^{+}(C)$ die positiv und $V^{-}(C)$ die negativ auftretenden Variablen in einer Clause $C \in \mathcal{C}$ sind.
    (Eine Lsg des entspr\@. ILP wäre eine exakte Lösung von MaxSAT\@.
    Bemerke: ${\sum}_{C \in \mathcal{C}} \hat{x}_C \geq z^*$)
    \item
      Seien die Zufallsvariablen $\Set{Y_v \in \{ 0, 1\}}{v \in V}$ unabhängig mit $\P(Y_v = 1) = \hat{y}_v$ für alle $v \in V$.
      Bestimme eine Variablenbelegung durch Ziehen all dieser ZVn.
  \end{itemize}
\end{alg}

% ausgelassen: Lemma 10.3
% ausgelassen: Lemma 10.4

\begin{lem}
  Jede Clause $\mathcal{C}$ mit Länge $k$ der Formel ist damit mit Wahrscheinlichkeit $\geq (1 - (1 - 1/k)^k) \cdot \hat{x}_C$ erfüllt.
\end{lem}

\begin{alg}[\textit{Symmetric Algorithm}]
  Eingabe: Formel in KNF mit Variablen~$V$,
  Ausgabe: Variablenbelegung $V \to \{ 0, 1 \}$ \\[0.2em]
  Seien die Zufallsvariablen $\Set{Y_v \in \{ 0, 1\}}{v \in V}$ unabhängig mit $\P(Y_v = 1) = 1/2$ für alle $v \in V$.
  Bestimme eine Variablenbelegung durch Ziehen all dieser ZVn.
\end{alg}

\begin{bem}
  Jede Clause $\mathcal{C}$ mit Länge $k$ der Formel ist damit mit Wahrscheinlichkeit $1 - (1/2)^k$ erfüllt.
\end{bem}

% 10.5
\begin{satz}
  Es gibt einen randomisierten Polynomialzeit-Algorithmus, der für jede MaxSAT-Instanz eine Variablenbelegung liefert, sodass in Erwartung mindestens $3/4 \cdot z^*$ Clauses erfüllt sind, wobei $z^*$ die Anzahl maximal erfüllbarer Clauses ist.
\end{satz}

\begin{beweis}
  Verwende folgenden Algorithmus: \\[0.2em]
  1. Wirf eine faire Münze.
  2. Bei Kopf wende \textit{Randomized Rounding}, bei Zahl den \textit{Symmetric Algorithm} an.
\end{beweis}

% §10.4. Minimum Steiner Forest
\subsection{\scriptSection{10.4} \Problem{Minimum Steiner Forest} mit (I)LP}

% 10.7
\begin{satz}
  Es gibt einen Polynomialzeit-Approximationsalgorithmus für Minimum Steiner Forest mit Approximationsverhältnis 2.
\end{satz}

\begin{alg}
  \begin{itemize}
    \item Simuliere Feuer, die sich von jedem Knoten, der noch nicht über eine Feuerstrecke mit allen Gleichfarbigen verbunden sind, entlang der Kanten ausbreiten.
    Jedes Feuer erzeugt so einen Feuerbaum.
    Wenn zwei Feuer sich treffen, so verschmelzen die Feuerbäume zu einem Baum.
    Wenn in einem Feuerbaum jeder Knoten mit allen Knoten gleicher Farbe verbun- den ist, so wird das Feuer inaktiv und setzt sich nicht mehr fort.
    \item
      Entferne aus dem so generierten Feuerwald alle Kanten, die nicht benötigt werden, um Knoten gleicher Farbe zu verbinden.
      Gebe den Wald bestehend aus den verbleibenden Kanten aus.
  \end{itemize}
\end{alg}

\begin{beweisidee}
  Für $S \subseteq V$ sei $\delta(S) \coloneqq \Set{e \in E}{\size{e \cap S} = 1}$ und
  \[
     g(S) \coloneqq
     \begin{cases}
       1 & \text{falls $u \in S$ und $v \in V \setminus S$ mit $r(u) = r(v)$ existieren,} \\
       0 & \text{sonst}
     \end{cases}
  \]
  Man kann zeigen, dass das Problem äquivalent zu folgendem ILP ist:
  \[
    \begin{array}{r l l}
      \text{minimiere} & {\sum}_{e \in E} c(e) x_e \\
      \text{unter den NBn}
        & {\sum}_{e \in \delta(S)} x_e \geq g(S) & \text{für alle } S \subseteq V \\
        & 0 \leq x_e & \text{für alle } e \in E
    \end{array}
  \]
  (Dieses ILP ist aber exponentiell groß!)
  Wir betrachten das entspr. (\textit{primale}) LP und dessen \textit{duales LP} mit Variablen $\Set{y_S}{S \subseteq V}$:
  \[
    \begin{array}{r l l}
      \text{maximiere} & {\sum}_{S \subseteq V} g(S) y_S \\
      \text{unter den NBn}
        & {\sum}_{S : e \in \delta(S)} y_S \leq c(e) & \text{für alle } e \subseteq E \\
        & 0 \leq y_S & \text{für alle } S \subseteq V
    \end{array}
  \]
  Für jede zul. Lösung $\{x_e\}_{e \in E}$ des \textit{primalen} und jede zul. Lösung $\{y_S\}_{S \subseteq V}$ des dualen Problems gilt dann wegen \textit{schwacher Dualität}:
  \[ {\sum}_{S \subseteq V} g(S) y_S \leq {\sum}_{e \in E} c(e) x_e \]
  Insbesondere gilt dies für die zulässige Lösung $\{y_S\}_{S \subseteq V}$ mit
  \[
    y_S \coloneqq \text{Brenndauer des Feuers mit Knotenmenge $S$}
  \]
  des dualen Problems.
  Dann kann man zeigen:
  \[
    \begin{array}{r l}
      & \text{Gesamtkosten der vom obigen Alg. berechneten Lösung} \\
      \leq & 2 \cdot {\sum}_{S \subseteq V} g(S) y_S \\
      \leq & 2 \cdot \text{optimaler Wert des dualen LP} \\
      \leq & 2 \cdot \text{optimaler Wert des primalen LP \enspace (es gilt sogar "`$=$"')} \\
      \leq & 2 \cdot \text{optimaler Wert des primalen ILP} \\
      = & 2 \cdot \text{optimaler Wert des Minimum-Steiner-Forest-Problems}
    \end{array}
  \]
\end{beweisidee}

% §12. A linear Vertex-Cover Kernel
\subsection{\scriptSection{12} Ein linearer Kernel für \Problem{Min. Vertex Cover}}

% 12.1
\begin{resultat}[\emph{Egerváry-König}]
  Sei ein bipartiter Graph $G$ mit $n$ Knoten und $m$ Kanten und ein Matching $M$ maximaler Größe in~$G$ gegeben.
  Dann kann ein Minimum Vertex Cover~$C$ von~$G$ der Größe~$\size{M}$ in Zeit $\O(n+m)$ berechnet werden.
\end{resultat}

\begin{algorithmic}
  \State $C \coloneqq \emptyset$
  \State $\mathrm{Matched} \coloneqq \cup_{e \in M} e$
  \While{$V \neq \emptyset$}
    \If{$\exists \, v \in V \setminus \mathrm{Matched}$}
      \State $X \coloneqq \Set{x \in V}{\{ v, x \} \in E}$, \enspace $V \coloneqq V \setminus \{ v \}$
    \Else \enspace
      wähle $v \in V$, setze $X \coloneqq \{ v \}$
    \EndIf
    \While{$X \neq \emptyset$}
      \State $Y \coloneqq \Set{y \in V}{\ex{x \in X} \{ x, y \} \in M}$
      \State $V \coloneqq V \setminus (X \cup Y)$, \enspace $C \coloneqq C \cup X$
      \State $X \coloneqq \Set{x \in V}{\ex{y \in Y} \{ x, y \} \in E} \subseteq \mathrm{Matched}$
    \EndWhile
  \EndWhile
\end{algorithmic}

\begin{satz}
  Für jeden unger. Graph $G = (V_G, E_G)$ und $k \in \N$ kann in Zeit~$\O(n+m)$ ein unger. Graph $H = (V_H, E_H)$ mit $\size{V_H} \leq 2 k$ und ein $k' \in \{ 0, \ldots, k \}$ berechnet werden, sodass gilt:
  \[
    \text{$G$ hat ein VC der Größe $\leq k$} \iff
    \text{$H$ hat ein VC der Größe $\leq k'$}.
  \]
  Desweiteren können wir in Zeit~$\O(n)$ aus einem Vertex Cover von~$H$ der Größe $\leq k'$ ein Vertex Cover von~$G$ der Größe $\leq k$ konstruieren.
\end{satz}

\begin{alg}
  \begin{itemize}
    \item Setze $G' \coloneqq (V', E')$ mit $V' \coloneqq V_G \times \{ \KCircle, \KSquare \}$ und $E' \coloneqq \Set{\{ (u, \KCircle), (v, \KSquare) \}}{(u, v) \in V_G \times V_G, \, \{ u, v \} \in E_G}$
    \item Berechne ein MVC~$\mathcal{C}$ von $G'$ mit dem Satz von Egerváry-König; im Folgenden werden Knoten rot ausgefüllt dargestellt, falls sie in diesem MVC enthalten sind, andernfalls als schwarz ausgefüllt.
    \item Ersetze $\dashbox{\KCircleUnsel \enspace \KSquareSel} \rightsquigarrow \dashbox{\KCircleSel \enspace \KSquareUnsel}$ in~$\mathcal{C}$. (Danach ist $\mathcal{C}$ immer noch ein MVC.)
    \item
      $V_2 \coloneqq \Set{v \in V_G}{(v, \KCircle) \in \mathcal{C}, \, (v, \KSquare) \in \mathcal{C}}$
      $V_1 \coloneqq \Set{v \in V_G}{(v, \KCircle) \in \mathcal{C}, \, (v, \KSquare) \not\in \mathcal{C}}$
      %$V_0 \coloneqq \Set{v \in V_G}{(v, \KCircle) \not\in \mathcal{C}, \, (v, \KSquare) \not\in \mathcal{C}}$
    \item Setze $k' \coloneqq k - \size{V_2}$.
    \item Falls $k' < 0$ oder $\size{V_1} > 2 k'$, so gib $(\tikz[baseline=-0.5ex]{\draw [fill] (0,0) circle (0.5pt) -- (6pt,0) circle (0.5pt);}, 0)$ zurück, denn dann gibt es kein VC von $G$ der Größe $\leq k$.
    \item Ansonsten gib $(G|_{V_1}, k')$ zurück.
  \end{itemize}
\end{alg}

Die Korrektheit des Algorithmus folgt aus:
\begin{itemize}
  \item Es gibt ein MVC von $G$, das $V_2$ enthält. Dies sieht man wie folgt:
    \begin{itemize}
      \item Sei ein MVC~$\mathcal{D}$ von~$G$ gegeben. Wir markieren die darin enthaltenen Knoten durch hellblaue Kästchen, die anderen Knoten durch nicht ausgefüllte Kästchen.
      \item Die imaginäre Ersetzung
        \[
          \colorbox{blue!20}{\KCircleUnsel \enspace \KSquareUnsel} \rightsquigarrow \colorbox{blue!20}{\KCircleSel \enspace \KSquareUnsel}
          \quad \text{und} \quad
          \framebox{\KCircleSel \enspace \KSquareSel} \rightsquigarrow \framebox{\KCircleSel \enspace \KSquareUnsel}
        \]
        zeigt, dass $\size{\framebox{\KCircleSel \enspace \KSquareSel}} \leq \size{\colorbox{blue!20}{\KCircleUnsel \enspace \KSquareUnsel}}$.
      \item
        Ändere $\mathcal{D}$ wie folgt ab:
        \[
          \colorbox{blue!20}{\KCircleUnsel \enspace \KSquareUnsel} \rightsquigarrow \framebox{\KCircleUnsel \enspace \KSquareUnsel}
          \quad \text{und} \quad
          \framebox{\KCircleSel \enspace \KSquareSel} \rightsquigarrow \colorbox{blue!20}{\KCircleSel \enspace \KSquareSel}
        \]
        Die vorhergehende Gleichung zeigt, dass dann $\mathcal{C}$ immer noch minimal ist.
    \end{itemize}
  \item $\size{V_1} \leq 2 \cdot (\text{Größe eines MVC von $G|_{V_1}$})$.
\end{itemize}

\begin{bem}
  Das Tupel $(H, k')$ wird \textit{Kernel} von $(G, k)$ genannt. \\
  Dieser Kernel ist \textit{linear} wegen $\size{V_H} \leq 2 k$.
\end{bem}

Bester Kern (Hagerup, 2012): Es gibt eine Kernelisierung von Edge Dominating Set mit $\#\text{Knoten} \leq \max \{ \tfrac{1}{2} k^2 + \tfrac{7}{2} k, 6 k \}$.
%  Carbonnel/Herbrard: Diese ist eine $\infty$-loss-less kernelization
Offenes Problem: Gibt es Kernelization mit $\#\text{Knoten} = \O(k)$ oder $\O(k^2)$?

% §11. Limits to Approximability
\section{\scriptSection{11} Grenzen der Approximierbarkeit}

% aus §4.3. Relative Approximation
\begin{satz}[§4.3]
  Falls $\P \neq \NP$, so gilt Minimum TSP $\not\in \APX$.
\end{satz}

\begin{beweisidee}
  Wäre Minimum TSP $r$-approximierbar, so könnte man diesen Algorithmus verwenden, um das NP-Problem, ob ein Graph einen Hamiltonweg besitzt, zu entscheiden.
\end{beweisidee}

\begin{satz}[§7]
  Falls $\P \neq \NP$, so gilt Minimum Bin Packing $\not\in \PTAS$
\end{satz}

\begin{beweisidee}
  Wäre Bin Packing $\epsilon$-approximierbar mit $\epsilon < 1/3$, so wäre das NP-vollständige Problem, zu entscheiden ob gegebene Objekte in zwei Bins passen, in~$\P$.
\end{beweisidee}

% §11.1 Probabilistically Checkable Proofs

\begin{defn}[\emph{Probabilistically Checkable Proofs}]
  Sei $L$ eine Sprache und $r, q : \N_0 \to \N$ Funktionen.
  Ein \emph{Verifizierer} ist ein Programm, das testen soll, ob (angebliche) Beweise in Form von Binärworten der Aussage $x \in L$ für ein gegebenes Wort~$x$ korrekt sind.
  Der Verifizierer bekommt dazu das Wort~$x$ der Länge~$n$ sowie $\O(r(n))$ unabhängig und gleichmäßig verteilte Zufallsbits.
  Dann erzeugt der Verifizierer $\O(q(n))$ Positionen von Bits.
  Der Verifizierer bekommt dann die Bits an den von ihm verlangten Positionen in einem (potentiellen) Beweis~$B$ für die Aussage $x \in L$.
  Dann muss der Verifizierer entscheiden, ob er glaubt, ob $B$ ein richtiger Beweis ist.
\end{defn}

\begin{defn}
  Eine Sprache $L$ gehört zur Komplexitätsklasse $\Defn{\PCP(r(n), q(n))}$, falls ein Verifizierer für~$L$ existiert, der $\O(r(n))$ Zufallsbits bekommt und vom Beweis $\O(q(n))$ Bits liest, sodass gilt:
  \begin{itemize}
    \item Falls $x \in L$, so gibt es einen Beweis~$B$, sodass der Verifizierer~$B$ mit Wahrscheinlichkeit~1 (also immer, egal was die Zufallsbits sind) akzeptiert.
    \item Falls $x \not\in L$, so wird jeder angebliche Beweis nur mit Wahrscheinlichkeit $< 1/2$ akzeptiert.
  \end{itemize}
\end{defn}

\begin{resultat}[\emph{PCP-Theorem}]
  $\NP = \PCP(\log n, 1)$
\end{resultat}

% §11.2. Inapproximability of MaxSAT

\begin{satz}
  $\mathrm{MaxSAT} \not\in \PTAS$ falls $\P \neq \NP$
\end{satz}

\begin{beweisskizze}
  Sei $L$ eine NP-vollständige Sprache. \\
  Nach dem PCP-Theorem gibt es einen Verifizierer~$V$ für~$L$, der $r(n)$ Zufallsbits nimmt und $q$ Bits liest, wobei $r(n) = \O(\log n)$. \\
  Sei ein Wort $x$ gegeben.
  Erzeuge eine Formel~$F$ wie folgt: \\
  Für Zufallsbits $y \in \{ 0, 1 \}^{r(n)}$ und jede Kombination $(b_1, \ldots, b_q) \in \{ 0, 1 \}^q$ von Bits an den verlangten Positionen, die zusammen zur Ablehnung führen, generiere eine Klausel $l_1 \vee \ldots \vee l_q$ mit $l_i \coloneqq v_{y,i}$ falls $b_i = 0$ und $l_i \coloneqq \overline{v_{y,i}}$ sonst.
  Dann gilt:
  \begin{itemize}
    \item Ist $x \in L$, so ist $F$ erfüllbar.
    \item Ist $x \not\in L$, so gilt für jede mögliche Variablenbelegung: Für mehr als die Hälfte der möglichen Werte von~$y$ gibt es mindestens eine für~$y$ generierte Klausel, die nicht erfüllt ist. \\
    Somit sind immer $> 2^{r(n) - 1}$ der insgesamt $\leq 2^{r(n) + q}$, also ein Anteil von $> 2^{-q-1}$ nicht erfüllt.
  \end{itemize}
  Wäre $\mathrm{MaxSAT} \in \PTAS$, so könnte man durch Anwendung des PTAS mit $\epsilon \coloneqq 2^{-q-1}$ entscheiden, welcher Fall vorliegt.
\end{beweisskizze}

% ausgelassen: §11.3 Inapproximability of Maximum Clique

\end{document}