\documentclass[12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman,provide=*]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[a4paper,margin=2.5cm]{geometry}

\title{Hausaufgabe 10}
\author{Marek Lenczewski \\ Matrikelnummer: 1025252}
\date{21.\ Juni 2026}

\begin{document}

\maketitle

\section*{Hausaufgabe 10.1}

\subsection*{Teil 1: FeedbackVertexSet ist in NP}

$FEEDBACKVERTEXSET \in NP$ wurde in Hausaufgabe 9.2 gezeigt. 

\subsection*{Teil 2: FeedbackVertexSet ist NP-schwer}

Zeige, dass $FEEDBACKVERTEXSET$ NP-schwer ist durch die Reduktion: \\
$VERTEXCOVER \le FEEDBACKVERTEXSET$. \\


\textbf{Konstruktion}: Sei $G$ und $k$ eine Instanz von $VERTEXCOVER$. \\
Wir konstruieren daraus ein $FEEDBACKVERTEXSET$ durch:
\begin{itemize}
  \item $V' = V$
  \item $E' = \{ (u,v), (v,u) \mid \{u,v\} \in E \}$
  \item $k' = k$
\end{itemize}

\textbf{Beweis VertexCover nach FeedbackVertexSet}:

\begin{itemize}
  \item Sei $VC$ ein VertexCover von $G$ mit $|VC| \le k$.
  \item Somit hat jede Kante aus $G$ einen Endpunkt in $VC$.
  \item Also hat $G \setminus VC$ keine Kanten mehr.
  \item Dann hat auch $G' \setminus VC$ keine Kanten und damit keine Kreise.
  \item Also ist $VC$ ein FeedbackVertexSet für $G'$ mit $|VC| \le k'$.
  \end{itemize}

\textbf{Beweis FeedbackVertexSet nach VertexCover}:

\begin{itemize}
  \item Sei $FVS$ ein FeedbackVertexSet von $G'$ mit $|FVS| \le k'$.
  \item Dann ist $G' \setminus FVS$ kreisfrei.
  \item Angenommen $FVS$ wäre kein VertexCover. 
  \item Dann gäbe es eine Kante $\{u, v\} \in E$ mit $u, v \notin FVS$.
  \item Somit wären $u, v$ noch in $G' \setminus FVS$ vorhanden.
  \item Die Kanten $(u, v)$ und $(v, u)$ würden einen Kreis erzeugen.
  \item Das wäre ein Widerspruch zu $G' \setminus FVS$ ist kreisfrei.
  \item Also ist $FVS$ ein VertexCover von $G$ mit $|FVS| \le k$.
\end{itemize}

\textbf{Laufzeit}: Nur die Kanten werden verdoppelt $O(|E|)$,
also bleibt die Transformation polynomiell. \\


Da $FEEDBACKVERTEXSET \in NP$ und NP-schwer ist, folgt dass
$FEEDBACKVERTEXSET$ NP-vollständig ist. \hfill $\square$

\newpage

\section*{Hausaufgabe 10.2}

\subsection*{Teil 1: $k$-CliqueUniversal ist in NP}

Eingabe: Graph $G = (V, E)$, Zahl $k$ und Zertifikat $C \subseteq V$. \\

Der Verifizierer arbeitet wie folgt:

\begin{itemize}
  \item Prüfe ob $|C| \ge k$, lehne ab falls $|C| < k$.
  \item Prüfe für jedes Paar $\{x, y\} \subseteq C$ ob $\{x, y\} \in E$.
  \item Lehne ab, falls für ein Paar $\{x, y\} \notin E$.
  \item Sonst akzeptiere.
\end{itemize}

Existiert eine Clique $C$ mit $|C| \ge k$, dann gibt es ein Zertifikat $C$
dafür. Dieses wird vom Verifizierer akzeptiert und sonst abgelehnt. \\

Prüfung der Größe und aller Paare läuft in $O(|V|^2)$, somit in poly. Zeit.
Somit ist das ein poly. Verifizierer.
Also gilt $k\text{-}CLIQUEUNIVERSAL \in NP$.

\subsection*{Teil 2: $k$-CliqueUniversal ist NP-schwer}

Zeige, dass $k\text{-}CLIQUEUNIVERSAL$ NP-schwer ist durch die Reduktion: \\
$CLIQUE \le k\text{-}CLIQUEUNIVERSAL$. \\
$CLIQUE$ ist bereits als NP-vollständig bekannt. \\

\textbf{Konstruktion}: Sei $G$ und $k$ eine Instanz von $CLIQUE$. \\
Wir konstruieren daraus ein $k\text{-}CLIQUEUNIVERSAL$ durch:
\begin{itemize}
  \item $V' = V \cup \{u\}$ mit einem neuen Knoten $u$
  \item $E' = E \cup \{ \{u, v\} \mid v \in V \}$
  \item $k' = k + 1$
\end{itemize}

\textbf{Beweis Clique nach $k$-CliqueUniversal}:

\begin{itemize}
  \item Sei $C$ eine Clique von $G$ mit $|C| \ge k$.
  \item Da $u$ mit allen Knoten verbunden ist, ist $u$ auch mit allen
        Knoten aus $C$ verbunden.
  \item Damit ist $C \cup \{u\}$ eine Clique in $G'$.
  \item Dann gilt auch $|C \cup \{u\}| \ge k + 1 = k'$.
\end{itemize}

\textbf{Beweis $k$-CliqueUniversal nach Clique}:

\begin{itemize}
  \item Sei $C'$ eine Clique von $G'$ mit $|C'| \ge k'$.
  \item Setze $C = C' \setminus \{u\}$, dann gilt $|C| \ge k' - 1 = k$.
  \item Alle Knoten in $C$ liegen in $V$ und alle Kanten zwischen ihnen
        liegen in $E$, da nur Kanten zu $u$ neu hinzugefügt wurden.
  \item Damit ist $C$ eine Clique in $G$ mit $|C| \ge k$.
\end{itemize}

\textbf{Laufzeit}: Es werden ein Knoten und $|V|$ Kanten hinzugefügt $O(|V|)$,
also bleibt die Transformation polynomiell. \\


Da $k\text{-}CLIQUEUNIVERSAL \in NP$ und NP-schwer ist, folgt dass
$k\text{-}CLIQUEUNIVERSAL$ NP-vollständig ist. \hfill $\square$

\end{document}