# Übung 10 Aufgabe 3 - Simon Stadlinger, Jost Götte
#### a)
Es ist zu zeigen, dass $TWOCLIQUESOVERLAPPING$ – im Folgenden $TCO$ abgekürzt – NP-vollständig ist. $TCO =\{(G,k,k')\mid G \text{ hat eine Clique der Größe }k \text{ und eine der Größe }k'\}$ Dabei dürfen sich die Cliquen überlappen, müssen es aber nicht.

Es gilt zweierlei zu zeigen:
1) TCO ist in NP
2) TCO ist NP-schwer

Zunächst wird 1) gezeigt.

Hierfür wird ein Algorithmus angegeben, der das Problem nichtdeterministisch polynomiell löst.

Zur Eingabe $(G,k,k')$ (der Graph wird als Adjazenzmatrix eingegeben) wählt der Algorithmus nichtdeterministisch zwei Mengen $U$ und $U'$ mit $k$ und $k'$ Knoten. Sollte eine der Mengen Duplikate enthalten so wird verworfen (also $false$ zurückgegeben). Ansonsten wird getestet, ob die Mengen $U$ und $U'$ Cliquen sind. Falls ja, wird akzeptiert (also $true$ zurückgegeben), sonst wieder verworfen.

Dieser Algorithmus läuft in Polynomialzeit, da nur $k+k' \leq 2n$ Knoten gewählt werden müssen, und weil das Testen auf Cliquen je Clique nur $\mathcal{O}(n^2)$ dauert (dank Adjazenzmatrixdarstellung); auch das Prufen der Duplikate ist schnell.

Falls es zwei Cliquen der geforderten Größe gibt, so werden diese offensichtlich fur eine nichtdetermistische Wahl gefunden. Ansonsten ist bei jeder Wahl von $U$ und $U'$
eine Bedingung, um zu akzeptieren verletzt, es wird also verworfen. Somit ist der Algorithmus korrekt und zeigt $TCO\in$NP.

Es bleibt 2) zu zeigen.

Wir reduzieren hierzu $CLIQUE$, von dem wir wissen, das es NP-vollständig ist, auf $TCO$ und somit gilt $TCO$ auch als NP-schwer wegen Transitivität. Es gilt also zu zeigen, dass
$$
CLIQUE \leq_P TCO
$$
Dazu gilt es eine Funktion $f$ zu finden, die deterministisch in polynomieller Zeit berechenbar ist, so dass gilt
$$
\forall G, k: (G,k, k') \in CLIQUE \Leftrightarrow f(G,k)\in TCO (2.1)
$$
Sei $f$ nun für alle $G,k$ folendermaßen defniniert:
$$
f(G,k) = (G,k,k)
$$
Es ist klar, dass $f$ in polynomieller Zeit berechenbar ist und deterministisch funktioniert, da nur ein neues Tupel mit einem kopierten $k$ ausgegeben werden muss.
Wir zeigen nun Aussage (2.1).
* Falls $(G,k)\in CLIQUE$ hat $G$ eine Clique der Größe $k$. Dann hat $G$ insbesondere zwei Cliquen der Größe $k$, die sich komplett überlappen, da es die selben sind. Ein Algorithmus kann nämlich einfach die selbe Clique zwei mal auswählen. Somit folgt $f(G,k) = (G,k,k) \in TCO$, wie gewünscht.
* Falls $(G,k)\notin Clique$ hat $G$ keine Clique der Größe $k$. Dann hat $G$ insbesondere keine zwei Cliquen der Größe $k$, dabei ist es auch egal, ob sich etwas überlappt oder nicht. Also folgt $f(G,k) = (G,k,k)\notin TCO$, wie gewünscht.

Es wurde somit 2) gezeigt und damit abschließend, dass $TCO$ NP-vollständig ist.
#### b)
Es ist zu zeigen dass $HALFLENGTHPATH$ – im Folgenden mit $HLP$ abgekürzt – NP-vollständig ist. $HLP = \{G | G \text{ hat einen Pfad der Länge }\lfloor n/2 \rfloor\}$.

Es gilt zweierlei zu zeigen:
1) $HLP$ ist in NP
2) $HLP$ ist NP-schwer

Zunächst wird 1) gezeigt.

Hierfür wird ein Algorithmus angegeben, der das Problem nichtdeterministisch polynomiell löst.

Zur Eingabe $G$ wählt der Algorithmus nichtdeterministisch eine Permutation von $\lfloor n/2 \rfloor$ Knoten aus $G$ aus. Wenn in dieser Permutation Duplikate vorkommen, verwerfen wir sie und geben $false$ aus. Dann testet er die Permutation auf $HAMILTONPATH$ und falls dieser Test positiv ausfällt gibt er $true$ zurück ansonsten $false$.

Dieser Algorithmus läuft in Polynomialzeit, da wir nun $\lfloor n/2 \rfloor$ Knoten ausgewählt werden müssen und wir vom Testen auf Hamiltonpath bereits wissen, dass er polynomiell läuft.

Falls es einen Pfad der geforderten Größe gibt, so wird dieser offensichtlich für eine nichtdetermistische Wahl gefunden. Ansonsten ist bei jeder Wahl einer Knoten-Permutation
eine Bedingung, um zu akzeptieren verletzt, es wird also verworfen. Somit ist der Algorithmus korrekt und zeigt $HLP\in$NP.

Es bleibt 2) zu zeigen.

