Soutenance mémoire
Définitions et hiérarchie de classes
Définition 2.2 (Problème paramétré). Un problème paramétré est un langage L ⊆ Σ ∗ ×N, où Σ dénote un alphabet fini. Le second composant est appelé le paramètre du problème. Étant donné un problème paramétré L, nous définissons un couple (I,k) ∈ Σ∗ ×N comme une instance de L. Nous disons que l’instance (I,k) est positive si et seulement si (I,k) appartient à L. instance
Définition 2.3 (algorithme FPT). Un problème paramétré L admet un algorithme FPT s’il peut être décidé en temps f (k)·|I| O(1) si une instance (I,k) de L est positive, où f dénote une fonction calculable ne dépendant que de k. La classe des problèmes paramétrés admettant un algorithme FPT est appelée F PT (pour fixed- F PT parameter tractable). Nous disons de manière similaire qu’un problème paramétré peut être résolu en temps F PT s’il admet un algorithme FPT. Remarques :
– Formellement, un tel algorithme est appelé uniformément FPT. En effet, certains problèmes admettent des algorithmes non-uniformément FPT, i.e. pour tout entier k fixé, il existe un algorithme polynomial particulier résolvant le problème. En d’autres termes, l’algorithme peut différer suivant la valeur du paramètre, ce qui n’est pas le cas des algorithmes uniformément FPT. Par souci de simplicité, nous parlerons uniquement d’algorithmes FPT, le fait qu’ils soient uniformes étant sous-entendu.
– Lorsque nous évoquons la complexité d’un algorithme FPT, nous utilisons la notation O∗, qui fait abstraction de la partie polynomiale de la complexité de l’ algorithme considéré. O ∗() Ainsi, O ∗(2k) représente la complexité 2k·nO(1) . La notion d’algorithmes FPT trouve son principal intérêt lorsque le paramètre associé au problème est petit comparé à la taille de l’instance. Ainsi, arriver à contenir l’explosion combinatoire à ce seul paramètre permet d’obtenir des algorithmes efficaces en pratique [87]. Dans de nombreuses applications, et notamment en ce qui concerne les problèmes d’édition de graphes, le paramètre correspondra donc au nombre d’éditions autorisé, qui sera petit en comparaison de la taille de l’instance. Dans le cadre de cette thèse, nous nous intéresserons principalement à ce paramètre. Théoriquement parlant, déterminer l’existence d’un algorithme FPT pour un problème paramétré donné est également important, puisqu’il est conjecturé que certains problèmes paramétrés n’admettent pas d’algorithme FPT. Hiérarchie de classes. Nous introduisons brièvement la W -hiérarchie [56, 57], qui permet de hié- W -hiérarchie rarchiser la difficulté des problèmes paramétrés. Le premier niveau (mis à part P et F PT ) de difficulté en théorie de la complexité paramétrée est représenté par la classe W [1]. En particulier, un analogue au Théorème de Cook [40] a été démontré, énonçant que le problème SHORT TURING MACHINE ACCEPTANCE est W [1]-Difficile [129]. En d’autres termes, si ce problème est résoluble en temps O(n k+1 ), il serait surprenant qu’il admette un algorithme FPT. Cela a donc donné lieu à la conjecture suivante, qui est l’analogue de P 6= NP en théorie de la complexité classique
Résoudre le problème G -EDITION en temps FPT lorsque G est héréditaire
Nous présentons maintenant une généralisation de cette idée, qui permet de concevoir un algorithme FPT pour le problème G -EDITION (ainsi que G -VERTEX DELETION) dès lors que la classe G est héréditaire et caractérisée par une famille finie de sous-graphes induits interdits. Nous présentons ce résultat dans le cas de la suppression de sommets, les idées étant les mêmes pour l’édition d’arêtes. Ce résultat, dû à Cai [31], est un résultat majeur en ce qui concerne la complexité paramétrée des problèmes d’édition de graphes. Le principe de cet algorithme est le suivant. Nous supposons dans la suite que h dénote le nombre maximum de sommets contenus dans un sous-graphe induit interdit de G. Comme précédemment, cet arbre de recherche a une hauteur bornée par k et possède donc au plus h k feuilles. Cela permet donc d’obtenir un algorithme FPT ayant une complexité O∗(hk). Observons que décider si un graphe appartient à la classe G peut se faire en temps O(nh) par définition de G. Remarquons également que cela permet de retrouver l’algorithme présenté pour VERTEX COVER, puisque ce problème peut se formuler de la manière suivante : existe-t-il un ensemble d’au plus k sommets dont la suppression permet d’obtenir un ensemble indépendant ? La classe des ensembles indépendants admet un seul-sous graphe induit interdit, composé de deux sommets reliés par une arête. Ainsi, cet algorithme a bien une complexité de 2k·nO(1).
Largeurs de graphe
Il existe de nombreux paramètres permettant de mesurer la largeur d’un graphe [28, 132, 142,143]. Dans le cadre de cette thèse, nous évoquons uniquement l’un des plus classiques, la treewidth [143] (que nous utiliserons Chapitre 8). Introduite par Robertson et Seymour dans leur série d’articles sur les mineurs de graphes (voir [142], par exemple), cette largeur arborescente a été par la suite largement étudiée et utilisée [42, 44, 123]. Un des théorèmes les plus importants à ce sujet est le Théorème de Courcelle [42], s’énonçant de manière simplifiée comme suit :
Théorème 2.7 (Courcelle [42]). Soit (G,ω) une instance d’un problème L paramétré par la treewidth ω du graphe G. Si l’appartenance au langage L peut s’exprimer en Logique Monadique du Second Ordre, alors décider si (G,ω) appartient à L est FPT. Nous ne rentrons pas ici dans les détails de la logique monadique du second ordre, ni dans le fonctionnement ou la complexité de cet algorithme. Cependant, il est important de connaître l’existence d’un tel théorème, notamment car il a permis d’établir la complexité paramétrée de nombreux problèmes d’édition de graphes [78, 123] (comme par exemple CHORDAL DELETION, voir Chapitre 8)
Lien avec les protrusions
Nous présentons maintenant la notion de protrusions introduite par Bodlaender et al. [17], qui considère une décomposition arborescente d’un graphe. En utilisant les protrusions, Bodlaender et al. [17] obtiennent plusieurs noyaux polynomiaux pour des problèmes d’édition définis sur des graphes de genre borné, établissant un cadre général pour concevoir des algorithmes de noyau polynomiaux pour de tels problèmes. Bien que le concept de protrusion soit similaire à la notion de branches, certaines propriétés additionnelles sont requises sur le problème considéré afin de pouvoir utiliser cette technique. Comme mentionné précédemment, le graphe doit pouvoir être plongé dans une surface de genre borné. De plus, les problèmes considérés doivent pouvoir s’exprimer en Counting Monadic Second Order Logic (CMSO), et être compacts [17]. Protrusions. Informellement, une protrusion est un sous-graphe de treewidth constante séparé du reste du graphe par un nombre constant de sommets. L’idée permettant de réduire le graphe est la suivante [17] : S’il existe un séparateur de taille constante dont la suppression permet d’obtenir une composante connexe de grande taille et de treewidth constante, alors il est possible de remplacer cette composante connexe par un graphe de petite taille. Si l’idée de cette règle de réduction est similaire à celle présentée dans la section précédente, remarquons cependant que la notion de branche utilise la décomposition d’adjacence propre à la classe G considérée, ce qui n’est pas le cas ici. Les résultats présentés dans [17] s’appliquent au problème p-MIN-CMSO (resp. p-EQ-CMSO, p-MAX-CMSO), où l’instance consiste en un graphe G := (V,E) et un entier k et où l’objectif est de déterminer l’existence d’un ensemble de sommets/arêtes S de taille au plus (resp. exactement, au moins) k dont l’édition satisfait la propriété CMSO G. Par souci de simplicité, nous mentionnons uniquement les résultats concernant p-MIN-CMSO. La version annotée de ce problème possède un ensemble Y ⊆ V de sommets annotés et il est requis que la solution S soit un sous-ensemble de Y . Dans ce qui suit, nous considérons la version annotée du problème p-MIN-CMSO, vu que les résultats obtenus pour les problèmes annotés peuvent être propagés aux versions classiques des problèmes (Corollaire 1 dans [17]).
Un outil combinatoire approprié : les cliques critiques
Nous établissons maintenant une corrélation entre la notion de cliques critiques (définie dans le Chapitre 1) et les 3-leaf powers. L’intérêt de l’utilisation de cet outil combinatoire dans l’étude des leaf powers provient de la remarque suivante : Remarque. Soient G := (V,E) un p-leaf power et T son p-leaf root associé. Soient x un noeud interne de T et Fx l’ensemble des feuilles attachées à x. Alors Fx définit une clique module de G (à condition que p Ê 2) : en effet, toute paire u, v appartenant à Fx est à distance 2 dans T et correspond donc à une arête de G. De plus, u et v sont à égale distance de toute feuille w ∉ Fx , impliquant que l’ensemble correspondant à Fx dans G définit une clique ayant le même voisinage. En supposant sans perte de généralité que le modèle T est optimal (i.e. les vrais jumeaux de G sont attachés au même noeud interne de T ), Fx définit alors une clique module maximale, i.e. une clique critique. La notion de cliques critiques permet en particulier d’obtenir une caractérisation simple pour les 3-leaf powers, formulée comme suit.
Théorème 3.4 ([24, 26]). Un graphe G := (V,E) est un 3-leaf power si et seulement si son graphe des cliques critiques C (G) est une forêt. Rappelons que le graphe des cliques critiques C (G) d’un graphe G := (V,E) peut-être vu comme un sous-graphe de G induit en conservant un unique sommet par clique critique de G. Ainsi, le graphe des cliques critiques de G contient toute l’information structurelle de G. En particulier, nous utiliserons le Théorème 3.4 de manière extensive afin d’élaborer nos règles de réduction.
|
Table des matières
Remerciements
Introduction
Théorie de la complexité
Formalisation de la complexité paramétrée
Travaux réalisés durant la thèse
1 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
2 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
2.3.5 Bornes inférieures pour des problèmes d’édition de graphes
Partie I. Edition de graphes – réduire les branches
Règles de réduction génériques pour le problème G -EDITION
Réduction via la notion de branches
Lien avec les protrusions
3 Noyau cubique pour CLOSEST 3-LEAF POWER
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 de branches
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-LEAF POWER COMPLETION et EDGE DELETION
4 Noyau polynomial pour PROPER INTERVAL COMPLETION
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 de branches
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 : BIPARTITE CHAIN DELETION
5 Noyau cubique pour COGRAPH EDITION
5.1 Cographes et décomposition modulaire
5.2 Noyaux cubiques pour COGRAPH EDGE-DELETION et COMPLETION
5.2.1 Règles de réduction basées sur la décomposition modulaire
5.2.2 Borner la taille d’une instance réduite
5.3 Noyau cubique pour COGRAPH EDITION
Partie II. Edition d’autres structures – Conflict Packing
6 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 TRIANGLE EDGE DELETION
6.1.3 Algorithme de noyau via ajustement
6.2 Noyau quadratique pour CLUSTER VERTEX DELETION
7 Applications de la méthode Conflict Packing
7.1 Noyau linéaire pour FEEDBACK ARC SET IN TOURNAMENTS
7.1.1 Tournois et acyclicité
7.1.2 Conflict Packing et Partition Sûre
7.2 Noyau linéaire pour DENSE ROOTED TRIPLET INCONSISTENCY
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 DENSE BETWEENNESS et DENSE CIRCULAR ORDERING
7.3.1 DENSE BETWEENNESS
7.3.2 DENSE CIRCULAR ORDERING
Partie III. Techniques alternatives et Conclusion
8 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 FEEDBACK VERTEX SET
9 Conclusion et perspectives de recherche
9.1 État de l’art
9.2 Techniques introduites et résultats obtenus
9.3 Perspectives de recherche et problèmes ouverts
9.3.1 Edition de graphes
9.3.2 Edition de relations
Bibliographie
Index
Table des figures
A Bornes inférieures pour Cl-FREE EDGE DELETION et Pl-FREE EDGE DELETION
B Noyaux pour FEEDBACK ARC SET IN TOURNAMENTS
C Réduction du problème MULTICUT à treewidth bornée
Télécharger le rapport complet
