4-exponential-algorithms.tex

\section{Exakte Exponentialzeit Algorithmen}

\begin{takeaway}
    \item $\bigOstar$-Notation
    \item Branching-Algorithmen: 3-SAT, Max-IS
    \item Dynamische Programmierung: TSP/Held-Karp, Graph Coloring
    \item Measure-and-Conquer
\end{takeaway}

\paragraph{Motivation}
Entwerfe Algorithmen die zwar exponentiell, aber dennoch schneller als vollständige Suche sind.
Insbesondere in Zeit $c^n$ für $c < 2$ (z.B. $2^{\sqrt{n}} \approx 1.41^n$) anstelle von $2^n$.

\paragraph{$\bigOstar$-Notation}
Idee: so wie wir in $\bigO$-Notation konstanten Faktoren weglassen, lassen wir in $\bigOstar$-Notation
polynomielle Vorfaktoren weg (da der exponentielle Faktor dominiert).

Seien $f,g : \N \mapsto \R^+$. Dann gilt $f(n) \in \bigOstar(g(n))$, falls ein Polynom $p : \N \mapsto \R^+$
existiert, so dass $f(n) \in \bigO(p(n) \cdot g(n))$.


\subsection{Branching-Algorithmen}

\paragraph{Idee}
Instanz der Grösse $n$ aufteilen in konstant viele kleinere Teilinstanzen der Grösse $n-d$, für eine Konstante $d$.
Ähnlich divide-and-conquer.


\subsubsection{Beispiel: 3-SAT}

Annahme: O.B.d.A. hat jede Klausel Literale von paarweise verschiedenen Variablen und alle Klauseln sind
paarweise verschieden, dank polynomiellem preprocessing.
Dann gilt $|\Phi| \in \bigO(n^3)$.

\paragraph{Belegungen}
Sei $\Phi$ eine Formel in 3-KNF über Variablen $X$, sei $x \in X$, $\alpha \in \setzeroone$.
$\Phi[x=\alpha]$ beschreibt die Formel in 3-KNF, die aus $\Phi$ entsteht indem man den Wert $x=\alpha$ einsetzt
und vereinfacht.
Fälle der Vereinfachung:
1) Klausel erfüllt und fällt weg.
2) Klausel noch nicht erfüllt, belegtes Literal fällt weg.
3) Falls Klausel nach 2) leer, ist $\Phi$ unerfülltbar.

Eine (partielle) Belegung $\sigma : X \mapsto \setzeroone$ heisst \emph{autark}, falls für alle Klauseln $C_i$ gilt:
entweder $\sigma$ erfüllt $C_i$, oder $C_i$ enthält keine Variablen aus $\sigma$.
Auch gilt: $\Phi$ erfüllbar $\iff$ $\Phi[\sigma]$ erfüllbar.

\paragraph{Trivialer Ansatz}
Wähle eine Variable $x$, berechne $\Phi[x=0]$ und $\Phi[x=1]$,
merge ($\Phi$ satisfiable $\iff$ $\Phi[x=0] \text{ satisfiable } \vee \Phi[x=1]$ satisfiable).
Zeit: $T(n) = 2 \cdot T(n-1) + \bigO(n) \implies T(n) \in \bigOstar(2^n) \implies$ keine Verbesserung,
probiert nur alle Belegungen aus.

\paragraph{Branch-3SAT / Monien-Speckenmeyer Algorithmus}
\begin{enumerate}
    \item Falls $\Phi = \emptyset$ return JA
    \item Wähle Klausel $F \in  \Phi$ von minimaler Länge
    \item Falls $F = \emptyset$ return NEIN
    \item Falls $F = (l)$, rufe Branch-3SAT($\Phi[l=1]$) auf
    \item Falls $F = (l_1 \vee l_2)$, rufe Branch-3SAT($\Phi[l_1=1]$) und Branch-3SAT($\Phi[l_1=0, l_2=1]$) auf
    \item Falls $F = (l_1 \vee l_2 \vee l_3)$, rufe Branch-3SAT($\Phi[l_1=1]$) und
    Branch-3SAT($\Phi[l_1=0, l_2=1]$) und Branch-3SAT($\Phi[l_1=0, l_2=0, l_3=1]$) auf
    \item return JA falls einer der rekursiven Aufrufe JA returned, sonst NEIN
