\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[utf8]{inputenc}
\usepackage[margin=2.5cm]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{xcolor}
\usepackage{tikz}

\setlength{\parskip}{0.4em}
\setlength{\parindent}{0pt}
\emergencystretch=1.5em

\definecolor{shadecolor}{gray}{0.94}

% ---- graue Box fuer Pseudocode/Problem-Boxen (nur mit xcolor) ----
\makeatletter
\newsavebox{\shadedbox}
\newenvironment{shaded}%
  {\par\smallskip\noindent
   \begin{lrbox}{\shadedbox}%
   \begin{minipage}{\dimexpr\linewidth-2\fboxsep\relax}}%
  {\end{minipage}\end{lrbox}%
   \colorbox{shadecolor}{\usebox{\shadedbox}}\par\smallskip}
\makeatother

% ---- alphabetische Aufzaehlung a) b) c) ohne enumitem ----
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi)}

% ---- Makros ----
\newcommand{\problem}[1]{\textsc{#1}}
\newcommand{\redp}{\le_p}
\newcommand{\NP}{\textsf{NP}}
\newcommand{\true}{\textsf{wahr}}
\newcommand{\false}{\textsf{falsch}}
\tikzset{knoten/.style={circle,draw,thick,minimum size=6.5mm,inner sep=1pt}}

% ---- Aufgabenkopf: Nummer + Titel + Punkte, jede Aufgabe auf neuer Seite ----
\newcommand{\aufgabe}[2]{\clearpage
  \noindent{\large\textbf{Aufgabe #1}}\hfill\textbf{(#2)}\par\nobreak
  \noindent\rule{\linewidth}{0.4pt}\par\medskip}

\begin{document}

% ================= Kopf =================
\begin{center}
{\large\textbf{Christian-Albrechts-Universität zu Kiel}}\\[2pt]
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität\\
Prof.\ Dr.\ K.\ Jansen\\[10pt]
{\large\textbf{Probeklausur 2 -- Analyse von Algorithmen und Komplexität}}\\[3pt]
SS 2026
\end{center}

\medskip
\begin{center}
Name:\ \underline{\hspace{3.5cm}}\qquad Matrikel-Nr.:\ \underline{\hspace{3.5cm}}
\end{center}

\medskip
\noindent\textit{Hinweise:}
\begin{itemize}
  \item Bearbeiten Sie \textit{alle} Aufgaben.
  \item Sie haben 10 Minuten Einlesezeit. Danach haben Sie \textbf{120 Minuten} Zeit für die Klausurbearbeitung.
  \item Erlaubte Hilfsmittel: Ein doppelseitig handschriftlich beschriebenes Blatt Papier DIN A4, (bunte) Stifte (kein Rot, kein Grün, kein Bleistift).
  \item Die Klausur besteht aus \textbf{5 Aufgaben}, die alle \textbf{10 Punkte} wert sind.
  \item Zum Bestehen müssen mindestens \textbf{18 Punkte} erreicht werden.
  \item Aufgabe 5 gibt zusätzlich \textbf{10 Bonuspunkte}. Insgesamt können also \textbf{50 Punkte plus 10 Bonuspunkte} erreicht werden.
\end{itemize}

% ======================================================================
\aufgabe{1 \quad ANWENDUNG -- LPT}{5 + 2 + 3 Punkte}
Wir betrachten das Scheduling-Problem $P\,\|\,C_{\max}$: $n$ Jobs mit
Bearbeitungszeiten $p_1,\dots,p_n \in \mathbb{Q}_{>0}$ sollen auf $m$ identische
Maschinen verteilt werden, sodass der Makespan $C_{\max}$ (die maximale
Maschinenlast) minimal ist. Der Algorithmus \problem{LPT} sortiert die Jobs
zunächst \emph{absteigend} nach Bearbeitungszeit und legt sie dann in dieser
Reihenfolge nacheinander jeweils auf die aktuell am wenigsten belastete
Maschine (\problem{ListScheduling}); bei Gleichstand wird die Maschine mit dem
kleinsten Index gewählt.

\begin{enumerate}
\item Wenden Sie \problem{LPT} auf die folgende Instanz mit $m = 3$ Maschinen an.
Geben Sie die Sortierung, die Platzierungen mit dem jeweiligen Lastvektor
$(M_1, M_2, M_3)$, den resultierenden Schedule (grafisch oder als
Belegungsliste) sowie den Makespan an.
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|}\hline
Job $j$ & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline
Bearbeitungszeit $p_j$ & 5 & 5 & 4 & 4 & 3 & 3 & 3\\\hline
\end{tabular}
\end{center}

\item Welche (multiplikative) approximative Güte hat der Algorithmus
\problem{LPT} in Abhängigkeit von der Maschinenzahl $m$?

\item Geben Sie eine Instanz mit $m = 2$ Maschinen an, bei der einfaches
\problem{ListScheduling} (ohne Vorsortierung, in der angegebenen
Job-Reihenfolge) die Güte $2 - \tfrac1m$ erreicht. Geben Sie sowohl den von
\problem{ListScheduling} erzeugten Makespan als auch den optimalen Makespan an.
\end{enumerate}

% ======================================================================
\aufgabe{2 \quad VORLESUNGSBEWEIS -- TRANSITIVITÄT}{10 Punkte}
Beweisen Sie den folgenden aus der Vorlesung bekannten Satz.

Seien $L_1, L_2, L_3$ Entscheidungsprobleme. Aus $L_1 \redp L_2$ und
$L_2 \redp L_3$ folgt $L_1 \redp L_3$.

Gehen Sie in Ihrem Beweis insbesondere auf die Konstruktion der Reduktion, die
Korrektheit (beide Richtungen der Äquivalenz) und die polynomielle Laufzeit
ein.

% ======================================================================
\aufgabe{3 \quad NP-VOLLSTÄNDIGKEIT}{10 Punkte}
Wir betrachten die folgende Variante von \problem{SubsetSum}.

\textbf{Problem: SubsetSum-ohne-Dreierpotenzen}\\
\textbf{Eingabe:} Zahlen $c_1, \dots, c_n \in \mathbb{N}_{>0}$ und ein Zielwert
$K \in \mathbb{N}$, wobei keine der Größen $c_i$ eine Dreierpotenz ist, d.h.\
$c_i \notin \{3^t \mid t \in \mathbb{N}_0\} = \{1, 3, 9, 27, \dots\}$ für alle
$i \in [n]$.\\
\textbf{Entscheide:} Existiert eine Teilmenge $S \subseteq \{1, \dots, n\}$ mit
$\sum_{i \in S} c_i = K$?

Zeigen Sie, dass \problem{SubsetSum-ohne-Dreierpotenzen} NP-vollständig ist.
Sie dürfen verwenden, dass \problem{SubsetSum} (ohne Einschränkung an die
Itemgrößen) NP-vollständig ist.

% ======================================================================
\aufgabe{4 \quad ETH}{1 + 4 + 1 + 4 Punkte}
\textbf{Problem: $k$-\problem{IndependentSet}}\\
\textbf{Eingabe:} Ein ungerichteter Graph $G = (V,E)$ und eine Zahl
$k \in \mathbb{N}_{\ge 1}$.\\
\textbf{Entscheide:} Existiert $S \subseteq V$ mit $|S| \ge k$, sodass
$\{v,u\} \notin E$ für alle $v, u \in S$ mit $v \ne u$?

Betrachten Sie folgende Reduktion von $k$-\problem{Clique} auf
$k$-\problem{IndependentSet}. Für eine Eingabe $(G = (V,E), k)$ bilde die
Instanz $(G' = (V, \bar E), k')$ mit
\[
\bar E = \{\{v,u\} \mid v, u \in V,\ v \ne u,\ \{v,u\} \notin E\}
\quad(\text{Komplementgraph}), \qquad k' = k.
\]

\begin{enumerate}
\item Geben Sie die Anzahl der Knoten $|V'|$ und die Anzahl der Kanten $|E'|$
für die resultierende $k$-\problem{IndependentSet}-Instanz in Abhängigkeit von
der originalen $k$-\problem{Clique}-Instanz an.
\item Beweisen Sie Laufzeit-Lower-Bounds für $k$-\problem{IndependentSet}
bezüglich der Knotenzahl $|V'|$ und der Kantenzahl $|E'|$ basierend auf der ETH
und der oben beschriebenen Reduktion.\\
\textit{Hinweis:} Unter der ETH ist $k$-\problem{Clique} weder in
$2^{o(|V|)} \cdot |I|^{O(1)}$ noch in $2^{o(\sqrt{|E|})} \cdot |I|^{O(1)}$
lösbar.
\end{enumerate}

\medskip
\textbf{Problem: \problem{SubsetSum}}\\
\textbf{Eingabe:} Zahlen $c_1, \dots, c_n$ und ein Zielwert $K$.\\
\textbf{Entscheide:} Existiert $S \subseteq \{1, \dots, n\}$ mit
$\sum_{j \in S} c_j = K$?

Betrachten Sie folgende Reduktion von \problem{3-ExactCover} (3-EC) auf
\problem{SubsetSum}. Bei \problem{3-ExactCover} sind eine Grundmenge $U$ und
eine Familie $F = \{S_1, \dots, S_{|F|}\}$ von Dreiermengen $S_j \subseteq U$
gegeben; gesucht ist eine exakte Überdeckung von $U$. Die Reduktion erzeugt
\emph{pro Menge $S_j \in F$ ein Item} $c_j$, kodiert als Zahl zur Basis
$(n+1)$, wobei $n = $ Anzahl der Items $= |F|$ ist (Ziffer $1$ an den drei
Stellen der Elemente von $S_j$). Der Zielwert $K$ ist die Zahl mit Ziffer $1$
an allen $|U|$ Stellen.

\begin{enumerate}\setcounter{enumi}{2}
\item Geben Sie die Itemzahl $n$ der resultierenden \problem{SubsetSum}-Instanz
in Abhängigkeit von der originalen \problem{3-ExactCover}-Instanz an.
\item Beweisen Sie einen Laufzeit-Lower-Bound für \problem{SubsetSum} bezüglich
der Itemzahl $n$ basierend auf der ETH und der oben beschriebenen Reduktion.\\
\textit{Hinweis:} Unter der ETH ist \problem{3-ExactCover} weder in
$2^{o(\sqrt{|U|})} \cdot |I|^{O(1)}$ noch in
$2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$ lösbar.
\end{enumerate}

% ======================================================================
\aufgabe{5 \quad APPROXIMATIVE ALGORITHMEN -- 2ApproxVC}{2 + 5 + 3 + (10) Punkte}
Beim Problem \problem{VertexCover} ist ein ungerichteter Graph $G = (V,E)$
gegeben; gesucht ist eine möglichst kleine Knotenmenge $C \subseteq V$, die
jede Kante abdeckt, d.h.\ $u \in C$ oder $v \in C$ für jede Kante
$\{u,v\} \in E$. Wir betrachten den folgenden Approximationsalgorithmus, der
die Kanten in einer gegebenen Reihenfolge durchläuft.

\begin{shaded}
\ttfamily\small
\textbf{Algorithmus 2ApproxVC($G = (V,E)$)}\\
1\quad $C \leftarrow \emptyset$\\
2\quad \textbf{foreach} Kante $\{u,v\} \in E$ (in gegebener Reihenfolge) \textbf{do}\\
3\quad\quad \textbf{if} $u \notin C$ \textbf{and} $v \notin C$ \textbf{then}\\
4\quad\quad\quad $C \leftarrow C \cup \{u, v\}$\\
5\quad\quad \textbf{fi}\\
6\quad \textbf{od}\\
7\quad \textbf{return} $C$
\end{shaded}

\begin{enumerate}
\item Wenden Sie \problem{2ApproxVC} auf den folgenden Graphen $G$ an. Die
Kanten werden in dieser Reihenfolge durchlaufen:
\[
\{1,2\},\ \{1,3\},\ \{2,3\},\ \{3,4\},\ \{4,5\},\ \{4,6\},\ \{5,6\}.
\]
Geben Sie den Ablauf (welche Kanten führen zu einer Aufnahme?) sowie die Größe
$|C|$ der berechneten Überdeckung an.
\begin{center}
\begin{tikzpicture}
  \node[knoten] (1) at (-2.6, 1.2) {$1$};
  \node[knoten] (2) at (-2.6,-1.2) {$2$};
  \node[knoten] (3) at (-1.0, 0.0) {$3$};
  \node[knoten] (4) at ( 1.0, 0.0) {$4$};
  \node[knoten] (5) at ( 2.6, 1.2) {$5$};
  \node[knoten] (6) at ( 2.6,-1.2) {$6$};
  \draw (1) -- (2);
  \draw (1) -- (3);
  \draw (2) -- (3);
  \draw (3) -- (4);
  \draw (4) -- (5);
  \draw (4) -- (6);
  \draw (5) -- (6);
\end{tikzpicture}
\end{center}

\item Zeigen Sie, dass \problem{2ApproxVC} die (multiplikative) Güte $2$ hat,
also $|C| \le 2 \cdot |C^\ast|$ für ein minimales Vertex Cover $C^\ast$ gilt.

\item Betrachten Sie den Kreis $C_n$ auf $n$ Knoten für \emph{gerades} $n$. Wie
groß ist ein minimales Vertex Cover von $C_n$, und welche Kantenreihenfolge
führt zur schlechtesten Approximationsrate von \problem{2ApproxVC}? Geben Sie
diese Rate an.

\item \textbf{BONUS:} Geben Sie eine Instanzfamilie an, deren
Approximationsrate von \problem{2ApproxVC} (bei ungünstigster
Kantenreihenfolge) gegen $2$ konvergiert, und weisen Sie dies nach.
\end{enumerate}

\end{document}