Clique

Problème de trouver un sous-graphe complet de taille maximale dans un graphe.

Définition

Une clique dans un graphe $G=(V,E)$ est un sous-ensemble $C\subseteq V$ tel que tous les sommets de $C$ sont adjacents deux à deux.

Problème de décision

• Instance : Graphe $G=(V,E)$ et entier $k$
• Question : Existe-t-il une clique de taille au moins $k$ ?

Complexité

Clique est NP-complet.

Certificat

• Certificat de verification : Ensemble $C\subseteq V$
• Vérification : Vérifier que $|C|\ge k$ et que $\forall x,y\in C,x\ne y⟹xy\in E$

Réductions

Clique ${\ll }_P$​ Stable maximum (MIS)

$f:⟨G,k⟩\to ⟨\overline{G},k⟩$

Une clique dans $G$ correspond à un stable dans $\overline{G}$.

Clique ${\ll }_P$​ Vertex Cover (VC)

Par transitivité : Clique ${\ll }_P$​ MIS ${\ll }_P$​ VC