Probleme – Une réduction depuis SAT

1. La construction. Soit $\phi$ une formule à $m$ clauses de trois littéraux chacune. On construit un graphe $G_{\phi }$ :

• un sommet par occurrence de littéral, soit $3m$ sommets, notés $(i,j)$ pour le $j$-ième littéral de la $i$-ième clause ;
• une arête entre les trois sommets d'une même clause — un triangle par clause ;
• une arête entre deux sommets portant des littéraux contradictoires, c'est-à-dire $x$ et $\neg x$, dans des clauses différentes.

On demande alors : $G_{\phi }$ a-t-il un stable de taille $m$ ?

2. L'équivalence.

Si $\phi$ est satisfiable, soit $v$ une valuation qui la satisfait. Dans chaque clause, choisissons un littéral vrai sous $v$, et prenons le sommet correspondant : cela fait $m$ sommets. Ils forment un stable, car (a) ils sont dans des clauses différentes, donc aucune arête de triangle ne les joint ; (b) ils sont tous vrais sous $v$, donc deux d'entre eux ne peuvent être contradictoires — $x$ et $\neg x$ ne sont jamais vrais ensemble.

Si $G_{\phi }$ a un stable $X$ de taille $m$, alors $X$ contient au plus un sommet par triangle — donc, comme il y a $m$ triangles et $|X|=m$, exactement un par clause. Définissons $v$ en rendant vrai chaque littéral porté par un sommet de $X$. C'est cohérent : si $x$ et $\neg x$ étaient tous deux dans $X$, l'arête de contradiction les joindrait, contredisant que $X$ est stable. On complète $v$ arbitrairement sur les variables non rencontrées. Chaque clause contient alors un littéral vrai : $\phi$ est satisfiable.

3. La construction est polynomiale. Le graphe a $3m$ sommets ; le nombre d'arêtes est majoré par $3m$ (les triangles) plus $\left(\genfrac{}{}{0ex}{}{3m}{2}\right)$ (les contradictions possibles), donc par $O(m^2)$. On l'écrit en parcourant tous les couples d'occurrences : $\Theta (m^2)$.

Une croissance quadratique : polynomiale, ce qui est la seule chose exigée. La réduction n'a pas à être efficace, elle a à être polynomiale.

La vérification. Sur $120$ formules aléatoires de $2$ à $4$ variables et $1$ à $4$ clauses, on a d'un côté décidé la satisfiabilité par recherche exhaustive, et de l'autre cherché exhaustivement un stable de taille $m$ dans le graphe construit : les deux réponses coïncident dans les $120$ cas. C'est la vérification de l'équivalence, instance par instance.

4. La conclusion. $3$-sat est np-complet (par Cook-Levin, admis, et la réduction classique de sat vers $3$-sat). La réduction ci-dessus montre donc que stable est np-difficile. Comme il est de plus dans $\mathsf{NP}$ — le certificat est l'ensemble des $m$ sommets, vérifiable en $O(m^2)$ —, il est np-complet. Et par l'exercice sur le complémentaire d'un graphe, clique l'est aussi.

Ce qu'il faut retenir de la méthode, puisque le programme dit que « la connaissance d'un catalogue de problèmes np-complets n'est pas un objectif » :

• on choisit une brique par clause et une par variable ;
• on relie les briques de sorte que le choix local soit contraint exactement comme la logique l'exige ;
• on vérifie l'équivalence dans les deux sens — c'est là que se cachent les fausses réductions ;
• on vérifie que la construction est polynomiale.

Les quatre étapes se retrouvent dans toutes les réductions du domaine, y compris celle vers la $3$-coloration donnée en exemple par le chapitre.