Solution Graphs of Combinatorial Problems : Algorithms and Complexity

Graphes solutions de problèmes combinatoires : algorithmes et complexité Cette thèse se concentre sur des objets particuliers en théorie des graphes appelés homomorphismes de graphes. ce sont des applications entre des ensembles de sommets qui préservent l'adjacence. S'ils ne sont pas aussi profondément étudiés que la coloration de graphe (qu'ils généralisent), les homomorphismes de graphes sont un outil classique de la combinatoire, reliant notamment profondément le domaine à l'algèbre. Du point de vue de l'informatique théorique, les problèmes de calcul liés aux homomorphismes de graphes présentent également un intérêt remarquable, car ils définissent une classe de problèmes de satisfaction de contraintes avec une théorie riche et de nombreux exemples pertinents dans la pratique.Cette thèse étudie quelques problèmes liés à la reconfiguration des homomorphismes de graphes. Sans trop formaliser, nous abordons le problème suivant : étant donné deux graphes G, H et deux homomorphismes de graphes de G vers H, est-il possible de transformer un homomorphisme en l'autre en changeant l'image d'un sommet à la fois, en gardant un homomorphisme tout au long du processus. Nous considérons également le problème voisin où nous demandons si de telles transformations existent pour deux homomorphismes quelconques de G vers H. Le cas échéant, on dit que le graphe G est H-mixant.Plus précisément, nous nous intéressons à la complexité combinatoire des deux problèmes ci-dessus, le graphe image H étant fixé comme une structure où les homomorphismes projettent le graphe instance G. En tant que problèmes de décision, la résolution de la première question est appelée "H-recoloration" et la seconde est appelée "H-mixing".Cette thèse affine profondément des outils topologiques introduit par Marcin Wrochna en 2014 pour résoudre la H-recoloration en temps polynomial lorsque H est sans carré. Nous montrons que les mêmes outils fonctionnent dans un cadre beaucoup plus général où G et H peuvent être des graphes dirigés ou être réflexifs (avoir une boucle sur chaque sommet) ou les deux. Nous généralisons ainsi tous les résultats positifs précédemment connus sur le problème, y compris, par exemple, la reconfiguration des homomorphismes vers des cliques circulaires.Nous nous tournons ensuite vers le problème du H-mixing, où nous faisons encore contribuer un peu la machinerie de M. Wrochna. Nous affinons les outils topologiques et une construction de gadget introduits par Hyobeen Kim, Jae-baek Lee et Mark H. Siggers pour montrer des résultats de dureté sur le mélange de H lorsque H est symétrique réflexif. Nous sommes ainsi en mesure de prouver des résultats de dureté dans un cadre beaucoup plus général où G et H peuvent être irréflexifs ou dirigés ou les deux; y compris (à nouveau) le mélange d'homomorphismes vers des cliques circulaires, dont la dureté n'était connue que dans des cas très particuliers.Tous ces résultats étendent considérablement la classe des graphes (et graphes dirigés) H pour lesquels la complexité du H-recoloriage et du H-mixing sont connues ; ils constitueront, nous l'espérons, une étape importante vers une classification complète de la complexité de ces problèmes. L'auteur espère également que ces résultats mettront l'accent sur le caractère prolifique de l'utilisation des méthodes topologiques dans les domaines de la théorie des graphes et de la reconfiguration combinatoire.