Problème de couverture de sommets

Cet article ne cite pas suffisamment ses sources (janvier 2013). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». (Modifier l'article)

Cet article est une ébauche concernant l'informatique théorique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie des graphes, le problème de couverture minimum de sommets (ou problème du transversal minimum) est un problème NP-complet faisant partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.

Définition

Une couverture des sommets d'un graphe G est un ensemble C de sommets tel que chaque arête de G est incidente à au moins un sommet de C. On dit que l'ensemble C couvre les arêtes de G. La figure suivante montre des exemples de couvertures des sommets de deux graphes (l'ensemble C est formé des sommets rouges).

Une couverture minimale des sommets est une couverture des sommets de taille minimale. La figure suivante montre des exemples de couvertures minimales des sommets dans les mêmes graphes que ci-dessus.

Définition

Une transversale (ou couverture de sommets) d'un graphe $G=(V,E)$ est un sous-ensemble de sommets $S \subseteq V$ contenant au moins une extrémité de chaque arête (c'est-à-dire, plus formellement, que pour chaque arête $(u,v)$ de $G$ on a $u \in S$ ou $v \in S$).

Le problème de la transversale (Vertex Cover Problem en anglais) est un problème de décision qui consiste à savoir s'il existe une couverture de sommets qui comporte au plus $k$ sommets. Le problème de la transversale minimum est le problème d'optimisation (en) associé, consistant donc à déterminer une transversale de cardinalité minimale.

Si un ensemble de sommets $S$ est une transversale, son complément $\bar S = V \setminus S$ est un stable (ou ensemble indépendant). Donc un graphe à n sommets a une transversale de taille k si et seulement s'il a un stable de taille n-k. On en déduit immédiatement le résultat suivant :

Théorème de Gallai (de) (1959) — Dans tout graphe $G$, α(G) + τ(G) = n.

où α(G) désigne la taille d'un stable maximum, τ(G) désigne la taille d'une transversale minimum et $n = |V|$.

Notes et références

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !