Une marche à travers les graphes de reconfiguration

A walk through reconfiguration graphs Cette thèse explore la structure des espaces de solutions à travers la reconfiguration combinatoire. Contrairement à l'approche classique, qui s'intéresse à l'existence ou l'optimisation d'une solution pour un problème donné, la reconfiguration étudie l'espace global formé par l'ensemble des solutions admissibles, appelées configurations. Ces solutions sont reliées entre elles par une règle de transition correspondant à une modification locale élémentaire, ce qui permet de modéliser cet espace sous la forme d'un graphe de reconfiguration. Un problème central consiste alors à déterminer s’il est possible de transformer une configuration en une autre en suivant ces transitions, tout en restant dans l’ensemble des solutions admissibles ; c'est-à-dire trouver un chemin entre ces deux configurations dans le graphe de reconfiguration. Dans cette thèse, nous nous intéressons particulièrement à des problèmes de reconfiguration en théorie des graphes. La première partie est dédiée à la reconfiguration des colorations de graphes. Nous étudions plusieurs règles de transition, en particulier la recoloration sommet par sommet et les changements de Kempe. Motivés par des questions de génération aléatoire de colorations propres, nous analysons d'abord un algorithme probabiliste basé sur une méthode de hill-climbing utilisant la recoloration sommet par sommet.Nous prouvons la terminaison de cet algorithme sur les colorations d'arêtes. Toujours en recoloration sommet par sommet, nous étudions ensuite le diamètre du graphe de reconfiguration des colorations propres de listes, lorsque sa connexité est assurée. Enfin, sous la règle des changements de Kempe, nous explorons le nombre de couleurs nécessaires pour assurer la connexité du graphe de reconfiguration. La deuxième partie porte sur la reconfiguration d'ensembles indépendants, où l'on cherche à transformer un ensemble indépendant en un autre en changeant un sommet à chaque étape. En général, ce problème est PSPACE-complet, même sur des classes de graphes très restreintes. Cependant, lorsqu'il est paramétré par la taille de l'ensemble indépendant, il devient FPT sur des classes de graphes creux, et en particulier pour les graphes de largeur arborescente bornée. Notre contribution principale est de montrer que, dans cette classe, le problème admet un noyau de taille linéaire. En d'autres termes, il est possible de réduire toute instance du problème à une instance équivalente dont la taille est directement proportionnelle à celle des ensembles indépendants. Enfin, la dernière partie aborde un problème de nature plus géométrique : la reconfiguration d'arbres plans (sans croisement) couvrant un ensemble de points en position convexe. Il est connu que tout arbre plan peut être transformé en un autre au moyen de changements d'arêtes (flips), mais le nombre exact de flips nécessaires reste difficile à déterminer. Étant donnés deux tels arbres, nous établissons des bornes inférieures et supérieures sur le nombre d'étapes requises pour passer de l'un à l'autre.