UNIVERSITÉ DE VERSAILLES SAINT-QUENTIN EN YVELINES École Doctorale Sciences et Technologies de Versailles – STV Laboratoire E3S SUPELEC, Département Informatique THÈSE DE DOCTORAT DE L’UNIVERSITÉ DE VERSAILLES SAINT-QUENTIN-EN-YVELINES Spécialité : Informatique Présentée par : Dimitri Watel Pour obtenir le grade de Docteur de l’Université de Versailles Saint-Quentin-en-Yvelines Approximation de l’arborescence de Steiner soutenue le 26 novembre 2014 Directeur de thèse : Dominique Barth : Professeur, Prism, UVSQ Encadrants de thèse : Cédric Bentz : Maître de conférence, CEDRIC, CNAM Marc-Antoine Weisser : Enseignant-Chercheur, E3S, Supélec Rapporteurs : Cristina Bazgan : Professeur, LAMSADE, Université Paris Dauphine Bruno Escoffier : Professeur, LIP6, Université Pierre et Marie Curie Examinateurs : Jean-Claude König : Professeur, LIRMM, Université de Montpellier Yannis Manoussakis : Professeur, LRI, Université Paris Sud Numéro national d’enregistrement : Version du 3 décembre 2014 Table des matières Introduction 1 I Contexte de l’étude 5 1 Algorithmes exacts pour le problème de l’arborescence de Steiner 7 1.1 Algorithmes exacts paramétrés par k . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Algorithmes exacts basés sur la programmation linéaire . . . . . . . . . . . . 11 2 Approximabilité du problème de l’arborescence de Steiner 15 2.1 Résultats préliminaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Résultats d’approximabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Résultats d’inapproximabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Récapitulatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Problèmes connexes au problème de l’arborescence de Steiner 27 3.1 Problèmes de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Problèmes de couverture par ensembles . . . . . . . . . . . . . . . . . . . . . 30 II Algorithmes d’approximation pour le problème de Steiner 33 4 Approximations gloutonnes pour le cas général 35 4.1 Représentation par une expérience de pensée . . . . . . . . . . . . . . . . . . 37 4.2 Algorithme naïf implémentant de l’expérience . . . . . . . . . . . . . . . . . 40 4.3 Amélioration du rapport d’approximation . . . . . . . . . . . . . . . . . . . . 50 4.4 Optimisation de l’algorithme FLAC . . . . . . . . . . . . . . . . . . . . . . . 53 4.5 Croissance des variables duales . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.6 Évaluation des performances . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.7 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5 Cas des graphes sans circuits structurés en paliers 71 5.1 Description des instances étudiées . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Résolution par le problème de couverture par ensembles . . . . . . . . . . . . 72 5.3 Amélioration du rapport d’approximation . . . . . . . . . . . . . . . . . . . . 72 5.4 Extension : couvrir avec deux paliers ou plus . . . . . . . . . . . . . . . . . . 77 5.5 Adaptation au cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 i ii TABLE DES MATIÈRES 5.6 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6 Approximation exponentielle pour le cas général 79 6.1 Séparation des terminaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.2 Approximation exponentielle pour la couverture par ensembles . . . . . . . . 80 6.3 Généralisation au problème de Steiner . . . . . . . . . . . . . . . . . . . . . 80 6.4 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Conclusion 89 III Problèmes de Steiner à branchements contraints 91 7 Présentation des problèmes étudiés 93 7.1 Limitation du nombre de nœuds de branchement . . . . . . . . . . . . . . . 93 7.2 Limitation du nombre de nœuds diffusants . . . . . . . . . . . . . . . . . . . 95 7.3 Origine des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8 DST avec un nombre limité de nœuds de branchement 101 8.1 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 8.2 Restriction aux graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . 107 8.3 Restriction aux graphes sans circuits . . . . . . . . . . . . . . . . . . . . . . 112 8.4 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 9 DST avec un nombre limité de nœuds diffusants 119 9.1 Propriétés du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 9.2 Construction d’un algorithme d’approximation pour DST . . . . . . . . . . . 121 9.3 Résultat d’inapproximabilité pour DSTLD . . . . . . . . . . . . . . . . . . . 124 9.4 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 10 Algorithmes paramétrés basés sur une énumération de patrons 131 10.1 Algorithme exact FPT en k et d pour DSTLD . . . . . . . . . . . . . . . . . 132 10.2 Algorithme exact probabiliste FPT en k et n pour DSTLB et USTLB . . . 137 s 10.3 Algorithme exact XP en k et p pour DSTLB et USTLB . . . . . . . . . . . . 142 10.4 Synthèse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Conclusion 147 Conclusion générale 149 Bibliographie 155 Annexes 161 A Démonstrations reportées 163 B Reproductibilité de l’expérience 177 TABLE DES MATIÈRES iii B.1 Reproduction des expériences comparant les rapports d’approximation . . . 177 B.2 Reproduction des expériences comparant les temps de calculs . . . . . . . . . 178 C Détail des expériences 179 C.1 Présentation des différents groupes d’instances . . . . . . . . . . . . . . . . . 179 C.2 Résultats détaillés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 D Notions de théorie de la complexité paramétrée 197 D.1 Les classes XP et FPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 D.2 Réduction FPT et W-hiérarchie . . . . . . . . . . . . . . . . . . . . . . . . . 198 Introduction Le sujet de cette thèse porte sur le problème de l’arborescence de Steiner1. Problème : Problème de l’arborescence de Steiner (DST) Instance : - Un graphe orienté G = (V,A) contenant n nœuds et m arcs. - Un nœud r ∈ V appelé racine. - Un ensemble de k nœuds X ⊂ V appelés terminaux. - Une fonction de pondération ω : A → R+. Solution réalisable : Une arborescence T enracinée en r couvrant chaque terminal de X. (cid:80) Optimisation : Minimiser le poids ω(T) = ω(a). a∈T Résoudre DST consiste à mutualiser des arcs pour relier la racine aux terminaux. Un exemple est donné Figure 1. On y observe en particulier qu’il ne suffit pas de relier la racine aux terminaux par des plus courts chemins pour trouver une solution optimale. La dénomination problème de Steiner, dans cette thèse, désignera toujours le problème de l’arborescence de Steiner, ou DST, sauf si cela provoque une ambigüité. Le problème de Steiner peut être vu comme la généralisation de plusieurs problèmes de la littérature sur lesquels nous reviendrons plus en détail dans la partie I : - le problème de recherche d’un chemin de poids minimum (quand k = 1); - le problème d’arborescence couvrante de poids minimum (quand k = n−1 ou k = n); - le problème de couverture par ensembles2; - le problème de l’arbre de Steiner3 : relier un sous-ensembles de nœuds d’un graphe non orienté par un arbre de poids minimum; - le problème de couverture de groupes par arbre de Steiner4 : relier des groupes de nœuds d’un graphe non orienté par un arbre de poids minimum, l’arbre devant couvrir au moins un nœud de chaque groupe; - le problème de couverture de groupes par arborescence de Steiner5, la version orientée du problème précédent. 1. Directed Steiner Tree, en anglais 2. Set Cover 3. Undirected Steiner Tree (UST) 4. Undirected Group Steiner Tree 5. Directed Group Steiner Tree 1 2 INTRODUCTION b r a c Figure 1 – Un exemple d’instance de DST où les trois terminaux de X sont a, b et c. Les poids des arcs sont tous unitaires. Il faut au minimum 5 arcs pour relier r aux terminaux. Une solution optimale est représentée avec les arcs en tirets bleus. On observe en particulier que r n’est pas relié à a avec un plus court chemin. La première version du problème de Steiner est celle du problème de l’arbre de Steiner dans le plan euclidien, où un ensemble de points du plan, nommés terminaux, doivent être reliés par une série de segments pouvant faire intervenir des points intermédiaires et dont la longueur totale minimum. Premièrement, étudiée par Fermat avec 3 terminaux, cette version fut généralisée à n terminaux par Gauss [CD01]. Si le mathématicien Jakob Steiner a donné son nom au problème, c’est probablement dû au succès du livre de Richard Courant et Herbert Robbins [CR41], qui furent les premiers à le nommer ainsi [GT93, DH08, (Préfaces)]. Les problèmes de l’arbre de Steiner, de couverture par ensembles et de de couverture de groupes par arbre de Steiner sont NP-difficiles [Kar72, GKR98]. Le problème de l’arborescence de Steiner appartenant à la classe NP, il est donc également NP-difficile. Rechercher des algorithmes exacts ou d’approximation pour DST permet d’en trouver pour ces problèmes. Inversement, des résultats d’inapproximabilité pour ces problèmes s’appliquent au problème de Steiner. On s’intéresse aujourd’hui aux problèmes de Steiner dans les graphes orientés ou non orientés principalement pour leurs applications dans la conception de circuit (problèmes d’intégration à très grande échelle ou VLSI) [CD01], mais aussi de diffusion multicast dans un réseau [Voß06, Win87]. Une machine, appelée racine, fait la demande d’une requête multicast vers un ensemble X de k terminaux dans un réseau. Le but est de satisfaire la requête tout en minimisant l’utilisation de la bande passante. Pour cela on modélise le réseau par un graphe orienté, où le poids de chaque connexion est égal au poids lié à la bande passante consommée si le paquet traverse cet arc. On calcule ensuite une arborescence optimale de Steiner, que le paquet va parcourir de la racine jusqu’aux terminaux. En fonction du réseau ou de l’objectif, on utilisera plutôt le problème de l’arborescence de Steiner ou un des problèmes connexes. Le problème de l’arbre de Steiner, par exemple, servira quand les connexions dans le réseau sont symétriques. INTRODUCTION 3 Ce manuscrit se penche sur l’approximabilité (polynomiale ou non) du problème de l’arborescence de Steiner. Du fait de leur proximité, il semble naturel d’étendre les résultats obtenus dans des graphes non orientés sur le problème de l’arbre de Steiner aux graphes orientés et au problème de l’arborescence de Steiner. Nous rappelons la définition du problème de l’arbre de Steiner ci-après. Problème : Problème de l’arbre de Steiner (UST, non orienté) Instance : - Un graphe non orienté G = (V,E). - Un ensemble de k nœuds X ⊂ V appelés terminaux. - Une fonction de pondération ω : E → R+. Solution réalisable : Un arbre T ⊂ G couvrant tous les terminaux de X. (cid:80) Optimisation : Minimiser le poids ω(T) = ω(e). e∈T Le problème UST peut être approché avec un rapport constant. Une 2-approximation connue pour ce problème consiste à chercher, parmi les couples de terminaux non reliés, celui dont la distance séparant les deux terminaux est minimum, et à recommencer jusqu’à avoir relié tous les terminaux entre eux [Cho78, KMB81]. Une généralisation de cet algorithme au cas de DST est l’algorithme dit des plus courts chemins qui consiste à relier la racine à chaque terminal avec un plus court chemin. Cependant cet algorithme est une k-approximation (nous le démontrerons dans le chapitre 2). La figure 2 montre une instance où la solution renvoyée est k fois plus coûteuse que la solution optimale. Elle montre aussi pourquoi, une fois supprimée la dissymétrie due à l’orientation des arcs mais aussi à la racine, la version non orientée de l’algorithme n’est plus affectée par le piège que pose cette instance. r r x 0 1 1 1 + + + ε ε ε 0 0 0 0 0 0 0 0 0 x x ... x x x ... x x x ... x 1 2 k 1 2 k 1 2 k Poids : k Poids : 1+ε Poids : 1 Figure 2 – Instance où le poids de la solution renvoyée par l’algorithme des plus courts chemins est k fois plus grand que celui d’une solution optimale. Les arcs dont le poids n’est pas précisé ont un poids unitaire. Cette figure représente également, à gauche, une solution renvoyée par l’algorithme des plus courts chemins (en traits gras rouges), au centre, l’arborescence optimale (en traits pointillés bleus), et à droite, la solution renvoyée par l’algorithme si on supprime l’orientation (en traits gras rouges). 4 INTRODUCTION De manière générale, les algorithmes d’approximation développés pour le problème de l’arbre de Steiner ne sont pas généralisables au problème de l’arborescence de Steiner. À moins que P = NP, il n’existe pas d’approximation polynomiale de rapport log2−ε(k) pour DST [HK03]. Trouver une approximation de rapport polylogarithmique en k pour ce problème est une question ouverte puisque le plus petit rapport d’approximation polynomiale connu pour le problème de Steiner est O(kε) quel que soit ε > 0 [CCCD98]. Résultats présentés dans ce manuscrit L’objet de cette thèse consiste à apporter de nouveaux résultats portant sur le problème de Steiner et plus particulièrement son approximabilité polynomiale. La partie I décrit le contexte de l’étude relatif au problème de Steiner, à ses résultats d’approximabilité connus, aux différents algorithmes exacts existants pour ce problème. Nous nous pencherons également sur les problèmes connexes. La partie II est consacrée à la recherche d’algorithmes d’approximations pour DST dans le cas général. Trois résultats sont décrits. Les algorithmes du chapitre 4 sont des algorithmes gloutons dont l’efficacité en pratique est démontrée en fin de chapitre. Le chapitre 5 présente une approximation du problème dans le cas particulier d’un graphe découpé en paliers de nœuds, ceux-ci n’étant reliés qu’aux nœuds du palier suivant. Le rapport de cette approximation est en dessous du plus haut rapport d’inapproximabilité connu pour DST dans le cas général. Enfin, dans le chapitre 6, nous développons un schémas approximation exponentielle qui mêle approximation gloutonne et algorithme exact. Ces algorithmes ne permettent pas de diminuer le rapport d’approximation du problème en dessous de O(kε). C’est pourquoi la partie III de la thèse explore une autre piste. Le problème est contraint de sorte à réduire le nombre de solutions réalisables que l’on peut renvoyer. Sachant que la solution optimale du problème contraint est elle-même une solution réalisable du problème non contraint, peut-on s’en servir pour approcher sa solution optimale? La partie étudie les classes de complexité paramétrée et l’approximabilité des problèmes contraints. Ces contraintes, issues des problématiques de réseaux tout-optiques, sont présentées dans le chapitre 7. On se limite premièrement aux solutions qui n’utilisent qu’un nombre limité de nœuds de branchement. Cette étude est faite dans les chapitres 8 et 10. Secondement, on se restreint aux solutions qui n’utilisent qu’un nombre limité de nœuds diffusants6. Ce problème est étudié dans les chapitres 9 et 10. La dernière partie de ce manuscrit est dédiée aux annexes. La première annexe contient un ensemble de démonstrations non présentes dans le chapitre 4, du fait de leur longueur. Les deux annexes suivantes se focalisent sur les expériences du chapitre 4. L’annexe B présente l’implémentation de ces expériences dans le but de pouvoir les reproduire. Elles utilisent une bibliothèque d’instances disponibles en ligne. Ces instances sont utilisées globalement. L’annexe C détaille plus finement les résultats de ces expériences. Enfin l’annexe D présente quelques notions fondamentales de la théorie de la complexité paramétrée nécessaires à la compréhension de ce manuscrit. 6. diffusing nodes ou multicast-capable en anglais. Un nœud non diffusant ne peut transmettre un paquet entrant que vers un seul destinataire, alors qu’un nœud diffusant peut le retransmettre autant de fois qu’il le souhaite vers chacun de ses destinataires.