\section{Größte Clique}
\begin{tasks}
	\item
		Wir prüfen für jede Teilmenge $V' \subseteq V$, ob sie eine Clique ist, 
		d. h. wir prüfen für jeden Knoten in $V'$ ob es eine Kante zu jedem anderen
		Knoten in $V'$ gibt.

		Dabei fangen wir mit der größten Teilmenge an und werden schrittweise kleiner.
		Wenn wir eine Clique finden ist sie die größte.
		
		Exakt haben wir eine Laufzeit von
		\[
			\sum_{i=1}^n \binom{n}{i} \cdotp i^2
		\]

		Es exitieren maximal $2^n$ viele Teilmengen. Für jede Teilmenge $V'$
		prüfen wir für jedes Knotenpaar, ob sie adjazent sind. Das geht in $\Oh(n^2)$ Zeit.
		Also $\Oh(2^n \cdotp n^2)$.
		\points{2}

	\item \label{1b}
		Wir prüfen diesmal für jede Teilmenge der Nachbarschaft $N(v)$ von $v$ (insbesondere ist
		$v$ in der $N(v)$) ob sie eine
		Clique ist. Wir fangen wieder mit den größten Teilmengen an. Wenn wir eine Clique
		finden, ist sie die größte, die $v$ enthält.

		Die exakte Laufzeit ist damit
		\[
			\sum_{i=1}^{deg(v)} \binom{\abs{N(v)}}{i} \cdotp i^2
		\]
		
		Den Knotengrad können wir mit dem Maximalknotengrad $\Delta$ abschätzen,
		ebenso wie die Größe von $N(v)$.
		Somit erhalten wir
		\[
			\sum_{i=1}^\Delta \binom{\Delta}{i} \cdotp i^2
		\]
		Das heißt wir bekommen asymptotisch $\Oh(2^\Delta \cdotp \Delta^2)$.
		\points{2}

	\item
		Mit dem Ansatz aus Teilaufgabe \ref{1b} können wir einen Algorithmus
		für \alg*{Größte Clique} mit Parameter $\Delta$ konstruieren.

		Dafür iterieren wir über jeden Knoten $v \in V$ und führen für ihn unseren
		Algorithmus aus.

		Das führt zu einer Laufzeit von $\Oh((2^\Delta \cdotp \Delta^2) \cdotp n)$, was in FPT liegt, da das die Form $\Oh(f(k) \cdotp \abs{I}^c)$ mit 
		Parameter $k$, Instanz $I$ und Konstante $c$ erfüllt.
		\points{2}
\end{tasks}