Stable maximum (MIS)

Le problème du stable maximum (Maximum Independent Set) consiste à trouver le plus grand ensemble de sommets sans arêtes entre eux.

Définition

Un stable (ou ensemble indépendant) dans un graphe $G=(V,E)$ est un sous-ensemble $S\subseteq V$ tel que : $\forall x,y\in S,x\ne y⟹xy\notin E$

Problème de décision

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

Complexité

MIS est NP-complet.

Preuve

1. MIS ∈\in ∈ NP
   • Certificat de verification : Ensemble $S\subseteq V$
   • Vérification : $|S|\ge k$ et $\forall x,y\in S,xy\notin E$
2. MIS est NP-difficile 3-SAT ${\ll }_P$​ MIS Transformation : Pour une formule $C=C_1\wedge C_2\wedge ...\wedge C_m$​ avec clauses de taille 3, construire un graphe $G$ où :
   • Chaque littéral de chaque clause devient un sommet
   • Relier les littéraux de la même clause entre eux
   • Relier $x$ et $\overline{x}$ de clauses différentes
   Propriété : $C$ est satisfiable ssi $G$ a un stable de taille $m$.

Réductions classiques

MIS ${\ll }_P$​ Clique

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

Un stable dans $G$ est une clique dans $\overline{G}$.

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

$f:⟨G,k⟩\to ⟨G,n-k⟩$

$S$ est un stable de taille $\ge k$ ssi $V\setminus S$ est une couverture de taille $\le n-k$.

MIS ${\ll }_P$ Sous-graphe

$f:⟨G,k⟩\to ⟨G_1=(V_1,\varnothing ),G_2=G⟩$

où $|V_1|=k$ (graphe vide de $k$ sommets).

Chaîne de réductions

$\text{Clique}{\ll }_P\text{MIS}{\ll }_P\text{VC}$

Via : $⟨G,k⟩\stackrel{\overline{G}}{\to }⟨\overline{G},k⟩\stackrel{n-k}{\to }⟨\overline{G},n-k⟩$