Cliquenproblem
Einfache Sprache
Gibt es in einem Graph zumindest $n$ Knoten, die alle untereinander paarweise verbunden sind. Das Cliquenproblem ist ein Entscheidungsproblem.
Cliquenproblem
Gegeben: ein Ungerichteter Graph $G$ und eine Zahl $k\in\mathbb N_{\geq1}$. Entscheide: Gibt es eine Clique $C$ in $G$ mit $|C|\geq k$?
Alternative Formulierung als Sprache:
$$CLIQUE=\left\{\begin{align*}u\#v|& u\in\{0,1\}^* \text{stellt Adjazenzmatirix von $G$ dar,}\\ &v\in\{0,1\}^* \text{stellt $k$ dar,}\\& G \text{ hat Clique mit $k$ Knoten}\end{align*}\right\}\;.$$Sätze
Naiver Algorithmus
Hier wird nach dem Versuch-und-Irrtum-Prinzip alle möglichen Teilmengen von Knoten der Größe $k$ ausprobiert. Da die Anzahl der Teilmenge jedoch exponentiell mit der Anzahl der Knoten wächst ist die Laufzeit in EXPTIME.
\begin{algorithm}
\caption{naive\_clique\_solver}
\begin{algorithmic}
\Input V, k
\ForAll{V' $\subseteq$ V with |V'| = k}
\If{V' ist eine Clique}
\Return True
\EndIf
\EndFor
\Return False
\end{algorithmic}
\end{algorithm}
Der Algorithmus hat eine Laufzeit $T(V,k)\geq 2^{|V|/2}$ für $k=|V|/2$.