Julien DURON soutiendra sa thèse de doctorat en Informatique, réalisée sous la direction d'Edouard BONNET, le 4 juillet 2025 à 14h.
Résumé de la thèse
Un graphe est composé d'un ensemble de points, appelés sommets, connectés par des arêtes. La simplicité de cette définition fait des graphes un outil mathématique particulièrement utile à la représentation de divers phénomènes, on pourra penser à la propagation d'une maladie, à des réseaux cristallins ou bien aux dépendances entre documents administratifs. Cependant, de leur généralité vient leur complexité : puisqu'ils peuvent représenter de nombreux phénomènes, les graphes peuvent a priori en représenter des particulièrement retors. Cela rend certains problèmes simples en apparence difficiles à résoudre en toute généralité. Par exemple trouver le plus long chemin entre deux points est un problème NP-complet. Lorsque l'on veut malgré tout pouvoir résoudre ces problèmes, une approche possible consiste à restreindre la classe de graphes sur laquelle on travaille, en évitant les structures trop complexes.
De cette approche naît un compromis entre l'étendue des problèmes que l'on peut résoudre et la diversité des phénomènes que l'on peut représenter. L'étude de ce compromis a mené à l'introduction de nombreuses classes de graphes, dont cette thèse propose d'explorer les différentes modèles de définitions, que ce soit en interdisant des sous-structures particulières, en imposant des contraintes structurelles via des paramètres bien choisis, ou simplement en limitant le nombre de graphes contenus par la classe. Nous verrons de quels propriétés ces définitions s'accompagnent, quels sont leur connexions, et leur utilité dans la résolution de problèmes algorithmiques.
Après une introduction aux différentes notions nécessaires à la compréhension du manuscrit, notre travail se divise en quatre parties. Tout d'abord, nous considérons la difficulté à décider si un graphe appartient ou non à certaines classes de graphes. Nous montrons qu'il est, de manière inattendue, difficile de décider si un graphe appartient à diverses généralisations des graphes dégénérés. De plus, nous verrons que différents paramètres proches de la mim-width, introduits par Vatshelle en 2012, sont para-NP-durs. Tout au long de ces démonstrations, nous nous familiariserons avec deux concepts particulièrement utiles : les graphes ordonnés, et les décompositions arborescentes.
Dans une deuxième partie, nous introduisons la stretch-width, un paramètre restreignant la twin-width, ce dernier ayant été proposé récemment par Bonnet, Kim, Thomassé et Watrigant. La stretch-width, malgré une première définition ardue, est liée à différents objets combinatoires : matrices d'adjacences structurées, graphes ordonnés, décompositions liées à la twin-width. Après avoir établi l'équivalence entre ces notions, nous verrons qu'une borne constante sur la stretch-width implique une borne logarithmique sur la tree-width, dans le cas des graphes de degré borné.
Dans la troisième partie, nous abordons la question suivante : dans quelles conditions un graphe contient-il une grande sous-structure « simple » ? C'est une question centrale de la théorie de Ramsey, où la sous-structure « simple » fait généralement référence à un graphe complet. Ici, nous prendrons les chemins comme structure simple : étant donné un graphe avec un long chemin, dans quelles conditions contient-il un long chemin induit ? En utilisant des graphes ordonnés, nous caractérisons ces conditions. La dernière partie du manuscrit aborde les classes définies par leurs tailles, telles que celles contenant au plus un nombre factoriel de graphes. Cette définition présente un comportement inhabituel car elle n'est pas stable par union, mais elle regroupe un large éventail de classes de graphes connues. Un article de Hatami et Hatami établit des bornes inférieures sur les Adjacency labeling schemes (ALS) des classes factorielles. Ici, nous nous concentrons sur un sous-ensemble des classes factorielles, connues sous le nom de petites classes, sur lesquelles nous décrivons avec précision la taille des ALS.
Gratuit
Disciplines