La soutenance sera accessible en visioconférence par Zoom:
https://grenoble-inp.zoom.us/j/93009629419
ID de réunion: 930 0962 9419
Code secret: 990568
Cette thèse sera soutenue publiquement devant le jury composé de:
- Bertrand GUENIN - Rapporteur - University of Waterloo
- Chien-Chung HUANG - Rapporteur - CNRS Délégation Centre
- Nadia BRAUNER - Examinatrice - Université Grenoble Alpes
- Victor CHEPOI - Examinateur - Aix-Marseille Université
- Annegret WAGLER - Examinatrice - Université Clermont Auvergne
- Zoltán SZIGETI - Directeur de thèse - Grenoble-INP, Ensimag
- Moritz MÜHLENTHALER - Co-encadrant de thèse - Grenoble-INP, Ensimag
Résumé:
Cette thèse étudie différents problèmes d’empaquetages et de recouvrements en théorie des graphes et donne des algorithmes pour les résoudre. Nous regardons d’abord les empaquetages d’arborescences, un domaine d’étude initié par Edmonds en 1960 qui cherche à empaqueter le plus d’arborescences arc-disjointes possibles dans un graphe orienté D. On se concentre sur des variations d’empaquetages d’arborescences avec des contraintes matroïdales, tels que les empaquetages matroid-reachability-based d’arborescences, où chaque sommet v de D doit être contenu dans des arborescences telles que leurs racines forment une base d’un matroide M donné, restreint sur les prédécesseurs dans D du sommet v. Alors qu’une caractérisation des graphes orientés admettant un tel empaquetage a été donnée par Cs. Király en 2016 et Gao, Yang en 2021, la question de limiter le nombre de racines dans un tel empaquetage est restée non répondue. Nous répondons à cette question et donnons un algorithme permettant de trouver un empaquetage avec un nombre de racines limité, puis nous montrons comment notre résultat se connecte à la théorie des empaquetages d’arborescences. Nous nous tournons ensuite vers la reconfiguration, une catégorie de problèmes
qui demande sous quelles conditions et comment peut-on transformer une configuration d’un problème donné en une autre configuration. Des exemples classiques de questions de reconfiguration sur les graphes sont la recoloration des graphes, la reconfiguration des sous-graphes, la réorientation et la reconfiguration des ensembles indépendants. Notre travail se concentre sur ces deux dernières questions. En raffinant les résultats récents de Ito et al. sur la réorientation des graphes, nous donnons un nouvel algorithme combinatoire pour calculer des orientations d’hypergraphes à haute connexité et donnons de nouvelles propriétés du graphe de reconfiguration des orientations des hypergraphes sous contraintes de connexité. Finalement, nous donnons un nouvel algorithme de kernelization pour le problème Token Jumping qui demande s’il est possible de transformer un ensemble indépendant d’un graphe G en un autre de même taille en itérativement enlevant puis ajoutant un sommet à l’ensemble indépendant. Notre technique s’appuie sur des arguments topologiques simples et peut être appliquée sans aucune information supplémentaire sur le graphe G.
La soutenance se fera en anglais.
Algorithms for packing and covering problems
It will take place on Wednesday December 10th at 15h00, in amphitheater C, Grenoble INP - Génie Industriel, 46 Avenue Félix Viallet, 38000 Grenoble.
The defense will be available remotely by Zoom:
https://grenoble-inp.zoom.us/j/93009629419
Meeting ID: 930 0962 9419
Secret Code: 990568
This thesis will be defended publicly before the following jury members:
- Bertrand GUENIN - Rapporteur - University of Waterloo
- Chien-Chung HUANG - Rapporteur - CNRS Délégation Centre
- Nadia BRAUNER - Examiner - Université Grenoble Alpes
- Victor CHEPOI - Examiner - Aix-Marseille Université
- Annegret WAGLER - Examiner - Université Clermont Auvergne
- Zoltán SZIGETI - Thesis director - Grenoble-INP, Ensimag
- Moritz MÜHLENTHALER - Thesis co-supervisor - Grenoble-INP, Ensimag
Summary:
This thesis studies various problems surrounding packings and coverings in graph theory and gives algorithms to solve them. We first take a look at packings of arborescences, a field of study initiated by Edmonds in 1960 which aims to pack as many arc-disjoint arborescences as possible in a directed graph D. We focus on variants of packings of arborescences with matroidal constraints, matroid-reachability-based packings of arborescences, where each vertex v of D must be contained in arborescences such that their root set forms the basis of a given matroid M restricted to the predecessors in D of the vertex v. While a characterization of digraphs admitting such a packing was given by Cs. Király in 2016 and Gao, Yang in 2021, the question of limiting the number of roots in such a packing remained unanswered. We give an answer and an algorithm to this question and show how our result connects to the broader theory of arborescence packings. We then turn to reconfiguration, a category of problems which asks under
which conditions and how it is possible to transform any configuration of a given problem into any other. Classic examples of reconfiguration problems on graphs include graph recoloring, subgraph reconfiguration, reorientation and independent set reconfiguration. Our work focuses on the latter two problems. By refining the recent results of Ito et al. on the reorientation of graphs, we give a new combinatorial algorithm for computing highly connected orientations of hypergraphs and give new properties of the reconfiguration graph of hypergraph orientations under connectivity constraints. Finally, we give a new kernelization algorithm for the Token Jumping problem which asks whether it is possible to transform an independent set of a graph G into another one of the same size by iteratively removing one vertex and adding back one to that independent set. Our technique uses simple topological arguments and can be applied without any extra information on G.
The defence will be in english.