\end{enumerate}

\paragraph{Theorem}
Branch-3SAT löst 3-SAT in Zeit $\bigOstar (1.8393^n)$ für alle Formeln über $n$ boolesche Variablen.

\underline{Laufzeit:}
\begin{align*}
T(n) &\leq T(n-1) + T(n-2) + T(n-3) + \bigO(n) \\
T(0) &= T(1) = T(2) = \bigO(n)
\end{align*}
Nehme $T(n) = \alpha^n$ an, forme um nach $\alpha^3 - \alpha^2 - \alpha - 1 = 0$,
finde reale Nullstelle mit $\alpha \in [1,2)$.


\subsubsection{Beispiel: Max-IS}

\paragraph{Maximum Independent Set Problem Max-IS}
\footnote{Recall: maximal == nicht erweiterbar. maximum == grösstes mögliches.} \\
Eingabe: $G=(V,E)$ \\
Lösungen: $\M(G) = \{ S \subseteq \M \st \{ u,v \} \notin E \text{ for all } u,v \in S, u \neq v \}$ \\
Kosten: $cost(S, G) = |S|$ \\
Ziel: $\max$

\paragraph{Algorithmus: Branch-Max-IS}
\begin{enumerate}
    \item if $V = \emptyset$: return $\emptyset$
    \item let $v \leftarrow \min_{u \in V} \deg_G(u)$
    \item let $N[v] = \{ u_1, \dots, u_k \}$ be the \emph{closed} neighbourhood%
    \footnote{Oft nehmen wir o.B.d.A. an dass $u_1 := v$.} of $v$
    \item return the largest set from the family $\{ \{u_i\} \cup \text{Branch-Max-IS}(G-N[u_i]) \st i \in \{1,\dots,k\} \}$
\end{enumerate}

\paragraph{Theorem}
Branch-Max-IS löst Max-IS in Zeit $\bigOstar (3^{n/3})  \subseteq \bigOstar (1.4423^n)$.

\underline{Korrektheit:} Per Konstruktion (wegen Beobachtung dass $\forall v \in V$ mindestens ein $u \in N[v]$ in der optimalen, maximum Lösung enthalten sein muss).

\underline{Laufzeit:}
Ziel: beschränke Anzahl Knoten des Rekursionsbaumes. Es gilt:
$$ T(G) \leq 1 + T(G-N[v]) + \sum_{i=2}^k T(G-N[u_i]) $$
$$ T(n) = \max_{\substack{ G=(V,E) \\ |V|=n}} T(G) $$
%
Ausserdem gilt Monotonie $T(n) \leq T(n+1)$ und $T(0) = 1$. \\
Sei $\delta_{min}(G)$ der minimale Grad in $G$. Es gilt:
%
\begin{align*}
T(G) & \leq 1 + T(n - \delta_G(v) - 1) + \sum_{i=2}^k T(n - \delta_G(u_i) - 1) \\
     & \overset{(1)}{\leq} 1 + T(n - \delta_{min}(G) - 1) + \delta_{min}(G) \cdot T(n - \delta_{min}(G) - 1) \\
     & = 1 + (1 + \delta_{min}(G)) \cdot T(n - (\delta_{min}(G) + 1)) \\
     & \leq 1 + \max_{1 \leq s \leq n} s \cdot T(n - s) \\
T(n) & \overset{(2)}{\leq} 1 + \max_{1 \leq s \leq n} s \cdot T(n - s) \\
\end{align*}
wobei (1) aus der Monotonie folgt.
(2) können wir schreiben, da die rechte Seite nicht mehr von einem bestimmten Graphen $G$ abhängt,
sondern nur noch von der Grösse der Eingabe.

Auflösen dieser letzten Ungleichung siehe Buch Kapitel 5.2, Seite 109f.


\subsection{Dynamische Programmierung}

\paragraph{Travelling Salesman Problem TSP} \mbox{} \\
Eingabe: (O.B.d.A. vollständiger) Graph $G=(V,E)$, Kostenfunktion $c : E \mapsto \N$ \\
Ausgabe: Hamiltonkreis $H$ in $G$ \\
Kosten: $cost(H, G) = \sum_{e \in H} c(e) $ \\
Ziel: $\min$

