51 lines
1.8 KiB
TeX
51 lines
1.8 KiB
TeX
\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}
|