Problème de couverture par sommets

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 sommets

Définition

Une couverture par sommets ou transversal 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).

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.

Propriétés combinatoires

Si un ensemble de sommets $S$ est un transversal, son complément ${\bar {S}}=V\setminus S$ est un stable (ou ensemble indépendant). Donc un graphe à n sommets a un transversal 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 (1959) — Dans tout graphe $G$ , α(G) + τ(G) = n.

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

Problème algorithmique

Description

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

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

minimiser	$\sum _{v\in V}x_{v}$		(minimiser le coût total)
tel que	$x_{u}+x_{v}\geq 1$	pour tout $\{u,v\}\in E$	(toutes les arêtes sont couvertes)
	$x_{v}\in \{0,1\}$	pour tout $v\in V$ .	(chaque sommet est dans la couverture ou non)

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

Complexité

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]. Sa NP-dureté est démontrée par une réduction du problème de la clique à celui-ci. Le problème de couverture de sommets est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.

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]. Sur les graphes bipartis, il est résolu en temps polynomial avec un algorithme de couplage maximum, par application du théorème de Kőnig.

Approximation

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 approché avec un meilleur ratio que 2^[9].

Notes et références

↑ 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.
↑ Tibor Gallai, « Über extreme Punkt- und Kantenmengen. », Ann. Univ. Sci. Budapest, Eötvös Sect. Math., vol. 2,‎ 1959, p. 133-138.
↑ 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, mars 2015.
↑ (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
↑ 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
↑ (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)
↑ (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 »).
↑ Irit Dinur et Shmuel Safra, « On the hardness of approximating minimum vertex cover », Annals of Mathematics,‎ 2005, p. 439-485
↑ Subhash Khot et Oded Regev, « Vertex cover might be hard to approximate to within 2-ε », Journal of Computer and System Sciences, vol. 74, n^o 3,‎ 2008, p. 335-349 (DOI 10.1016/j.jcss.2007.06.019)

Liens externes

(en) Viggo Kann, « Minimum Vertex Cover », sur A compendium of NP optimization problems, 20 mars 2000 (consulté le 6 août 2014)
(en) « PACE 2019 (Track Vertex Cover Exact) », sur Parameterized Algorithms and Computational Experiments Challenge, 2019

Article lié

Complexité paramétrée

Portail de l'informatique théorique

[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., vol. 2,‎ 1959, 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, mars 2015.

[4] (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, 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, 1974 (DOI 10.1145/800119.803884), p. 47-63

[6] (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)

[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,‎ 2005, 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, n^o 3,‎ 2008, p. 335-349 (DOI 10.1016/j.jcss.2007.06.019)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]