Wir reduzieren hierzu $HAMILTONPATH$, von dem wir wissen, dass es NP-vollständig ist, auf $HLP$ und somit gilt $HLP$ auch als NP-schwer wegen Transitivität. Es gilt also zu zeigen, dass
$$
HAMILTONPATH \leq_P HLP
$$
Dazu gilt es eine Funktion $f$ zu finden, die deterministisch in polynomieller Zeit berechenbar ist, so dass gilt
$$
\forall G: (G) \in HAMILTONPATH \Leftrightarrow f(G)\in HLP (2.1)
$$
Sei $f$ folgendermaßen definiert:
$$
f(G) = G'
$$
Die Funktion bildet nun den erhaltenen Graphen $G$ auf einen Graphen $G'$, ab der doppelt so viele Knoten hat wie der Ursprungsgraph aber keine neuen Kanten.
Es ist klar, dass $f$ in polynomieller Zeit berechenbar ist und deterministisch funktioniert, da nur $n$ Knoten neu erstellt werden müssen.
Wir zeigen nun Aussage (2.1).
* Falls $G\in HAMILTONPATH$ hat $G$ einen Hamiltonpath der Größe $n = k$. Dann hat $G'$ mit $2k = n$ insbesondere einen Pfad der Größe $\lfloor n/2 \rfloor = k$, da nach Funktionsvorschrift genau noch der selbe Pfad der Länge $k$ existiert. Somit folgt $f(G) = G' \in HLP$, wie gewünscht.
* Falls $G\notin HAMMILTONPATH$ hat $G keinen Pfad der Größe $n = k$. Dann hat $G'$ mit $2k = n$ insbesondere keinen Pfad der Größe $\lfloor n/2 \rfloor = k$. Also folgt $f(G) = G'\notin HLP$, wie gewünscht.

Es wurde somit 2) gezeigt und damit abschließend, dass $HLP$ NP-vollständig ist.

#### c)
Es ist zu zeigen, Dass $DIRECTEDCLIQUE$ – im Folgenden mit $DC$ abgekürzt – NP-vollständig ist.
$DC = \{(G,k) | G \text{ ist gerichtet und es gibt } U \subseteq V_G \text{ mit } |U| = k \text{ so, dass für alle } u,v \in U \text{ mit } u \neq v \text{ gilt } (u,v) \in E_G\}$.
Es wird also nach einer $k$-elementigen Menge gesucht, so dass zwischen jedem Paar zweier Knoten der Menge Kanten in beide Richtungen verlaufen.

Es gilt zweierlei zu zeigen:
1) $DC$ ist in NP
2) $DC$ ist NP-schwer

Zunächst wird 1) gezeigt.

Hierfür wird ein Algorithmus angegeben, der das Problem nichtdeterministisch polynomiell löst.

Zur Eingabe $(G,k)$ (der Graph wird als Adjazenzmatrix eingegeben) wählt der Algorithmus nichtdeterministisch eine Permutation von $k$ Knoten. Wenn diese Duplikate enthält wird sie verworfen($false$ ausgegeben). Ansonsten wird sie nun darauf getestet, ob zwischen jedem Paar zweier Knoten Kanten in beide Richtungen verlaufen und dem entsprechend $true$ oder $false$ ausgegeben.

Dieser Algorithmus läuft in Polynomialzeit, da nur $k\leq n$ Knoten gewählt werden müssen, und weil das Testen auf die Existenz zweier Kanten zwischen zwei bestehenden Knoten danke Adjazenzmatrixdarstellung auch effizient machbar ist. Auch das Prüfen der Duplikate ist schnell.

Falls es gerichtete Cliquen gibt, so werden diese offensichtlich für eine nichtdetermistische Wahl gefunden. Ansonsten ist bei jeder Knotenwahl eine Bedingung, um zu akzeptieren verletzt, es wird also verworfen. Somit ist der Algorithmus korrekt und zeigt $TCO\in$NP.

Es bleibt 2) zu zeigen.

Wir reduzieren hierzu $CLIQUE$, von dem wir wissen, das es NP-vollständig ist, auf $DC$ und somit gilt $DC$ auch als NP-schwer wegen Transitivität. Es gilt also zu zeigen, dass
$$
CLIQUE \leq_P DC
$$
Dazu gilt es eine Funktion $f$ zu finden, die deterministisch in polynomieller Zeit berechenbar ist, so dass gilt
$$
\forall G, k: (G,k) \in CLIQUE \Leftrightarrow f(G,k)\in DC (2.1)
$$
Sei $f$ nun für alle $G,k$ folendermaßen defniniert:
$$
f(G,k) = (G',k)
$$

$G'$ ist hierbei ein gerichteter Graph, bei dem alle ungerichteten Kanten aus G durch zwei gerichtete Kanten, die in beide Richtungen gehen, ersetzt werden. Die Knotenmenge bleibt identisch.

Es ist klar, dass $f$ in polynomieller Zeit berechenbar ist und deterministisch funktioniert, da in einer einer Adjazenzmatrix in $\matbb{O}(m+n)$ alle Kanten einmal traversiert und ersetzt werden können.
Wir zeigen nun Aussage (2.1).
* Falls $(G,k)\in CLIQUE$ hat $G$ eine Clique der Größe $k$. Da alle ungerichteten Kanten aus $G$ in gerichtete Kanten in $G'$ umgewandelt wurden, bilden diese Kanten auche eine gerichtete Clique in $G'$. Somit folgt $f(G,k) = (G',k) \in DC$, wie gewünscht.
* Falls $(G,k)\notin Clique$ hat $G$ keine Clique der Größe $k$. Dann kann auch $G'$ keine gerichtete Clique der Größe $k$ haben. Also folgt $f(G,k) = (G',k)\notin DC$, wie gewünscht.

Es wurde somit 2) gezeigt und damit abschließend, dass $DC$ NP-vollständig ist.