Comment concevoir un algorithme d’approximation ?

Analyse d’Algorithme

Algorithmes exacts

Temps polynomial vs. exponentiel

Petit rappel sur la notation « O ». Il s’agit d’une convention d’écriture dont le sense est le suivant. Lorsque l’on écrit, par exemple, que t(n) = 2O(f(n)), cela siginifie que : 9 c > 0; n0; 8n > n0; t(n) 6 2c f(n) :
Il faut donc voir la notion « O » non pas comme une valeur ou fonction précise, mais plutôt comme un majorant. Par exemple, on peut écrire que sin n = O(1), où que la complexité d’un programme est en logO(1) n pour dire qu’elle est polylogarithmique. C’est la même chose pour la notation « » que l’on doit voir comme un minorant. La notation est un majorant et minorant à la fois. On écrit ainsi sin n = (1) puisque sin n = O(1) et sin n = (1).
Il faut lire cette notation de gauche à droit seulement, et bien se méfier des multiples
« O » qui peuvent apparaître : O(A) = O(B) n’est pas pareil que O(B) = O(A). Chaque notation « O » se refère à des constantes n0 et c différentes.
Pour illustrer les complexités polynomiales et exponentielles, considérons une instance de taille n 50 (par exemple une grille 7 7), un ordinateur d’une puissance d’un milliard d’instructions par seconde (soit environ 1 GHz).
Le problème des complexités exponentielles est qu’il ne suffit pas de gagner un order de grandeur ( 10) sur la puissance de l’ordinateur pour améliorer définitivement la situation. Bien sûr, le problème de complexité 2n sur un ordinateur 10 fois plus puissant s’exécutera en 13j au lieu de 130j.
Cependant, si l’on double la taille du problème, l’instance est disons un graphe à n = 100 sommets (une grille à 10 10), alors, même avec le nouvel ordinateur, le temps sera de :
T = 22n = (2n)2 (13 j)2 = 179 j et si l’on veut résoudre un problème 10 fois plus grand (une grille 33 33) :
T = 210n = (2n)10 (13 j)2 = 130 milliards d’années :

Problèmes jouets

On va définir trois problèmes que l’on va suivre tout au long de ce cours. Commençons par quelques définitions (voir figure 2.1 pour une illustration) :
– Couverture par sommets (Vertex Cover) : ensemble de sommets contenant au moins une extrémité de chacune des arêtes. En général, on cherche une couverture par sommets de la plus petite taille possible.
– Ensemble indépendant (Independent Set) : ensemble de sommets deux à deux non adjacents. Dans le graphe complémentaire, c’est une clique. En général, on cherche un ensemble indépendant de la plus grande taille possible.
– Ensemble dominant (Dominating Set) : ensemble de sommets S tel que tout sommet u 2= S a au moins un voisin dans S. En général, on cherche un ensemble dominant de la plus petite taille possible.
Les trois problèmes de décisions associés sont : Couverture par sommets de taille k, Ensemble indépendant de taille k et Ensemble dominant de taille k où le but est de savoir si un graphe G possède une couverture par sommets (resp. ensemble indépendant, ensemble dominant) de taille k.
Ces trois problèmes sont NP-complets, même pour les graphes planaires. L’intérêt de ces problèmes est qu’ils sont à la fois très simple (cas d’école) et centraux en théorie de la complexité car beaucoup de problèmes NP-complets se réduisent facilement à ceux-là.
On remarquera qu’une couverture par sommets est un ensemble dominant, le contraire étant faux en général. Également, le complémentaire d’une couverture par sommets est un ensemble indépendant, et qu’inversement, le complémentaire d’un ensemble indépendant est une couverture par sommets. [Exercice : pourquoi ?] Bien sûr, Ensemble indépen-dant est équivalant au problème Clique dans le graphe complémentaire.

Algorithmes exhaustifs (brute force)

