Vertex Cover (VC)

Le problème de couverture de sommets consiste à trouver un ensemble minimal de sommets couvrant toutes les arêtes.

Définition

Une couverture de sommets (vertex cover) dans un graphe $G=(V,E)$ est un sous-ensemble $C\subseteq V$ tel que : $\forall xy\in E,x\in C\text{ ou }y\in C$

Problème de décision

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

Complexité

VC est NP-complet.

Preuve

1. VC $\in$ Classe NP
   • Certificat de verification : Ensemble $C\subseteq V$
   • Vérification : $|C|\le k$ et $\forall xy\in E,x\in C\vee y\in C$
2. VC est NP-difficile Stable maximum (MIS) ${\ll }_P$​ VC Transformation : $f:⟨G=(V,E),k⟩\to ⟨G^{\prime }=G,k^{\prime }=n-k⟩$ Preuve de correction : $S$ est un stable de taille $\ge k$ ssi $V\setminus S$ est une couverture de taille $\le n-k$.
   • Si $S$ est stable, aucune arête ne relie deux sommets de $S$, donc toute arête a au moins une extrémité dans $V\setminus S$
   • Si $C$ est une couverture, $V\setminus C$ ne contient aucune arête, donc est un stable

Réductions

Clique ${\ll }_P$​ VC

Par transitivité : Clique ${\ll }_P$​ MIS ${\ll }_P$​ VC

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

Chaîne complète

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

Relation avec MIS

VC et MIS sont des problèmes duaux : $C\text{ est une couverture}⟺V\setminus C\text{ est un stable}$

Cette dualité est au cœur de la réduction entre les deux problèmes.