Deux problèmes, une réduction d'une ligne

La transformation. À un graphe $G=(S,A)$, on associe son complémentaire $\bar{G}=(S,\bar{A})$, où $\bar{A}$ contient exactement les paires de sommets non adjacentes dans $G$.

L'équivalence. Un ensemble $X$ de sommets est une clique de $G$ si et seulement si toute paire de $X$ est une arête de $G$, si et seulement si aucune paire de $X$ n'est une arête de $\bar{G}$, si et seulement si $X$ est un stable de $\bar{G}$. La correspondance est donc la même pour toutes les tailles :

$$G\text{ a une clique de taille }k⟺\bar{G}\text{ a un stable de taille }k.$$

La fonction $(G,k)\mapsto (\bar{G},k)$ est calculable en $\Theta (|S{|}^2)$ : on parcourt une fois toutes les paires. C'est bien polynomial, et la réduction inverse est la même transformation, puisque $\overline{\stackrel{ˉ}{G}}=G$.

Vérification. Sur $200$ graphes aléatoires de $3$ à $8$ sommets, la taille de la plus grande clique de $G$ et celle du plus grand stable de $\bar{G}$ ont été calculées séparément, par recherche exhaustive : égalité dans les $200$ cas.

Ce que cette réduction montre, et ne montre pas. Elle montre que les deux problèmes ont exactement la même difficulté. Elle ne montre pas qu'ils sont difficiles : pour cela, il faudrait une réduction depuis sat, et c'est l'objet d'un des problèmes de ce chapitre.

Une remarque de méthode. Les réductions les plus utiles sont souvent les plus courtes. Celle-ci ne fait aucun travail : elle change le point de vue sur la même donnée. Beaucoup de problèmes de graphes sont ainsi deux écritures d'un seul — le complémentaire d'un stable maximal est une couverture par sommets minimale, ce qui donne une troisième écriture du même objet.