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.

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.

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 ${\displaystyle S\subseteq V}$ tel que pour chaque arête ${\displaystyle (u,v)}$ de ${\displaystyle G}$ on a ${\displaystyle u\in S}$ ou ${\displaystyle 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 ${\displaystyle S}$ est un transversal, son complément ${\displaystyle {\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 ${\displaystyle G}$, α(G) + τ(G) = n.

où α(G) désigne la taille d'un stable maximum, τ(G) désigne la taille d'un transversal minimum et ${\displaystyle 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	${\displaystyle \sum _{v\in V}x_{v}}$			(minimiser le coût total)
tel que	${\displaystyle x_{u}+x_{v}\geq 1}$	pour tout ${\displaystyle \{u,v\}\in E}$		(toutes les arêtes sont couvertes)
	${\displaystyle x_{v}\in \{0,1\}}$	pour tout ${\displaystyle 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].