Probleme – Du seuil à l'approximation garantie : la couverture par sommets

1. La version décision. « Le graphe $G$ possède-t-il une couverture par sommets de taille au plus $k$ ? » Le certificat est l'ensemble $C$ lui-même : on vérifie $|C|\le k$, puis que chaque arête a une extrémité dans $C$ — en $\Theta (n+m)$. Le problème est donc dans $\mathsf{NP}$ ; il est np-complet, ce qu'on admet.

Par la dichotomie sur le seuil, la version optimisation n'est pas plus difficile — $\lceil {\log }_{2}n\rceil$ appels suffisent.

2. Le glouton, et sa garantie. L'algorithme est court, et son idée n'est pas celle qu'on croit :

C <-- ensemble vide
tant qu'il reste une arete non couverte
    choisir une telle arete (u, v)     -- n'importe laquelle
    ajouter u ET v a C                 -- LES DEUX
rendre C

Terminaison : chaque tour couvre au moins une arête, le nombre d'arêtes non couvertes décroît strictement.

Correction : à la sortie, plus aucune arête n'est non couverte, donc $C$ est bien une couverture.

La garantie. Soit $M$ l'ensemble des arêtes choisies par l'algorithme. Deux arêtes de $M$ ne partagent aucune extrémité : dès qu'on choisit $(u,v)$, toutes les arêtes touchant $u$ ou $v$ deviennent couvertes et ne seront plus choisies. $M$ est donc un couplage. Or toute couverture doit contenir au moins une extrémité de chaque arête de $M$, et ces extrémités sont deux à deux distinctes :

$$|C_{\text{opt}}|\ge |M|.$$

Et l'algorithme rend $|C|=2|M|$. Donc $|C|\le 2|C_{\text{opt}}|$.

Ce qui rend la preuve possible, et c'est le point du problème : on ne compare pas $|C|$ à l'optimum, qu'on ne connaît pas. On le compare à une borne inférieure calculée en même temps, le couplage $M$. Toute approximation garantie fonctionne ainsi.

Prendre les deux extrémités est nécessaire. Un glouton qui n'ajouterait qu'une extrémité — disons $u$ — ne fournirait plus de couplage, et la borne s'effondrerait.

3. Les mesures. Sur $299$ graphes aléatoires de $4$ à $10$ sommets, l'optimum étant calculé par recherche exhaustive :

Le pire rapport observé pour le premier vaut exactement $2$ : la garantie est atteinte, elle n'est donc pas améliorable telle quelle. Le graphe qui la réalise est simple : une arête isolée demande une couverture de taille $1$, et l'algorithme en rend $2$.

4. Le glouton « degré maximal ». Il choisit à chaque tour le sommet de plus grand degré parmi les arêtes restantes. Les mesures lui donnent un rapport moyen de $1,01$ — meilleur en pratique, et de loin.

Et pourtant on garde l'autre. Car le glouton par degré n'a aucune garantie constante : on construit, pour tout $c$, des graphes bipartis où il rend $c$ fois l'optimum. Son rapport est en $\Theta (\log n)$, non borné.

C'est la distinction la plus utile du chapitre, et elle rejoint celle de son ouverture : la mesure sur des instances aléatoires dit ce qu'un algorithme fait d'habitude, la démonstration dit ce qu'il fait toujours. Un rapport moyen de $1,01$ ne protège de rien si l'instance suivante est adverse — et sur un problème np-complet, elle finit toujours par l'être.

C'est aussi ce que voulait dire le chapitre chap:gloutons en parlant d'approximation garantie : le mot porte tout.