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.