Voir la source de Problème de couverture par sommets

[[Fichier:Couverture de sommets.svg|vignette|Il y a 6 couloirs à contrôler et il faut placer le nombre minimal de caméras 360° de façon que chaque couloir soit vu par au moins une caméra. Le nombre minimal est 2 et les deux caméras forment une 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''', '''''{{Langue|en|Vertex Cover}}''''' en anglais<ref>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 : {{Approximation algorithms (Vazirani)}}. Voir le [http://perso.ens-lyon.fr/nicolas.schabanel/livre_approx.html plan du livre en ligne]. </ref>) 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 [[optimisation (mathématiques)|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é (informatique théorique)|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 <math>S \subseteq V</math> tel que pour chaque arête <math>(u,v)</math> de <math>G</math> on a <math>u \in S</math> ou <math>v \in S</math>. 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).

:[[Fichier: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.

:[[Fichier:Minimum-vertex-cover.svg]]

=== Propriétés combinatoires ===

Si un ensemble de sommets <math>S</math> est un transversal, son complément <math>\bar S = V \setminus S</math> est un [[stable (théorie des graphes)|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<ref>
{{article
 |auteur= Tibor Gallai
 | titre= Über extreme Punkt- und Kantenmengen.
 | périodique= Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 
 | volume =2
 | passage = 133-138
 | année =1959}}.</ref> :

{{Théorème|Théorème de [[Tibor Gallai|Gallai]] (1959)|Dans tout graphe <math>G</math>, α(G) + τ(G) &#61; n.}}

où α(G) désigne la taille d'un [[stable maximum]], τ(G) désigne la taille d'un transversal minimum et <math>n = |V|</math>.

== 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
| colspan="2" | <math>\sum_{v \in V} x_v</math>
| &nbsp;&nbsp;
| (minimiser le coût total)
|-
| tel que
| <math>x_u+x_v\geq 1</math>
| pour tout <math>\{u,v\} \in E</math>
|
| (toutes les arêtes sont couvertes)
|-
|
| <math>x_v\in\{0,1\}</math>
| pour tout <math>v\in V</math>.
|
| (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 (théorie des graphes)|couplage maximum]]<ref>
{{lien web|url=http://theory.epfl.ch/courses/topicstcs/Lecture52015.pdf|titre=Topics in Theoretical Computer Science, Lecture 5: Understanding and using Linear Programming|auteur=Ola Svensson (scribe: Mateusz Golebiewski, Maciej Duleba)|date= mars 2015|site=[[École polytechnique fédérale de Lausanne]]}}.</ref>.

== Complexité ==
Le [[problème de décision]] associé à ce [[optimisation (mathématiques)|problème d'optimisation]] est [[NP-complet]], et fait partie des [[21 problèmes NP-complets de Karp]]<ref>{{Reducibility Karp 1972}}</ref>. Sa NP-dureté est démontrée par une réduction du problème de la [[clique (théorie des graphes)|clique]] à celui-ci. Le problème de couverture de sommets est souvent utilisé en [[Théorie de la complexité (informatique théorique)|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 [[graphe cubique|graphes cubiques]]<ref>
{{chapitre
 | nom1=Garey      | prénom1=Michael R. 
 | nom2=Johnson    | prénom2=David S.  
 | nom3=Stockmeyer | prénom3=Larry      
 | titre chapitre=Some simplified NP-complete problems
 | titre ouvrage =Proceedings of the sixth annual ACM symposium on Theory of computing
 | passage=47-63
 | année=1974
 | doi=10.1145/800119.803884}}</ref> ou à des [[graphe planaire|graphes planaires]] de [[Degré (théorie des graphes)|degré]] au plus 3<ref>{{Garey Johnson NP}}</ref>. Sur les graphes bipartis, il est résolu en temps polynomial avec un algorithme de [[Couplage (théorie des graphes)|couplage]] maximum, par application du [[Théorème de Kőnig (théorie des graphes)|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 (théorie des graphes)|couplage maximal]] et mettre chaque paire de sommets dans la solution<ref>{{Approximation algorithms (Vazirani)|numéro chapitre=1.1.1|titre chapitre=An approximation algorithm for cardinality vertex cover}}.</ref>.

Si l'on suppose que [[P=NP|P différent de NP]], le problème ne peut pas être approché avec un meilleur ratio que {{formatnum:1.3606}}<ref>
{{article
 |titre=On the hardness of approximating minimum vertex cover
 | auteur1=[[Irit Dinur]]  |auteur2=[[Shmuel Safra]]
 | périodique=[[Annals of Mathematics]]| passage=439-485
 | année=2005}}</ref>. Si l'on suppose la [[conjecture des jeux uniques]], le problème ne peut pas être [[Algorithme d'approximation|approché]] avec un meilleur ratio que 2<ref>{{article
 | auteur1 = [[Subhash Khot]]
 | auteur2= [[Oded Regev]]
 | titre=Vertex cover might be hard to approximate to within 2-ε
 | périodique=Journal of Computer and System Sciences
 | volume=74 | numéro=3
 | année=2008
 | passage=335-349
 | doi=10.1016/j.jcss.2007.06.019}}</ref>.

== Notes et références ==
<references />

== Liens externes ==

* {{Lien web|langue= en|url=http://www.nada.kth.se/~viggo/wwwcompendium/node10.html |titre= Minimum Vertex Cover|date= 20 mars 2000 |site=A compendium of NP optimization problems |consulté le=6 août 2014 | auteur = Viggo Kann }}
* {{Lien web|langue= en|url=https://pacechallenge.org/2019/vc/ |titre= PACE 2019 (Track Vertex Cover Exact)|date= 2019 |site=Parameterized Algorithms and Computational Experiments Challenge}}

== Article lié ==
* [[Complexité paramétrée]]

{{Palette 21 problèmes NP-complets de Karp}}
{{Portail|informatique théorique}}

[[Catégorie:Théorie des graphes]]
[[Catégorie:Problème NP-complet|Couverture de sommets]]