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

\newcommand{\ZETTELNUMMER}{13}
\newcommand{\ABGABEDATUM}{17. July 2017, in class.}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\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}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\tw}{tw}

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

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER.\@ Problem Set for 

\smallskip
\noindent
\large
\textbf{Advanced Algorithms II}\hfill Spring 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM


\noindent
This is the last problem set.

\vskip 0.5cm

\begin{description}

\AUFGABE{Chromatic number}{10 points}

Let $G = (V, E)$ be a graph, and let $c \in \N$.
A \emph{$c$-coloring} of $G$ is a function
$\chi: V \rightarrow \{1, \dots, c\}$ such
that $\chi(u) \neq \chi(v)$ for all
edges $uv$ of $G$. The \emph{chromatic number}
of $G$, $\chi(G)$, is the smallest $c \in \N$ 
such that there is a $c$-coloring of $G$.

\begin{enumerate}
  \item Show that there is a function $f: \N \rightarrow \N$ such
    that $\chi(G) \leq f(\tw(G))$.
  \item Suppose we are given a non-redundant tree-decomposition
    $T = (W, F)$ and  $\left(V_w\right)_{w \in W}$ for $G$ of
    width $\tw(G)$. Show that there is an algorithm to 
    compute a coloring of $G$ with $\chi(G)$ colors
    that runs in time $g(\tw(G))\poly(|V|)$, where 
    $g: \N \rightarrow \N$ is a fixed function.
\end{enumerate}

\AUFGABE{Tree-Width of the triangulated regular $n$-gon}{10 points}

Let $n \geq 3$. 
The \emph{regular $n$-gon} $Q_n$ is the plane graph with
vertices $\{v_0, \dots, v_{n-1}\}$ and edges
$\{v_iv_{i+1} \mid i = 0, \dots, n - 2 \} \cup \{v_{n-1} v_0\}$ 
such that $v_i = (\cos(i 2\pi/n), \sin (i 2\pi/n))$,
for $i = 0, \dots, n-1$.
A \emph{triangulation} $R_n$ of $Q_n$ is obtained
from $Q_n$ by adding a maximal set of edges $v_iv_j$,
$0 \leq i < j \leq n-1$,
to $Q_n$ without creating any crossings.
It is known that any triangulation $R_n$ of $Q_n$
has exactly $2n-3$ edges and $n-1$ faces,  
and that all inner faces of $R_n$
are triangles.

Let $R_n$ be a triangulation of $Q_n$. Show that
$\tw(R_n) = 2$, and give a polynomial-time
algorithm to obtain a non-redundant tree decomposition
of $R_n$ with width $2$.


\AUFGABE{Separated sets}{10 points}

Let $G = (V, E)$ be a graph with $n$ nodes and $m$ edges.
Let $Y, Z \subseteq V$ with $|Y| = |Z| = k$.
Give an algorithm that determines in $O(k m)$ time
whether there is a set $S \subseteq V$ with 
$|S| < k$ such that $G \setminus S$  contains no 
path between $Y \setminus S$  and $Z \setminus S$.
\end{description}
\end{document}
