Thèse Valentin BARTIER

Auteur : Valentin BARTIER
Directrice de thèse : Myriam PREISSMANN
Co Encadrant : Nicolas BOUSQUET
Date : 29 novembre 2021
 

Un problème de reconfiguration combinatoire consiste à trouver une transformation étape par étape entre deux solutions réalisables d'un problème d'optimisation, appelé problème source, de telle sorte que toutes les solutions intermédiaires soient également réalisables. Chaque étape de la transformation consiste à appliquer une modification atomique sur la solution courante. Une telle modification est appelée opération de reconfiguration.

Le graphe de reconfiguration est le graphe dont les sommets sont les solutions réalisables du problème source, et tel que deux solutions sont adjacentes si et seulement si l'une peut être obtenue à partir de l'autre en appliquant exactement une opération de reconfiguration.

Dans cette thèse, nous étudions deux questions fondamentales en reconfiguration. La première est la question de l’accessibilité : étant donné une solution initiale réalisable, une solution cible réalisable, et une opération de reconfiguration, est-il possible de transformer la solution initiale en la solution cible en appliquant successivement l'opération de reconfiguration donnée, et de telle sorte que chaque solution intermédiaire soit également réalisable ? De manière équivalente, existe-t-il un chemin entre la solution initiale et la solution cible dans le graphe de reconfiguration? On dit qu’une telle transformation est valide.

La deuxième question que nous étudions concerne le diamètre du graphe de reconfiguration : Supposons que le graphe de reconfiguration soit connecté, en d'autres termes qu'il existe une transformation valide entre deux solutions réalisables quelconques du problème source. Quel est le diamètre du graphe de reconfiguration ? De manière équivalente, quel est le nombre maximum d'opérations de reconfiguration à appliquer pour transformer une solution en une autre ?

Dans cette thèse, nous nous concentrons sur les problèmes de reconfiguration sur les graphes. Nous étudions d'abord le problème de recoloration de graphe, dans lequel on considère un graphe et des colorations propres de ce graphe, et où l'opération de reconfiguration consiste à modifier la couleur d'un sommet. Le nombre de couleurs qui peuvent être utilisées dans une transformation est limité. Nous nous concentrons sur la recherche de transformations de taille linéaire en la taille du graphe donné. Nous considérons en particulier les graphes chordaux et les graphes de largeur arborescente deux, et améliorons les meilleures bornes connues sur le nombre de couleurs nécessaires pour obtenir de telles transformations dans ces graphes.

Nous considérons ensuite problème de reconfiguration d'ensembles indépendants. Un ensemble indépendant est vu comme un ensemble de jetons qui sont placés sur les sommets de l’indépendant. Nous considérons deux opérations de reconfiguration. La première est l'opération de « token jumping » : un jeton peut être déplacé n'importe où sur le graphe à chaque étape. La seconde est l'opération de « token sliding »: un jeton ne peut se déplacer que vers un voisin du sommet sur lequel il se trouve. Nous nous concentrons sur la complexité du problème d’accessibilité défini par ces opérations. Nous prouvons d'abord que le problème est PSPACE-complet sur les graphes H-free pour les deux opérations, à moins que H n'appartienne à un ensemble fini de graphes S que nous décrivons, et nous étudions la complexité du problème sur les graphes H-free pour un certain H dans S. Nous étudions ensuite l'impact de l’épaisseur des graphes sur la complexité paramétrée du problème pour les deux opérations, et donnons une limite précise entre tractabilité et intractabilité dans les graphes bipartis et des sous-classes de ces graphes. Nous introduisons ensuite un nouveau modèle que nous appelons « galactic token sliding » que nous utilisons pour montrer que le problème d’accessibilité avec token sliding est FPT paramétré par la taille des ensembles indépendants sur les graphes de degré borné.