\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{bis zum 26. April 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\hfill SoSe 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Lineares Programmieren}{10 Punkte}


F\"ur welche Werte von $s$ und $t$ gilt f\"ur das lineare Programm 
\begin{align*}
\max x_1 + x_2&, \text{ wobei}\\
sx_1 + tx_2 &\leq 1\\
x_1, x_2 &\geq 0
\end{align*}

\begin{enumerate}
\item es gibt eine optimale L\"osung, 
\item es gibt keine zul\"assige L\"osung,
\item die Zielfunktion ist unbeschr\"ankt?
\end{enumerate}

\AUFGABE{Polynomialzeitreduktion}{10 Punkte}

Zeigen Sie, dass
\begin{enumerate}
\item \textsc{Rudrata-Pfad} $\leq_p$ \textsc{Rudrata-Kreis}.
Dabei ist \textsc{Rudrata-Kreis} das Problem, ob ein gegebener Graph einen
Kreis besitzt, auf dem jeder Knoten genau einmal vorkommt, und 
\textsc{Rudrata-Pfad}  ist das Problem, ob ein Pfad vorhanden ist,
in dem jeder Knoten genau einmal vorkommt (der Anfangs- und Endknoten
m\"ussen nicht verbunden sein).

\emph{Hinweis}: F\"ugen Sie zu einem Graphen $G$ einen weiteren 
Knoten hinzu, der mit allen urspr\"unglichen Knoten durch Kanten verbunden ist.

\item \textsc{Rudrata-Pfad} $\leq_p$ TGI,
wobei TGI (Teilgraphisomorphie) folgenderma\ss{}en definiert ist: 
Gegeben seien zwei gerichtete Graphen $G_1 = (V_1, E_1)$ und 
$G_2 = (V_2, E_2)$. Gibt es einen Teilgraphen 
$G'_2 = (V'_2, E'_2)$
mit $V'_2 \subseteq V_2$ und $E'_2 \subseteq E_2$, so dass 
$G_1$ und $G'_2$
isomorph sind?
\end{enumerate}


\newpage
\AUFGABE{Planare Graphen}{10 Punkte}

Lipton and Tarjan haben bewiesen, dass jeder 
planare Graph $G = (V, E)$ mit $n$ Knoten einen \emph{ausgeglichenen
Separator} der Gr\"o\ss{}e $O(\sqrt{n})$ besitzt.
Dabei handelt es sich um eine Knotenmenge $S \subseteq V$,
so dass jede Zusammenhangskomponente von $G \setminus S$ h\"ochstens
$2n/3$ Knoten hat.
Lipton und Tarjan haben auch gezeigt, dass sich ein ausgeglichener
Separator in $O(n)$ Zeit finden l\"asst.

Folgern Sie daraus, dass man eine gr\"o\ss{}te \emph{unabh\"angige Menge}
in $G$ in
$2^{O(\sqrt{n})}$ Zeit berechnen kann.
Eine unabh\"angige Menge ist eine Menge von Knoten, in der keine zwei
Knoten durch eine Kante verbunden sind.

\emph{Hinweis}: Verwenden Sie dynamisches Programmieren und das
Teile-und-Herrsche Prinzip.
\end{description}
\end{document}
