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.

Couverture par sommet[modifier | modifier le code]

Définition[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

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|.

Problème algorithmique[modifier | modifier le code]

Description[modifier | modifier le code]

Le problème d'optimisation, appelé problème de la couverture minimum par sommets, est le suivant :

Entrée : un graphe G
Question : Quel est le plus petit entier k, tel qu'il existe une couverture par sommets de G de taille k

et le problème de décision :

Entrée : un graphe G et un entier k
Question : existe-t-il une couverture par sommet de G de taille k ?

Programme linéaire[modifier | modifier le code]

Le programme d'optimisation linéaire en nombres entiers associé est :

minimiser \sum_{v \in V} c(v) x_v    (minimiser le coût total)
sous les contraintes que x_u+x_v\geq 1 pour tout \{u,v\} \in E (toute les arêtes sont couvertes)
x_v\in\{0,1\} for all v\in V. (chaque sommet est dans la couverture ou non)

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, et peut lui-même être réduit du problème de la clique.

Le problème est encore NP-complet si l'on se restreint à des graphes cubiques[3] ou à des graphes planaires de degré au plus 3[4].

Algorithmes[modifier | modifier le code]

Approximation[modifier | modifier le code]

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
  3. Michael R. Garey, David S. Johnson et Larry Stockmeyer, « Some simplified NP-complete problems », dans Proceedings of the sixth annual ACM symposium on Theory of computing,‎ 1974 (DOI 10.1145/800119.803884), p. 47-63
  4. (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman,‎ 1979 (ISBN 0-7167-1045-5)

Lien externe[modifier | modifier le code]