Du

Shedule -

Séminaire Philippe Flajolet

Aline Parreau: Complexité algorithmique du jeu de domination Maker-Breaker sur les graphes

IHP

Dans cet exposé, nous expliquerons à travers l'exemple du jeu de domination Maker-Breaker dans les graphes comment être sûr de pouvoir construire une structure donnée face à un adversaire malveillant. Dans le jeu de domination dans les graphes, à chaque tour, Dominator choisit un sommet du graphe puis Staller lui interdit un sommet. A la fin, Dominator gagne si elle a obtenu un ensemble dominant avec ses sommets: c'est-à-dire si chaque sommet du graphe est à distance au plus 1 d'un sommet de Dominator.

Alors que les problèmes classiques de graphes sont très souvent dans la classe NP, savoir si Dominator peut gagner à tous les coups est un problème PSPACE-complet. Cela est en particulier dû au fait que décrire une stratégie pour l'un des joueurs ne peut se faire en temps polynomial en général. Nous verrons dans cet exposé des stratégies structurelles pour Dominator qui sont suffisantes pour certaines classes de graphes comme les graphes d'intervalles, les graphes planaires extérieures ou les graphes réguliers. Cela permet en particulier d'améliorer la complexité du problème dans ces classes de graphes : ainsi les graphes réguliers peuvent toujours être dominés par Dominator, déterminer qui gagne pour un graphe planaire extérieur est polynomial. Pour les graphes d'intervalles, nous obtenons que ce problème est dans NP en le ramenant à la recherche d'une structure particulière dans le graphe mais ne savons pas si cette recherche peut se faire en temps polynomial...