Auteur : Florian HORSCH
Directeur de thèse : Zoltan SZIGETI
Date : 27 septembre 2021
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.
Directeur de thèse : Zoltan SZIGETI
Date : 27 septembre 2021
Problèmes de connexité en théorie de graphes: structures, algorithmes et complexité
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é.
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é.