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

Anthony Perez

Description

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

Sujets

• Durand
• Deletion

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 novembre 2011
• Nombre de lectures: 143
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

A CADÉMIE DE M ONTPELLIER U N I V E R S I T É M O N T P E L L I E R Sciences etTechniques duLanguedoc

T HÈ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 P AUL . . . . . . . . . . . . . Directeur de Recherche CNRS, LIRMM, Université Montpellier II CoDirecteur de thèse M. Stéphane B ESSY Maître de Conférences, LIRMM, Université Montpellier II. . . . . . . . . . . . . . . . . . . . . . Rapporteurs M. Rolf N IEDERMEIER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Professor, Technische Universität, Berlin M. Ioan T ODINCA . . . . . . . . . . Professeur, LIFO, Université d’Orléans. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Président du jury M. Bruno D URAND . . . . . . . . . . . . . . . . . . . . . . . . . . . Professeur, LIRMM, Université Montpellier II. . . . . . . . Examinateur M. Frédéric H AVET Chargé 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 C OGRAPH E DITION 105 5.1 Cographes et décomposition modulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.2 Noyaux cubiques pour C OGRAPH E DGE D ELETION et C OMPLETION . . . . . . . . . . . 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 C OGRAPH E DITION 113. . . . . . . . . . . . . . . . . . . . . . . . . . .

Partie I. Edition de graphes  réduire les branches Règles de réduction génériques pour le problèmeGE DITION . . . . . . . . . . . . . . . . . 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 P ROPER I NTERVAL C OMPLETION 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 : B IPARTITE C HAIN D ELETION . . . . . . . . . . . . . . . . . . . . . .

Noyau cubique pour C LOSEST 3L EAF P OWER 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L EAF P OWER C OMPLETION et E DGE D ELETION . . . . . . . .

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 T RIANGLE E DGE D ELETION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 F EEDBACK A RC S ET IN T OURNAMENTS

9

Bibliographie

B

C

Table des figures

Index

A

Noyau quadratique pour C LUSTER V ERTEX D ELETION . . . . . . . . . . . . . . . . . . .

187

191

185

201

173

127 129 129 130 134 136 139 141 143 144 149

iii

124

8

Réduction du problème M ULTICUT à 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 M ULTICUT . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Compression itérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Description générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Application sur F EEDBACK V ERTEX S ET . . . . . . . . . . . . . . . . . . . . . . .

Applications de la méthode Conflict Packing 7.1 Noyau linéaire pour F EEDBACK A RC S ET IN T OURNAMENTS . . . . . . . . . . . . . . . . 7.1.1 Tournois et acyclicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Conflict Packing et Partition Sûre . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Noyau linéaire pour D ENSE R OOTED T RIPLET I NCONSISTENCY . . . . . . . . . . . . . . 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 D ENSE B ETWEENNESS et D ENSE C IRCUL AR O RDERING . . . . . . . . . . . . . . . . . . . 7.3.1 D ENSE B ETWEENNESS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 D ENSE C IRCUL AR O RDERING . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

151

7

6.2

TABLE DES MATIÈRES

E ELETIO D N etP l F REE E DGE D ELETION Bornes inférieures pourC l F REE E DG

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 V OYAGEUR DE C OMMERCE [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