Eliminating more than vertices in graphs
Time: 14:00 -- Location: LRI, 445
summary: Considérons le jeu suivant sur un graphe. À chaque tour, le joueur peut enlever un sommet de
chaque composante connexe du graphe courant. Le but du jeu est d’éliminer tous les sommets du graphe.
Le nombre minimum de tours nécessaires est appelé la treedepth du graphe. C’est un paramètre structurel
bien étudié et souvent utilisé dans des problèmes algorithmiques. Dans ce séminaire, nous allons introduire
un nouveau paramètre appelé la elimination depth, une généralisation de la treedepth. Au lieu d’éliminer
un sommet par composante connexe, nous autorisons l’élimination de sous-graphes connexes plus complexes.
Nous étudions les valeurs extrémales de la elimination depth en fonction de deux classes de graphes :
les graphes que nous cherchons à éliminer et les sous-graphes connexes que nous pouvons enlever. Nous soulignons
un résultat surprenant pour les classes de graphes à éliminer pour de nombreuses classes connues : s’il existe
un graphe que nous ne pouvons pas éliminer en un tour, alors il en existe que nous ne pouvons pas éliminer en
moins qu’un nombre logarithmique (en la taille du graphe) de tours. Nous montrons aussi que cette borne inférieure
peut être atteinte dans plusieurs cas, par exemple quand nous éliminons des cycles dans les graphes planaires.