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[2] :

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)
tel 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)

La relaxation linéaire de ce système est le dual du programme d'optimisation pour problème du couplage maximum[3].

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[4]. 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[5] ou à des graphes planaires de degré au plus 3[6].

Approximation[modifier | modifier le code]

L'algorithme d'approximation suivant donne une solution au plus deux fois plus grande que l'optimal : calculer un couplage maximal et mettre chaque paire de sommets dans la solution[7].

Si l'on suppose que P différent de NP, le problème ne peut pas être approché avec un meilleur ratio que 1.3606[8]. Si l'on suppose la conjecture des jeux uniques, le problème ne peut pas être approcher avec un meilleur ratio que 2[9].

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. Tibor Gallai, « Über extreme Punkt- und Kantenmengen. », Ann. Univ. Sci. Budapest, Eötvös Sect. Math.,‎ , p. 133-138.
  3. Ola Svensson (scribe: Mateusz Golebiewski, Maciej Duleba), « Topics in Theoretical Computer Science, Lecture 5: Understanding and using Linear Programming », sur École polytechnique fédérale de Lausanne,‎ .
  4. (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ (lire en ligne), p. 85-103
  5. 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,‎ (DOI 10.1145/800119.803884), p. 47-63
  6. (en) Michael Garey (en) et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman,‎ (ISBN 0-7167-1045-5)
  7. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 1.1.1 (« An approximation algorithm for cardinality vertex cover »).
  8. Irit Dinur et Shmuel Safra, « On the hardness of approximating minimum vertex cover », Annals of Mathematics,‎ , p. 439-485
  9. Subhash Khot et Oded Regev, « Vertex cover might be hard to approximate to within 2-ε », Journal of Computer and System Sciences, vol. 74, no 3,‎ , p. 335-349 (DOI 10.1016/j.jcss.2007.06.019)

Lien externe[modifier | modifier le code]