Exposé de Nicolas Nisse

mardi 21 janvier 2025
Nicolas Nisse, chercheur dans l'équipe COATI (pôle COMRED), donnera un séminaire intitulé « On some positional games in graphs » le mardi 21 janvier 2025 à 14h00 au Centre Inria d'Université Côte d'Azur dans la salle E006, bâtiment Euler.
Abstract :
Maker-Breaker game is a classical 2-Player game where two players, Alice and Bob (starting with Alice), alternately select vertices of an hypergraph. Alice wins if she eventually manages to select all vertices of some hyper-edge. Bob wins otherwise, I.e., if he manages to select all vertices of a transversal of the hyper-edges. The problem of deciding the outcome of the game (who is the winner) is known to be PSPACE complete [Schaefer 1978] even if the hyper-edges have size 6 [Rahman,Watson 2021] and to be polynomial if hyper-edges have size 3 [Galliot,Gravier,Sivignon 24+]. To better understand this game, particular hypergraph classes (defined from graphs) have been studied. For instance, given a graph, we may consider the hypergraph with same vertex set and hyper-edges are the closed neighbourhoods of each vertex (Maker-Breaker domination game) [Duchêne, Gledel, Parreau,Renault 2020]. In this talk, we aim at giving a (far to be exhaustive) overview of these games (and their numerous variants). As examples, we will focus on the Largest Connected Subgraph game (where, given a graph , Alice aims at selecting the vertices of inducing a connected subgraph as large as possible) and on the -game (where players select edges instead of vertices and, given a graph , Alice aims at selecting edges of inducing a copy of a fixed graph ). We will describe some complexity results in various graph classes and we will mainly focus on open problems.