Problem: $\bigO(n!) = \bigOstar (2^{n \log n})$ viele mögliche Lösungen

\paragraph{Dyn-Prog-TSP / Held-Karp Algorithmus}
{ % space for util command
\newcommand{\vtwon}{\{v_2, \dots, v_n\}}
Für alle $S \subseteq \vtwon$ und jeden Knoten $x \in S$ berechne $l(S, x)$ als die minimalen Kosten
eines Pfades der in $v_1$ startet, in $x \in S$ endet und genau alle Knoten aus $S$ je einmal besucht.

\begin{enumerate}
    \item Initialisierung: $ l(\{v_i\}, v_i) \leftarrow c(\{v_1, v_i\})$ für alle $i \in \{2, \dots n\}$
    \item Für alle $j \in \{2, \dots n-1\}$, für alle $S \subseteq \vtwon$ mit $|S|=j$,
    für alle $x \in S$ berechne:
    $$ l(S, x) \leftarrow \min_{y \in (S-\{x\})} \{ l(S-\{x\},y) + c(\{y,x\}) \} $$
    \item Finde Lösung: $$ l_{min} \leftarrow \min_{v_i \in \vtwon} \{ l(\vtwon,v_i) + c(\{v_i,v_1\}) \} $$
    Return $l_{min}$.
\end{enumerate}
}

\paragraph{Theorem}
Held-Karp löst das TSP in Zeit $\bigOstar (2^n)$.

\underline{Beweis:}
Korrektheit trivial.
Schritte 1 und 3 in $\bigO(n)$.
Schritt 2: $\bigO(2^n)$ viele Teilmengen $S$, für jede wählen wir $x,y$ $\implies \bigO(n^2 \cdot 2^n)$.

\paragraph{Graph Coloring Problem (Graphfärbung)}
Sei $G$ ein ungerichtet, ungewichteter Graph und $k \in \N$.
Eine \emph{k-Färbung (k-coloring)} von $G$ ist eine Funktion $c : V \mapsto \{1, \dots, k\}$ so dass
$$ \{x,y\} \in E \implies c(x) \neq c(y) $$
Die Menge $C_i := \{ x \in V \st c(x) = i \}$ heisst i-te \emph{color class} von $c$.
Die \emph{chromatische Zahl (chromatic number)} $\chi(G)$ von $G$ ist das kleinste $k$ so dass $G$ eine $k$-Färbung besitzt.

Eingabe: $G=(V,E)$ \\
Ausgabe: $\chi(G)$

Bruteforce: $\bigOstar(n^n)$ da $\chi(G) \leq n$

\paragraph{Algorithmus: Dyn-Prog-Coloring}
Beobachtungen:
1) Jeder Farbklasse ist ein independent set in $G$.
2) Wenn $C_i$ kein maximales IS ist, dann existiert ein $x \in V-C_i$ dass zu $i$ umgefärbt werden kann.

\begin{enumerate}
    \item Initialisierung: $\chi(\emptyset) \leftarrow 0$
    \item Für alle $i \in \{1, \dots, n\}$, für alle $X \subseteq V$ mit $|X| = i$ berechne:
    $$ \chi(X) \leftarrow 1 + \min \{ \chi(X-I) \st I \text{ ist ein maximales IS in } G[X] \} $$
    Return $\chi(G) \leftarrow \chi(V)$
\end{enumerate}

\paragraph{Theorem}
Dyn-Prog-Coloring löst das Graphfärbungsproblem in Zeit $\bigOstar(2.4423^n)$.

\underline{Beweis:}
Verwende Variante von Branch-Max-IS\footnote{Betrachtet geschlossene Nachbarschaft aller Knoten, nicht nur
die von minimalem Grad, und gibt alle maximalen IS zurück (nicht nur das grösste).} um in $\bigOstar(3^{i/3})$ alle maximalen IS der Grösse $i$ zu finden.
Insgesamt:
$$ \bigOstar \left(\sum_{i=1}^n \binom{n}{i} \cdot 3^{i/3} \textcolor{gray}{\cdot 1^{(n-i)/3}} \right)
= \bigOstar \left( \left(1+3^{1/3} \right)^n \right) \in \bigOstar \left(2.4423^n \right) $$
unter Anwendung des Binomischen Satzes.


