ACADÉMIE DE MONTPELLIER U N I V E R S I T M O N T P E L L I E R II

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
ACADÉMIE DE MONTPELLIER U N I V E R S I T É M O N T P E L L I E R II Sciences et Techniques du Languedoc THÈSE présentée au Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier pour obtenir le diplôme de doctorat Spécialité : Informatique Formation Doctorale : Informatique École Doctorale : Information, Structures, Systèmes Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures par Anthony PEREZ Soutenue le 14 Novembre 2011, devant le jury composé de : Directeur de thèse M. Christophe PAUL . . . . . . . . . . . . . Directeur de Recherche CNRS, LIRMM, Université Montpellier II Co-Directeur de thèse M. Stéphane BESSY . . . . . . . . . . . . . . . . . . . . . . Maître de Conférences, LIRMM, Université Montpellier II Rapporteurs M. Rolf NIEDERMEIER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Professor, Technische Universität, Berlin M. Ioan TODINCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  • noyaux cubiques pour cograph edge-deletion

  • conflict packing

  • cograph edition

  • problèmes d'édition de graphes

  • noyau

  • deletion

  • transformations polynomiales en temps

  • triangle edge


Publié le : mardi 1 novembre 2011
Lecture(s) : 139
Tags :
Source : univ-orleans.fr
Nombre de pages : 243
Voir plus Voir moins
ACADÉMIE DEMONTPELLIER UN I V E R S I T ÉMO N T P E L L I E R Sciences etTechniques duLanguedoc
THÈSE
II
présentée au Laboratoire d’Informatique de Robotique et de Microélectronique de Montpellier pour obtenir le diplôme de doctorat
Spécialité Formation Doctorale École Doctorale
: : :
Informatique Informatique Information, Structures, Systèmes
Algorithmes de noyau pour des problèmes d’édition de graphes et autres structures
par
Anthony PEREZ
Soutenue le 14 Novembre 2011, devant le jury composé de :
Directeur de thèse M. Christophe PAUL. . . . . . . . . . . . . Directeur de Recherche CNRS, LIRMM, Université Montpellier II CoDirecteur de thèse M. Stéphane BESSYMaître de Conférences, LIRMM, Université Montpellier II. . . . . . . . . . . . . . . . . . . . . . Rapporteurs M. Rolf NIEDERMEIER. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Professor, Technische Universität, Berlin M. Ioan TODINCA. . . . . . . . . . Professeur, LIFO, Université d’Orléans. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Président du jury M. Bruno DURAND. . . . . . . . . . . . . . . . . . . . . . . . . . . Professeur, LIRMM, Université Montpellier II. . . . . . . . Examinateur M. Frédéric HAVETChargé de recherche CNRS, INRIA SophiaAntipolis. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table des matières
Remerciements
Table des matières
Introduction Théorie de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Formalisation de la complexité paramétrée . . . . . . . . . . . . . . . . . . . . . . . . . . . . Travaux réalisés durant la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
Préliminaires et notations 1.1 Graphes nonorientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Quelques familles de graphes connues . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Décomposition modulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Edition de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Autres structures : collection de relations . . . . . . . . . . . . . . . . . . . . . . . . . .
Complexité paramétrée et algorithmes de noyau 2.1 Complexité et algorithmes paramétrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Définitions et hiérarchie de classes . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Applications et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Quel paramètre choisir ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Algorithmes de noyau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Définition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Techniques pour prouver la nonexistence de noyaux polynomiaux . . . . . . . . . . 2.3.1 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Transformations polynomiales en temps et paramètre . . . . . . . . . . . . . . 2.3.3 Couleurs et identifiants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Crosscomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
i
1
3 3 7 9
13 13 14 16 18 18
21 23 23 24 26 29 29 34 35 37 38 39
4
40
Noyau cubique pour COGRAPHEDITION105 5.1 Cographes et décomposition modulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.2 Noyaux cubiques pour COGRAPHEDGEDELETIONet COMPLETION. . . . . . . . . . . 109 5.2.1 Règles de réduction basées sur la décomposition modulaire . . . . . . . . . . 109 5.2.2 Borner la taille d’une instance réduite . . . . . . . . . . . . . . . . . . . . . . . 111 5.3 Noyau cubique pour COGRAPHEDITION113. . . . . . . . . . . . . . . . . . . . . . . . . . .
Partie I. Edition de graphes  réduire les branches Règles de réduction génériques pour le problèmeGEDITION. . . . . . . . . . . . . . . . . Réduction via la notion de branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lien avec les protrusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47 49 52 54
6
2.3.5
ii
3
77 79 81 84 85 85 91 92 93 96 98 101 102
TABLE DES MATIÈRES
5
Noyau polynomial pour PROPERINTERVALCOMPLETION 4.1 Définition et caractérisation des graphes d’intervalles propres . . . . . . . . . . . . . . 4.1.1 Branches et Kjoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Règles de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Règles de réduction via la notion debranches. . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Borner la taille d’un Kjoin propre . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Extraire un Kjoin propre depuis un Kjoin . . . . . . . . . . . . . . . . . . . . . 4.3.3 Borner la taille d’un Kjoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.4 Couper les 1branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.5 Couper les 2branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Détecter les branches en temps polynomial . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Borner la taille d’une instance réduite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Un cas particulier : BIPARTITECHAINDELETION. . . . . . . . . . . . . . . . . . . . . .
Noyau cubique pour CLOSEST3LEAFPOWER 3.1 Définition et caractérisation des 3leaf powers . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Un outil combinatoire approprié : les cliques critiques . . . . . . . . . . . . . . 3.1.2 Branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Règles de réduction via la notion debranches. . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Couper les 1branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Couper les 2branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Borner la taille d’une instance réduite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Noyaux cubiques pour 3LEAFPOWERCOMPLETIONet EDGEDELETION. . . . . . . .
57 59 60 62 63 64 67 71 73
Partie II. Edition d’autres structures  Conflict Packing
Conflict Packing : un outil de conception de noyaux 6.1 Principe général et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Partition Sûre et Conflict Packing . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.2 TRIANGLEEDGEDELETION. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.3 Algorithme de noyau via ajustement . . . . . . . . . . . . . . . . . . . . . . . .
117 119 119 122 123
115
Bornes inférieures pour des problèmes d’édition de graphes . . . . . . . . . .
Conclusion et perspectives de recherche 165 9.1 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 9.2 Techniques introduites et résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . 168 9.3 Perspectives de recherche et problèmes ouverts . . . . . . . . . . . . . . . . . . . . . . 169 9.3.1 Edition de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 9.3.2 Edition de relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Noyaux pour FEEDBACKARCSET INTOURNAMENTS
9
Bibliographie
B
C
Table des figures
Index
A
Noyau quadratique pour CLUSTERVERTEXDELETION. . . . . . . . . . . . . . . . . . .
187
191
185
201
173
127 129 129 130 134 136 139 141 143 144 149
iii
124
8
Réduction du problème MULTICUTà treewidth bornée
153 15 5 155 156 15 7 157 157 159 159 161
Techniques alternatives 8.1 Règles de branchement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Sur quels problèmes brancher ? . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.2 Questions ouvertes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Réduction à treewidth bornée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.1 Dichotomie petite/grande treewidth . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2 Application au problème MULTICUT. . . . . . . . . . . . . . . . . . . . . . . . 8.3 Compression itérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Description générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Application sur FEEDBACKVERTEXSET. . . . . . . . . . . . . . . . . . . . . . .
Applications de la méthode Conflict Packing 7.1 Noyau linéaire pour FEEDBACKARCSET INTOURNAMENTS. . . . . . . . . . . . . . . . 7.1.1 Tournois et acyclicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Conflict Packing et Partition Sûre . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Noyau linéaire pour DENSEROOTEDTRIPLETINCONSISTENCY. . . . . . . . . . . . . . 7.2.1 Adaptation de la notion de Partition Sûre . . . . . . . . . . . . . . . . . . . . . 7.2.2 Définition et conséquences du Conflict Packing . . . . . . . . . . . . . . . . . 7.2.3 Algorithme de noyau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 DENSEBETWEENNESSet DENSECIRCUL ARORDERING. . . . . . . . . . . . . . . . . . . 7.3.1 DENSEBETWEENNESS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 DENSECIRCUL ARORDERING. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
151
7
6.2
TABLE DES MATIÈRES
E ELETIO DNetPlFREEEDGEDELETION Bornes inférieures pourClFREEEDG
Partie III. Techniques alternatives et Conclusion
215
Remerciements
Bien que m’ayant apporté une expérience professionnelle unique et particulièrement enrichis sante, cette thèse a surtout été importante sur le plan humain. Il est évident que je n’aurai pas pu la mener à terme sans l’aide de Stéphane et Christophe, dont la patience, la disponibilité, le soutien, la culture scientifique et la bonne humeur permanente m’ont permis de mener ces trois années de recherche dans des conditions plus que parfaites. En ajoutant le fait de travailler avec du dEUS en fond ou avec L’équipe ouverte en permanence, l’environnement était vraiment idéal. Un grand merci également à Stéphan, avec qui travailler fut un réel bonheur (surtout que tu avais tes doctorants sous la main pour passer tes nerfs, et que j’ai ainsi pu échapper à ton courroux à de nombreuses reprises). Je tiens également à remercier tous les membres de l’équipe AlGCo (Philippe, Ignasi, Alex, Daniel, Benjamin, . . .), pour leur gentillesse et leur dynamisme, ainsi que le personnel administratif pour m’avoir aidé dans toutes ces démarches.
Durant ces trois années de thèse, j’ai eu l’opportunité de rencontrer de nombreuses personnes, avec lesquelles j’ai eu la chance de pouvoir travailler. Je remercie donc tous mes coauteurs pour leur collaboration précieuse. Leur contact m’a permis d’apprécier la recherche de différentes manières, et je ne les en remercierai jamais assez. Un immense merci également à Ioan Todinca et Rolf Niedermeier pour avoir accepté de rapporter ce manuscrit, ainsi qu’à Bruno Durand pour avoir accepté de présider le jury de ma soutenance, et à Frédéric Havet pour son rôle d’examinateur.
Je n’oublie bien sûr pas mes cobureaux : Jean, qui m’a supporté toutes ces années, même durant ma période cheveux longs (bien qu’il ait préféré effacer cette période de sa mémoire). Merci d’avoir eu le bon goût de me faire découvrir La Horde du Contrevent (qui a presque compensé ton sa crilège concernant Arctic Monkeys), j’espère que tu sauras apprécier la petite dédicace. Nicolas B., Sandrine, Kevin, Sarah (et MarcOliver), merci également pour votre gentillesse, qui vous a permis de supporter sans broncher mes impressionnants retards. Nicolas T., merci pour tous nos moments geeks, nos moult sandwichs partagés et ton coup de main inestimable pour le déménagement ! Merci enfin aux membres du LIFO (notamment Jérôme, Ali, Ioan, Mathieu L. et Mathieu C.), dont l’accueil chaleureux m’a permis de préparer ma soutenance dans les meilleures conditions. Quant
1
Ω Δ> ¬)π
2
REMERCIEMENTS
à la clique de doctorants/docteurs, merci d’avoir rendu mon intégration si rapide et agréable. Anthony Della Rocca vous salue bien !
Je tiens évidemment à remercier ma famille, et notamment mes parents qui m’ont forcément poussé à arriver jusque là. Faire une liste exhaustive serait beaucoup trop long, donc je me conten terai d’un message général : merci à tous ! Pour toute votre aide, et pour tous les souvenirs accu mulés. Un remerciement particulier au frère (et à Angélique), pour tous nos bons moments passés ensemble, que ce soit à se geler devant un fantastique Nîmes  CroixdeSavoie ou à se prendre un déluge pendant un concert mythique d’Arcade Fire. Merci aussi pour les innombrables kilomètres que vous m’avez aidé à parcourir. Angélique, merci de ne pas avoir (trop) râlé face à la masse de foot que nous t’avons imposée, et pour ta gentillesse. Enfin, je tiens à remercier ma bellefamille, pour son accueil incroyable et son aide plus que précieuse (mais si Kévin tu nous aideras à déménager dans l’autre sens, c’était pas si dur !). Mathieu, merci de me rappeler chaque fois qu’on se voit (même indirectement) qu’il existe des docteurs qui sauvent des vies, eux.
Pour terminer, un immense merci à tous mes amis de longue date, sans qui ces trois années n’au raient pas été les mêmes. Olivier, merci pour ton côté cartésien qui m’a aidé à relativiser plus de situations que tu ne l’imagines, et pour toutes nos sessions Playstation qui m’auront vidé la tête et fait le plus grand bien (même si tu campes). Je vous souhaite tout le bonheur du monde à toi, Stéphanie et au petit Lucas qui vient tout juste de débarquer. Mattias, merci pour tes innombrables coups de main, pour ta bonne humeur hautement communicative, pour ta concentration plus qu’exceptionnelle à Fifa, et pour tous nos fous rires ("passe ! centre ! frappeeee ! ! ooooohh non la barre !"). Coni, enfin, même si on ne se voit plus des masses, chacune de nos rencontres aussi brèves soientelles est un réel plaisir, et j’espère qu’on aura plus l’occasion de se croiser à l’avenir.
Tous ces jolis remerciements n’auraient jamais vu le jour sans le soutien et la bonne humeur constante de Virginie, qui a (presque !) réussi à effacer mon côté gronchon invétéré, et à me faire sortir de ma tanière plus que je ne l’aurai jamais imaginé. Je ne serai jamais allé au bout si tu ne m’avais pas transformé en amont, et si je n’avais pas eu ton soutien. Je ne suis pas très fort pour exprimer les sentiments, alors je vais conclure avec une phrase qui n’aura guère de sens pour la plupart des gens, mais qui en a énormément pour nous. Let’s go for a drive, and see the town tonight. There’s nothing to do, but I don’t mind, when I’m with you.
Théorie de la complexité
Introduction
Contexte historique.Lathéorie de la complexitéa été introduite afin de permettre de mesurer la difficulté d’un problème algorithmique en fonction de lataillede ses instances. De manière plus générale, la théorie de la complexité mesure ladifficulté d’un algorithmerésolvant le problème considéré. Il existe deux principaux types de problèmes : les problèmes d’optimisation, où l’ob jectif est de minimiser ou de maximiser une certaine propriété, et les problèmes dedécision, de mandant une réponse de typeoui/non. Dans la suite de cette introduction ainsi que de cette thèse, nous nous intéressons principalement à des problèmes dedécision. De plus, nous considérons uniquement l’aspecttemporelde la théorie de la complexité, et ne considérons donc pas la notion d’espace. Un problème peut se résoudre de manièreefficacelorsqu’il existe un algorithme le résol vant avec un temps d’exécutionpolynomial en la taille de l’instance considérée. Pendant de nom breuses années, la recherche d’algorithmes polynomiaux pour des problèmes donnés a constitué un axe de recherche majeur [51, 58, 69, 113]. Cependant, de nombreux problèmes classiques (tels que le problème du VOYAGEUR DECOMMERCE[46]) n’arrivaient pas à être résolus en temps po lynomial, laissant supposer que tous les problèmes n’avaient pas une difficulté équivalente. Dans un papier fondateur, intituléPaths, Trees and Flowerset paru en1965dans leCanadian Journal of Mathematics,Jack Edmondsa été l’un des premiers à pressentir que certains problèmes pouvaient effectivement être plusdifficilesque d’autres. Cela se traduit en particulier par la citation suivante : [. . .]There is an obvious finite algorithm, but that algorithm increases in difficulty ex ponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. L’existence systématique d’un algorithme polynomial pour un problème donné était donc re mise en question, et permettait d’ouvrir de nouvelles perspectives de recherche. Does there or does there not exist an algorithm of given order of difficulty for a given class of problems ?
3
4
INTRODUCTION
Quelques années après la parution de cet article, la théorie de laN PComplétudea été forma lisée [40, 72], permettant de donner un cadre théorique aux idées informelles deJack Edmonds.
Théorie de la NPComplétude.L’intuition de lathéorie de laN PComplétudeest la suivante, et est décrite comme telle dans le livreA guide to the theory ofN PCompleteness, parGarey et Johnson[72]. Supposons qu’une personne essaie de résoudre de manièreefficaceun problèmeL et, qu’après plusieurs mois de travail, elle ne soit pas capable de concevoir un tel algorithme. En l’état, cette personne doit donc se résoudre à admettre :
Je n’arrive pas à trouver d’algorithme résolvant ce problème en temps polynomial.
En suivant l’idée deJack Edmondsstipulant que certains problèmes sont probablement plus difficiles que d’autres, il serait alors idéal de trouver un argument permettant de prouver la non existence d’un tel algorithme.
Je n’arrive pas à trouver d’algorithme résolvant ce problème en temps polynomial car il n’existe pas de tel algorithme.
Malheureusement, déterminer la nonexistence d’un algorithme polynomial pour un problème estau moins aussi difficileque d’en démontrer l’existence. Ainsi, cette piste de recherche ne semble pas être concluante. La solution proposée par lathéorie de laN PComplétudeest d’étu dier lesrelations d’équivalenceexistant entre les problèmes. Plus exactement, cette théorie se base
THÉORIE DE LA COMPLEXITÉ
5
sur le principe deréductions polynomiales. SoientLetLdeux problèmes. Le problèmeLseré duit en temps polynomial versLs’il existe un algorithme qui prend en entrée une instanceIdeL, ′ ′ s’exécute en temps polynomial en|I|et retourne une instanceéquivalenteIdu problèmeL. Ainsi, tout algorithme résolvantLen temps polynomial résoudraLen temps polynomial. En effet, l’algo ′ ′ rithme consistant à réduireLversLen temps polynomial puis à utiliser l’algorithme résolvantL en temps polynomial permet de résoudreLen temps polynomial. De ce fait, le problèmeLestau moins aussi difficileque le problèmeL. Ainsi, si l’on peut réduire le problème étudiéLdepuisun problèmeclassiqueLconsidéré commedifficile, cela permettra d’établir queLestaussi difficile queL, qui a été largement étudié et pour lequel aucun algorithme polynomial n’est connu.
Je n’arrive pas à trouver d’algorithme résolvant ce problème en temps polynomial, mais je peux vous garantir qu’aucune de ces personnes n’y est arrivée.
Il reste donc à déterminer formellement ce que sont lesproblèmes difficiles. Ce concept peut être établi via lathéorie de laN PComplétude, qui s’appuie principalement sur les deux classes de problèmes suivantes : P: classe de problèmes pouvant se résoudre de manièredéterministeen tempspolynomial. N P: classe de problèmes pouvant se résoudre de manièrenondéterministeen tempspoly nomial. Une autre formulation de la classeN Pest la suivante : un problème appartient àN Ps’il est possible devérifier en temps polynomialuncertificatpour le problème,i.e.de vérifier en temps polynomial si une solution proposée est une solution du problème considéré. De manière non for melle, les problèmes de la classePsont ceux que l’on peutrésoudre efficacement, ceux de la classe N Pceux que l’on peutvérifier efficacement. Considérée comme l’une desconjectures du millé nairepar leClay Mathematics Institute, la conjecture suivante est l’hypothèse de travail supposée tout le long de cette thèse et a été formulée indépendamment parStephen COOK[40] etLeonid LEVIN[115] en1971.
Conjecture 1(P6=N P).Il existe un problème de la classe N P qui n’appartient pas à la classe P .
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.