Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP-complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de contraintes. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes Closest 3-Leaf Power, Cograph Edition et Proper Interval Completion. Ces résultats constituent les premiers noyaux polynomiaux pour ces problèmes. Concernant les problèmes d'édition de contraintes, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème Feedback Arc Set in Tournaments, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème Dense Rooted Triplet Inconsistency. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette technique sur les problèmes Betweenness in Tournaments et Dense Circular Ordering, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes. / In this thesis, we study the parameterized complexity of several NP-complete problems. More precisely, we study the existence of polynomial kernels for graph and constraints modification problems. In particular, we introduce the concept of branches, which provides polynomial kernels for some graph modification problems when the target graph class admits a so-called adjacency decomposition. This technique allows us to obtain the first known polynomial kernels for the Closest 3-Leaf Power, Cograph Edition and Proper Interval Completion problems. Regarding constraint modification problems, we develop and push further the concept of Conflict Packing, a technique that has already been used in a few parameterized problems and that provides polynomial kernels for several problems. We thus present a linear vertex-kernel for the Feedback Arc Set in Tournaments problem, and adapt these techniques to obtain a linear vertex-kernel for the Dense Rooted Triplet Inconsistency problem as well. In both cases, our results improve the best known bound of $O(k^2)$ vertices. Finally, we apply the Conflict Packing technique on the Betweenness in Tournaments and Dense Circular Ordering problems, obtaining once again linear vertex-kernels. To the best of our knowledge, these results constitute the first known polynomial kernels for these problems.
| Identifer | oai:union.ndltd.org:theses.fr/2011MON20240 |
| Date | 14 November 2011 |
| Creators | Perez, Anthony |
| Contributors | Montpellier 2, Paul, Christophe, Bessy, Stéphane |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0025 seconds