Thèse de Nacim Oijid


Sujet :
Complexité des jeux positionnels sur les graphes

Date de soutenance : 08/07/2024

Encadrant : Eric Duchene
Co-encadrant : Aline Parreau

Résumé :

Cette thèse de doctorat traite de la complexité des jeux positionnels, c'est-à-dire des jeux dans lesquels deux joueurs prennent à tour de rôle les sommets libres d'un hypergraphe. Dans la convention la plus célèbre, Maker-Breaker, Maker gagne s'il parvient à prendre tous les sommets d'une hyperarête, sinon Breaker gagne. Dans ces jeux, il existe toujours un joueur qui a une stratégie gagnante, et nous étudions ici la complexité algorithmique de déterminer de quel joueur il s'agit, dans différentes conventions et sur différentes structures, ainsi que le calcul de cette stratégie.

Ce modèle de jeu est très général, et dans les études les plus récentes, l'hypergraphe est une structure sous-jacente du jeu, qui se joue en réalité sur un graphe. Dans ce contexte, les joueurs prennent à tour de rôle des arêtes du graphe et Maker gagne s'il parvient à créer une certaine structure dans le graphe, telle qu'une copie d'un autre graphe cible ou un couplage parfait. Cette thèse se concentre sur la complexité algorithmique de différents jeux positionnels dans différentes conventions.

Parmi les résultats les plus importants de cette thèse, nous pouvons citer la PSPACE-difficulté des jeux Avoider-Enforcer, différents résultats de complexité paramétrés sur le jeu de domination dans la convention Maker-Breaker et l'étude de la complexité du $H$-game et du jeu du perfect matching.


Jury :
M. LAMPIS MichaelMaître de conférenceUniversité Paris Dauphine UMR 7243 - LAMSADERapporteur(e)
M. TODINCA IoanProfesseur(e)Université d’Orléans UR 4022 - LIFORapporteur(e)
M. DEMAINE ErikProfesseur(e)Université de Massachusetts Cambridge (Etats Unis)Examinateur​(trice)
DUCHENE EricProfesseur(e)Université Lyon 1 UMR 5205 - LIRISDirecteur(trice) de thèse
Mme. GUERIN LASSOUS IsabelleProfesseur(e)Université Lyon 1 UMR 5668 - LIPExaminateur​(trice)
Mme. PARREAU AlineChargé(e) de RechercheCNRS Lyon UMR 5205 - LIRISEncadrant(e)