Problèmes de reconfiguration dans les graphes

Abstract

Dans cette thèse, nous nous intéressons à la théorie des graphes, et plus particulièrement à des problèmes de reconfiguration. Pour un problème d'optimisation donné, l'objectif est alors d'étudier les relations existant entre les différentes solutions. Typiquement, est-il possible de transformer étape par étape une solution en une autre à l'aide d'opérations élémentaires, de telle sorte que chaque étape intermédiaire soit également une solution ?Le problème au départ de cette thèse est celui d'Ensemble Dominant, qui consiste à trouver un sous-ensemble D de sommets tel que chaque sommet est dans D ou adjacent à un sommet de D. Nous étudions la reconfiguration d'ensembles dominants sous deux opérations élémentaires différentes, principalement d'un point de vue algorithmique. Nous donnons également des conditions nécessaires et suffisantes garantissant qu'une transformation est toujours possible entre deux solutions données. Enfin, nous nous intéressons à la complexité paramétrée d'une variante d'optimisation : étant donné un ensemble dominant D, quel est le plus petit ensemble dominant que l'on peut atteindre depuis D sous certaines contraintes ? Nous nous intéressons également à deux autres questions de reconfiguration. Nous étudions d'une part la complexité de la reconfiguration d'arbres couvrant avec une contrainte sur le nombre minimum de feuilles ; d'autre part la recoloration dans le modèle LOCAL, un modèle de calcul distribué. Pour cette dernière question, nous cherchons à optimiser à la fois le nombre de communications et d'étapes permettant de transformer une coloration en une autre.