Technique consistant à lister toutes les solutions possibles et à vérifier chacune d’elle.
Pour les problèmes de type « sous-ensemble de sommets d’un graphe G », comme les trois problèmes jouets précédant, cela donne :
8S V (G) de taille k, vérifier si S est du type recherché.
Vérifier que S est une couverture par sommets, un ensemble indépendant ou un en-semble dominant, peut se faire en temps O(n + m) = O(n2) où n = jV (G)j et m = jE(G)j. Donc pour savoir s’il existe un ensemble S désiré de taille k il faut un temps :
T = k O(n2) = O(nk+2) car n  k = {nk = k!(n k)! < n (n 1) (n k + 1) < nk : n n!
Cette méthode est appliquée lorsqu’on ne sait rien faire d’autre. Elle peut a priori s’ap-pliquer à tout problème qui est dans NP, car chacun de ces problèmes admet un certificat et un vérificateur positif de complexité polynomiale (voir la section 3.1 au chapitre 3). Il suffit donc de lister tous les certificats positifs possibles et d’appliquer le vérificateur. Ceci dit, il y a des problèmes prouvé dans P où le vérificateur peut être très difficile à obtenir, comme par exemple les problèmes définis à partir d’une liste finie de mineurs exclus (voir la section 2.7). La liste peut être finie mais pas connue de manière explicite, comme la liste des mineurs exclus minimaux pour les graphes toriques (c’est-à-dire dessinable sur le tore).
Cette méthode peut donner de bon résultats seulement si k est très petit (k 6 5) et n pas trop grand (n 6 50). Une complexité en nk+1 = n6 à 1 GHz prend déjà 30 minutes pour n = 50.
Pour comprendre le phénomène d’explosion combinatoire, imaginons que l’on souhaite trier un jeu de cartes en appliquant la méthode exhaustive, et donc en ignorant les algo-rithmes polynomiaux bien connus. La méthode consiste donc ici à mélanger les cartes pour tous les ordres possibles et à vérifier (en temps linéaire) que le tas est trié. Cet algorithme est de complexité n! n (n=e)n+1, n étant le nombre de cartes, tout comme l’algorithme très naïf du voyageur de commerce à n villes.
Supposons maintenant que cet algorithme est implanté sur une architecture parallèle de processeurs surpuissants, chacun capable de tester un milliard de mélange par seconde, associant un tel processeur par particule de l’Univers 2 ( 2400), et qui est exécuté pendant toute la durée de vie de l’Univers (< 15 Ma). Combien, dans ces conditions, pourrait-on trier de cartes ? Réponse : à peu près 52.

Complexité paramétrique : définition

L’idée est de paramétrer le problème et de produire des algorithmes spécifiques et opti-misés pour ce paramètre. Par exemple, on peut être intéressé de produire des algorithmes optimisés en fonction du genre du graphe, c’est-à-dire du nombre de trous de la surface sur lequel est dessiné le graphe (0 trou pour les graphes planaires, 1 trou pour les graphes toriques, …).
Dans la pratique n est très grand (n > 106) et on espère que le paramètre soit pe-tit. Typiquement, la triangulation surfacique d’objets réels (une carrosserie de voiture ou d’avion par exemple) est un graphe ou maillage comprennant de nombreux sommets (n #triangles) alors que le nombre de trous de la surface supportant le graphe est limité (fe-nêtres, portes, etc.). Par ce biais, on espère que la difficulté du problème est liée au fait que le paramètre k soit grand, et non pas n (cf. figure 2.2).
Définition 3 Un problème de paramètre k est de complexité paramétrique polynomiale (en abrégé fpt pour Fixed Parametrized Tractable) si la complexité en temps de pour une instance de taille n est bornée par f(k) nO(1) pour une certaine fonction f.
Supposons que soit un problème NP-complet et que k soit un paramètre borné par une fonction polynomiale en n, c’est-à-dire k 6 nO(1). Par exemple, si k représente la taille d’une couverture par sommets, d’un ensemble indépendant ou encore d’un ensemble dominant, on a k 6 n.

1 Introduction 
1.1 À quoi ça sert ?
1.2 Quelques algorithmes que nous analyserons
1.3 Des algorithmes pour construire quoi ?
1.4 Existence d’objets spécifiques: les spanners
2 Algorithmes exacts 
2.1 Temps polynomial vs. exponentiel
2.2 Problèmes jouets
2.3 Algorithmes exhaustifs (brute force)
2.4 Complexité paramétrique: définition
2.5 Arbre borné de recherche
2.5.1 Couverture par sommets de taille k
2.5.2 Ensemble indépendant pour les graphes planaires
2.5.3 Ensemble dominant pour les graphes planaires
2.5.4 Améliorations : raccourcissement de l’arbre
2.6 Réduction à un noyau : « kernalisation »
2.6.1 Principe et propriété
2.6.2 Exemple de noyau
2.6.3 Couverture par sommets
2.6.4 Noyau et approximation
2.7 Théorie des mineurs de graphes
2.7.1 Définitions
2.7.2 Théorème des mineurs de graphes
2.7.3 Applications
2.8 Réduction aux graphes de treewidth bornée
2.8.1 Décomposition arborescente
2.8.2 Un exemple simple: 3-Coloration
2.8.3 Couverture par sommets pour treewidth bornée
2.8.4 Application aux graphes planaires
2.8.5 Amélioration pour les graphes planaires
2.9 Remarques finales
3 Algorithmes d’approximation
3.1 Introduction
3.2 Problèmes bien caractérisés
3.2.1 Couplage
3.2.2 Les problèmes MIN-MAX
3.2.3 Comment concevoir un algorithme d’approximation ?
3.3 Couverture par sommets de taille minimum
3.3.1 Un premier algorithme
3.3.2 Un second algorithme
3.3.3 Technique de précalcul (color coding)
3.4 Couverture par ensembles
3.4.1 Algorithme glouton
3.4.2 Un second algorithme
3.4.3 Algorithme exact