\subsection{Measure-and-Conquer}

\paragraph{Idee}
Ähnlich zu Branching-Algorithmen: Teile das Problem in Teilinstanzen auf.
Bei der Analyse betrachte aber nicht eine Rekursionsgleichung in der Eingabegrösse, sondern analysiere
eine andere Grösse.
D.h. entwerfe keine neuen Algorithmen, sondern verbessere die Analyse.

\paragraph{Definition}
Es gibt zwei Arten von Regeln, die wir auf die Eingabe anwenden:
\begin{enumerate}
    \item \emph{(data) reduction rules}, welche eine Instanz zu einer äquivalenten, kleineren Instanz reduzieren.
    \item \emph{branching rules}, welche eine Instanz in mehrere kleinere Teilinstanzen aufteilen.
\end{enumerate}

Eine branching rule reduziert eine Instanz der Grösse $n$ in $l$ viele Teilinstanzen der Grössen $n-k_1, \dots, n-k_l$.
$(k_1, \dots, k_l) \in \mathbb{Q}^{+^l}$ heisst \emph{branching vector} der branching rule.

\paragraph{Lemma (branching factor)}
Sei $\A$ ein Algorithmus mit \underline{einer} branching rule mit branching vector $(k_1, \dots, k_l)$.
Nehme an, dass die Anwendung einer Regel (und das Testen ihrer Anwendbarkeit!) in Polynomzeit möglich ist.
Beobachte ausserdem, dass Datenreduktionsregeln nur polynomiell oft angewendet werden können.

Dann ist die Laufzeit von $\A$ auf eine Eingabe der Grösse $n$ in Zeit $\bigOstar(\alpha^n)$;
dabei ist $\alpha$ die eindeutige positive Nullstelle des Polynoms
$$ x^n - x^{n-k_1} - x^{n-k_2} - \dots - x^{n-k_l} $$

$\alpha$ heisst \emph{branching factor} der branching rule, auch notiert als $\alpha(k_1, \dots, k_l)$.

Falls $\A$ mehrere branching rules verwendet, schätze jede Regel einzeln ab und nehme den worst case als obere Schranke.

