Problème de couverture par sommets

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, Vertex Cover en anglais[1]) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes.

Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait 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éfinitions[modifier | modifier le code]

Couverture par sommet[modifier | modifier le code]

Une couverture par sommets, ou transversale d'un graphe G est un ensemble C de sommets tel que chaque arête de G=(V,E) est incidente à au moins un sommet de C, ie un sous-ensemble de sommets S \subseteq V tel que pour chaque arête (u,v) de G on a u \in S ou v \in S. 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).

Vertex-cover.svg

Une couverture minimale par 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.

Minimum-vertex-cover.svg

Problème algorithmique[modifier | modifier le code]

Le problème de couverture par sommets (sans poids) est le problème d'optimisation qui consiste à trouver une telle couverture. Dans le cas où les sommets ont des poids, le problème consiste à trouver une couverture dont la somme des poids est minimale.

Complexité[modifier | modifier le code]

Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp[2]. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.

Approximation[modifier | modifier le code]

Algorithmes[modifier | modifier le code]

Propriétés combinatoires[modifier | modifier le code]

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[modifier | modifier le code]

  1. La traduction problème de couverture par sommets est notamment présente dans le chapitre 14 de la traduction par N. Schabanel de l'ouvrage de référence : (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7). Voir le plan du livre en ligne.
  2. (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ 1972 (lire en ligne), p. 85-103