Soutenance de thèse de Florian HÖRSCH (OC) le 27 septembre 2021 à 14h00 en amphi C - Site Viallet - Grenoble INP

Les membres du jury :
 

• Monsieur Zoltán SZIGETI PROFESSEUR DES UNIVERSITES, GSCOP, Grenoble, Directeur de thèse
• Monsieur Tibor Jordán PROFESSEUR, Eötvös Loránd University, Rapporteur
• Monsieur Matthias Kriesell PROFESSEUR, Technische Universität Ilmenau, Rapporteur
• Monsieur Frédéric Havet PROFESSEUR, Univ. Nice-Sophia-Antipolis, Examinateur
• Madame Nadia Brauner PROFESSEUR, GSCOP, Grenoble, Examinatrice
• Monsieur Stéphan Thomassé PROFESSEUR, ENS Lyon, Examinateur

Abstract :

This thesis is concerned with 3 classes of problems related to graph connectivity.

Firstly, we deal with graph orientations where an orientation of a graph is obtained by replacing every edge by an arc between the same two vertices. This chapter is divided into two parts: one on orientations for arc-connectivity and one on orientations for vertex-connectivity. For edge-connectivity, we first review some results related to the strong orientation theorem of Nash-Williams and show that it is co-NP-complete to decide whether a given odd-vertex pairing is admissible. This resolves a question of Frank. We next show that it is NP-complete to decide whether a given graph has an orientation satisfying some arbitrary local edge-connectivity condition and give some related problems. We then give some partial results on the problem of determining whether a given graph has a strongly connected orientation such that the in-degree of every vertex is of a prescribed parity. Finally, we wish to give a connectivity property of orientations of 3-edge-connected graphs which is located between strong connectivity and 2-arc-connectivity. This problem has been suggested by Frank and leads to the introduction of a new invariant for 3-edge-connected graphs. We give several bounds for this invariant. For vertex-connectivity, we first give an overview of previous results. We then deal with a problem suggested by Cheriyan, determining some restricted classes of eulerian graphs all of whose eulerian orientations are highly vertex-connected. Next, we deal with arborescence packings. We first provide an inductive method that allows to derive theorems on packings of reachability arborescences from theorems on packings of spanning arborescences in several settings. In particular, we conclude a theorem of Kamiyama, Katoh and Takizawa from a strong form of the theorem of Edmonds. This inductive method also allows to prove a result on matroid-reachability-based packings of mixed hyperarborescences which generalizes numerous previous results. We next use matroid intersection to obtain a theorem on packing mixed hyperarborescences in a setting where the roots of the arborescences are not fixed. Finally, we provide an algorithm certifying that a problem on packing arborescences that have to satisfy a little extra condition is FPT. The same technique allows to find algorithms certifying that two similar problems are FPT. In one case, this resolves a question of Bang-Jensen, Havet and Yeo. In the last part, we deal with connectivity augmentation problems. In particular, relying on some structure provided by Durand de Gevigney and Szigeti, we give a fast algorithm for $(2,k)$-connectivity augmentation.


Résumé :

Cette thèse traite 3 classes de problèmes liés à la connexité des graphes.

En premier lieu, nous traitons des orientations des graphes où une orientation d'un graphe non-orienté est obtenue en remplaçant chaque arête par un arc entre les mêmes deux sommets. Ce chapitre est divisé en deux parties : l'une sur les orientations pour l'arête-connexité et l'autre sur les orientations pour la sommet-connexité. Pour l'arête-connexité, nous présentons certains résultats liés au théorème fort de Nash-Williams sur les orientations et nous démontrons qu'il est co-NP-complet de décider si un "odd-vertex pairing" donné est admissible. Ceci répond à une question posée par Frank. Ensuite, nous prouvons qu'il est NP-complet de décider si un graphe a une orientation satisfaisant des conditions d'arc-connexité locale arbitraires données et nous mentionnons quelques problèmes liés. Ensuite, nous présentons certains résultats partiels sur le problème de décider si un graphe donné a une orientation fortement connexe telle que le degré entrant de chaque sommet a une certaine parité assignée. Finalement, nous souhaitons traiter une propriété de connexité des orientations des graphes 3-arête-connexes qui se situe entre la connexité forte et la 2-arc-connexité. Ce problème a été proposé par Frank et mène à l'introduction d'un nouvel invariant des graphes 3-arête-connexes. Nous démontrons plusieurs bornes pour cet invariant. Pour la sommet-connexité, nous présentons d'abord une collection de résultats antérieurs. Puis, nous traitons un problème proposé par Cheriyan, déterminant quelques classes restreintes de graphes eulériens tel que chacune de leurs orientations eulériennes a une grande sommet-connexité. Le chapitre suivant porte sur les packages d'arborescences. D'abord, nous proposons une méthode récursive qui permet de déduire des théorèmes sur les packages d'arborescences d'accessibilité à partir des théorèmes sur les packages d'arborescences couvrantes dans plusieurs contextes. En particulier, nous déduisons un théorème de Kamiyama, Katoh et Takizawa à partir d'une version forte du théorème d'Edmonds. Cette méthode récursive permet aussi de prouver un résultat sur les packages basés sur la matroïde-accessibilité des hyperarborescences mixtes qui généralise de nombreux résultats précédants. Puis, nous utilisons l'intersection de matroïdes afin d'obtenir un théorème sur les packages d'hyperarborescences mixtes dans un contexte où les racines des arborescences ne sont pas fixées. Finalement, nous construisons un algorithme qui montre qu'un problème sur les packages d'arborescences dans lequel les arborescences doivent satisfaire une petite condition supplémentaire est FPT. La même technique permet de montrer que deux problèmes similaires sont FPT. Dans un cas, cela répond à une question posée par Bang-Jensen, Havet et Yeo. Dans la dernière partie, nous considérons des problèmes d'augmentation de connexité. En particulier, en nous appuyant sur des résultats structurels développés par Durand de Gevigney et Szigeti, nous donnons un algorithme rapide pour l'augmentation pour la $(2,k)$-connexité.