\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {VertexCover},
  Referenz = 46115-2016-H.T1-A4,
  RelativerPfad = Examen/46115/2016/09/Thema-1/Aufgabe-4.tex,
  ZitatSchluessel = examen:46115:2016:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Polynomialzeitreduktion},
  EinzelpruefungsNr = 46115,
  Jahr = 2016,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 4,
}

\def\vc{\bProblemName{VERTEX COVER}}
\def\vcDrei{\bProblemName{VERTEX COVER 3}}

Betrachten Sie die beiden folgenden Probleme:
\index{Polynomialzeitreduktion}
\footcite{examen:46115:2016:09}
%%
%
%%

\bProblemBeschreibung
{\vc}
{Ein ungerichteter Graph $G = (V, E)$ und eine Zahl $k \in \{ 1, 2, 3,
\dots \}$}
{Gibt es eine Menge $C \subseteq V$ mit $|C| \leq k$, so dass für jede
Kante $(u, v)$ aus $E$ mindestens einer der Knoten $u$ und $v$ in $C$
ist?}

%%
%
%%

\bProblemBeschreibung
{\vcDrei}
{Ein ungerichteter Graph $G = (V, E)$ und eine Zahl $k \in \{ 3, 4, 5
\dots \}$.}
{Gibt es eine Menge $C \subseteq V$ mit $|C| \leq k$, so dass für jede
Kante $(u, v)$ aus $E$ mindestens einer der Knoten $u$ und $v$ in $C$
ist?}

Geben Sie eine polynomielle Reduktion von \texttt{\vc} auf
\texttt{\vcDrei} an und begründe anschließend, dass die Reduktion
korrekt ist.

\footcite[Seite 12, Aufgabe 13]{theo:ab:4}

\begin{bExkurs}[\vc]
\bProblemVertexCover
\end{bExkurs}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\begin{bAntwort}
\bPolynomiellReduzierbar{\vc}{\vcDrei}

\noindent
$f$ fügt vier neue Knoten hinzu, von denen jeweils ein Paar verbunden
ist. Außerdem erhöht $f$ $k$ um $2$.

\begin{description}
\item[Total:]

Jeder Graph kann durch $f$ so verändert werden.

\item[Korrektheit:]

Wenn \vc{} für $k$ in $G$ existiert, dann existiert auch \vc{} mit $k +
2$ Knoten in $G^\prime$, da für den eingefügten Teilgraphen ein \vc{}
mit $k = 2$ existiert.

\item[In Polynomialzeit berechenbar:]

Für die Adjazenzmatrix des Graphen müssen lediglich vier neue Spalten
und Zeilen eingefügt werden und $k + 2$ berechnet werden.
\end{description}

\end{bAntwort}

\end{document}