Exercice
Une couverture par sommet d’un graphe $G=(S,A)$ non orienté est un sous ensemble $W \subseteq S$ tel que pour chaque arrête $(u,v) \in A$ on a $u \in W$ ou $v \in W$. Le problème de décision de la couverture par sommet, appelé en anglais vertex cover et désigné par la suite par VC, est le suivant :
Entrée : Un graphe $G = (S,A)$ et un entier $k$.
Sortie : Existe-t-il une couverture par somme de $G$ de taille $k$ ?
Ce problème fait partie des 21 problèmes NP-complet de Karp qui ont été prouvé NP-complet par Richard Karp en 1972.
$1.$ Montrer que VC est dans NP.
On effectue une réduction à partir de Clique : le problème de l’existence d’une clique de taille $l$ dans un graphe $G$. Considérons une instance $\displaystyle \left(G=\left(S,A\right),\;l\right)$ de clique.
$2.$ Montrer que $G$ a une clique de taille $l$ si et seulement si $\bar{G}$, le complémentaire de $G$, a une couverture par sommet de taille $|S| – l$.
$3.$ Conclure.
À présent que nous avons montré que VC est NP-complet, on note que $k$ est un paramètre du problème. On peut donc se demander ce qui se passe si $k$ est fixé.
$4.$ Montrer que pour tout $k$ entier, le problème $k$-VC qui prend en entrée un graphe $G$ représentée sous forme de matrice d’adjacence et vérifie s’il existe une couverture par sommet de taille exactement $k$ se résout en temps cubique en le nombre de sommets.
Correction
$1.$ On donne comme certificat une liste de $k$ sommets et on vérifie en temps polynomiale en la taille du graphe qu’ils constituent bien d’une couverture par sommet. De ce fait, VC appartient à NP.
$2.$ Supposons que $G$ a une clique de taille $l$ et soit $C$ l’ensemble des sommets de cette clique. On note que pour toute arrête $(x,y)$ dans $\bar{G}$ on ne peut avoir $x \in C$ et $y \in C$, car cela contredirait le fait que $C$ soit une clique dans $G$. Ainsi $S \smallsetminus C$ est une couverture par sommet de $\bar{G}$ et il en résulte donc que $\bar{G}$ admet une couverture par sommet de taille $|S|-l$.
Réciproquement, si $\bar{G}$ possède une couverture par sommet de taille $|S|-l$, on note $V$ cette couverture. Par définition, il n’y a aucune arrête entre les éléments de $S \smallsetminus V$. De ce fait, $S \smallsetminus V$ constitue une clique dans le complémentaire de $\bar{G}$. On a donc bien exhibé une clique de taille $l$ dans $G$.
$3.$ On peut transformer tout problème de Clique en un problème de VC en temps polynomiale. Or Clique est un problème NP-complet. Il en résulte que VC est NP-difficile. Or VC est dans NP, donc VC est un problème NP-complet.
$4.$ Notons que pour toute arrête $(s,t)$ de $G$ et toute couverture par sommet $V$ de $G$, on a au moins $s$ ou $t$ dans $V$. Autrement dit, pour tout sommet $s$, soit $s \in V$ soit tous ses voisins font partie de $V$. Cela nous donne donc l’algorithme récursif suivant.
Dans le pire des cas, notre algorithme tourne en $O\left(2^{k}n^{3}\right)$ étapes. Il est important de noter que $k$ ne fait pas partie de l’instance du problème $k$-VC. Ainsi, le facteur $2^{k}$ ne varie pas suivant la taille de $G$ et n’est donc qu’une constante. Ainsi, kVertexCover fonctionne en temps $O\left(n^{3}\right)$.
Exercice en lien
- Le problème des 3 couleurs : Une autre preuve de NP-complétude.