[Soutenance en anglais/Talk in english]
Cette thèse traite des questions structurelles de la théorie des graphes qui découlent de motivations algorithmiques. En effet, les problèmes de graphes NP-complets sont typiquement plus faciles dès lors qu'on restreint la classe de graphes.
Sur les arbres, qui sont des graphes connexes sans cycles, la programmation dynamique donne souvent un algorithme linéaire. Tous les graphes ne sont pas des arbres, mais il est possible de quantifier à quel point un graphe est plus complexe qu'un arbre. Un outil standard pour cela est la largeur arborescente, qui est profondément liée à la théorie des mineurs, et une autre stratégie consiste à obtenir une structure arborescente en supprimant le moins de sommets possible.
La première partie de la thèse porte sur l'idée de graphes universels pour la relation de mineur. Un graphe est mineur-universel pour une famille de graphes s'il contient comme mineur chaque graphe de la famille. Il est en effet plus aisé de manipuler un unique graphe plutôt qu’une famille entière pour en déduire des propriétés. De plus, un résultat célèbre de Robertson, Seymour et Thomas lie cette notion à la largeur arborescente, en s’intéressant en particulier au mineur-universel des graphes planaires. Le but est d’étendre leur résultat à une famille plus vaste.
La deuxième partie se concentre sur la recherche d'une grande forêt (union de plusieurs arbres) induite dans un graphe. Le théorème d’Erdős-Pósa stipule que si un graphe a peu de cycles disjoints, alors il admet un ensemble de sommets de taille constante dont l'élimination produit une forêt. Nous obtenons une propriété similaire pour une famille plus générale, la contrepartie de cette généralisation étant que la taille de cet ensemble est alors logarithmique en la taille du graphe, et cette borne peut être atteinte.
----------------------------
This thesis deals with structural graph theory questions that stem from algorithmic motivations. Indeed, NP-complete graph problems are typically easier on restricted graph classes. On trees, which are connected graphs without cycles, dynamic programming often yields a linear algorithm. Not every graph is a tree, but we can measure how much more complex the graph is. A standard tool is the treewidth which is deeply connected to minor theory and another strategy is to obtain a much simpler structure by deleting as few vertices as possible, as discussed in the second chapter.
The first part of this thesis concerns the idea of minor-universality. A graph is minor-universal for a family of graphs if it contains as a minor every graph in the family. It is indeed easier to deal with a unique graph than the whole family to derive some properties. A celebrated result of Robertson, Seymour, and Thomas links this notion to the minor-universal graph of planar graphs. Our goal is then to extend their result to wider families.
The second part focuses on finding a large induced forest in a graph. The Erdős-Pósa theorem states that if a graph does a small number of vertex-disjoint cycles, then it admits a set of vertices of constant size whose removal yields a forest, called the feedback vertex set. We obtain a similar property for a wider graph class, the trade-off for this generalization being a feedback vertex set whose size depends in the logarithm of the order, and this is sharp.
Le jury sera composé de/The jury will be composed of:
- Marthe BONAMY, PhD Advisor (CR CNRS, Université de Bordeaux)
- Éric COLIN DE VERDIÈRE, Examiner (DR CNRS, Université Gustave Eiffel)
- David EPPSTEIN Absent reviewer (Distinguished Professor, University of California)
- Cyril GAVOILLE, PhD Advisor (Professeur, Université de Bordeaux)
- Gwenaël JORET, Reviewer (Chargé de cours, Université Libre de Bruxelles)
- Zi-Xia SONG, Reviewer (Professeure, University of Central Florida)
- Marc ZEITOUN, Examiner (Professeur, Université de Bordeaux)
[Claire Hilaire] - (Université de Bordeaux, LaBRI, France)
https://www.labri.fr/perso/chilaire/