\paragraph{Beobachtung}
\begin{enumerate}[label=(\alph*)]
    \item $ \alpha(k_1, \dots, k_l) = \alpha(k_{i_1}, \dots, k_{i_l}) $ für jede Permutation $(i_1, \dots, i_l)$
    von $(1, \dots, l)$.
    \item $ \alpha(k_1, k_2, \dots, k_l) > \alpha(k_1', k_2, \dots, k_l)$ für jedes $k_1' > k_1$
    \item $ \alpha(k_1, k_2) > \alpha(k_1+s, k_2-s)$ für $0 \leq s \leq k_2 - k_1$
\end{enumerate}
Intuitiv: Der branching factor wird kleiner wenn ein Element des branching vectors grösser wird,
oder wenn der Vektor ``balancierter'' wird.
Ein kleinerer branching factor ist besser.

\paragraph{Algorithmus: Max-Degree-Branch-Max-IS}
Ähnlich Branch-Max-IS, aber branched auf Knoten von maximalen (anstatt minimalem) Grad.
{
\newcommand{\algo}{\textsc{Max-Degree-Branch-Max-IS}}
\begin{enumerate}
    \item If $\exists v \in V \cl \deg_G(v) \leq 1$: return $ 1+ \algo(G-N[v]) $
    \item If $\exists v \in V \cl \deg_G(v) \geq 3$: let $v$ be a vertex of maximum degree. return \\
    $ \max \{ 1 + \algo(G-N[v]), \algo(G-v) \} $
    \item If $\exists v \in V \cl \deg_G(v) = 2$: compute a max IS in polynomial time on the remaining trees+cycles
\end{enumerate}
}

\paragraph{Theorem}
Max-Degree-Branch-Max-IS löst Max-IS in Zeit $\bigOstar(1.3803^n)$

\underline{Beweis:}
Korrektheit: offensichtlich (Schritt 1: sichere Datenreduktionsregel). \\
Laufzeit: der branching vector in Schritt 2 ist $(1, 1+\deg_G(v))$ bzw. im worst case $(1,4)$ (siehe Beobachtung). \\
$\implies$ branching factor $\alpha(1,4) < 1.3803$.

\paragraph{Measure-and-Conquer Analyse}
Idee: Die branching-rule-Analyse betrachtet alle Knoten, aber ignoriert dass Knoten mit kleinem Grad ``nicht so schlimm''
sind für die Laufzeit.
Seien $n_{\leq 1}, n_2, n_{\geq 3}$ die Anzahl Knoten von entsprechendem Grad.
Definiere eine Gewichtsfunktion (arbiträr):
$$
w(v) := \begin{cases}
0 & \text{if} \deg_G(v) \leq 1 \\
\frac{1}{2} & \text{if} \deg_G(v) = 2 \\
1 & \text{if} \deg_G(v) \geq 3 \\
\end{cases}
$$

Das Gesamtgewicht des Graphen ist dann:
$$ w(G) = \sum_{v \in V} w(v) = n_{\leq 1} \cdot 0 + n_2 \cdot \frac{1}{2} + n_{\geq 3} \cdot 1
= \frac{1}{2} \cdot n_2 + n_{\geq 3} $$

In den neuen Teilinstanzen betrachte nun die Gewichts-Verringerung (anstatt der Knotenanzahl-Verringerung).
Sei $G_{in} = G-N[v]$ und $G_{out} = G-v$.
Seien $w_{in}, w_{out}$ die Werte, um die sich die Gewichte verringern:
$$ w(G_{in}) \leq w(G) - w_{in} \qquad w(G_{out}) \leq w(G) - w_{out} $$
Der branching vector ist also $(w_{in}, w_{out})$.

Da in beiden Fällen mindestens $v$ entfernt wird, wissen wir dass $w_{in}, w_{out} \geq 1$.

Jeder Knoten $u \in N(v)$ mit $\deg_G(u) = 2$ wird entweder entfernt ($G_{in}$) oder verliert seinen Nachbarn $v$ ($G_{out}$).
In beiden Fällen verringert sich das Gewicht um $\frac{1}{2}$, in der Summe also um 1.
\\
Jeder Knoten $u \in N(v)$ mit $\deg_G(u) \geq 3$ wird in $G_{in}$ entfernt, d.h. der Graph verliert Gewicht 1.
Über $G_{out}$ können wir in diesem Fall nichts sagen, das Gewicht von $u$ bleibt schlimmstenfalls gleich.

Zusammengefasst:
In beiden Fällen wird $v$ entfernt (wobei $w(v)=1$ sonst würden wir nicht auf $v$ branchen).
Ausserdem wird via die Nachbarschaft $N(v)$ über $G_{in}, G_{out}$ hinweg $d := \deg_G(v)$-mal
das Knotengewicht 1 entfernt. Also gilt in der Summe:
$$ w_{in} + w_{out} \geq 2 + d $$

Aus der vorherigen Beobachtung folgt, dass im schlimssten Fall $w_{in}, w_{out}$ unbalanciert sind, also der
branching vector $(1, 1 + d)$ ist.

Fallunterscheidung:
\begin{itemize}
    \item[$d=3$]
    Der Graph hat nur Knoten von Grad 2 oder 3.
    Damit wissen wir, dass sich sowohl in $G_{in}$ als auch in $G_{out}$ das Gewicht aller Nachbarn
    von $v$ um mindestens $\frac{1}{2}$ verringert:
    $$ w_{in}, w_{out} \geq 1 + 3 \cdot \frac{1}{2} = 2.5 $$
    $\implies$ $\alpha(2.5, 2.5) < 1.3196$.
    \item[$d \geq4 $]
    $\implies$ $\alpha(1, 5) < 1.3248$.
\end{itemize}
Wegen der Beobachtung wissen wir, dass $\alpha(1, 4) > \alpha(1, 5)$.
Diese Fallunterscheidung erlaubt es uns den Fall $d=3$ besser abzuschätzen als mit $\alpha(1, 4)$.
Da für grössere $d$ der branching factor $\alpha$ nur kleiner wird, können wir folgern:

\paragraph{Theorem}
Max-Degree-Branch-Max-IS löst Max-IS in Zeit $\bigOstar(1.3248^n)$.