Le problème de la couverture par sommet

$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