Inria d’université Côte d’Azur, France.
Title: On some positional games in graphs
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 $G$, Alice aims at selecting the vertices of $G$ inducing a connected subgraph as large as possible) and on the $H$-game (where players select edges instead of vertices and, given a graph $G$, Alice aims at selecting edges of $G$ inducing a copy of a fixed graph $H$). We will describe some complexity results in various graph classes and we will mainly focus on open problems.
Short bio: Nicolas NISSE is an Inria research director (DR2) at Inria d’Université Côte d’Azur since 2023, in the project-team COATI. He received his engineer diploma from Supélec, in 2004, his Master (2004) and Ph.D. (2007) degrees from LRI, Univ. Paris-Sud 11. He did a postdoc at DIM, Universidad de Chile (07-08) and then at INRIA (08-09). He was Inria researcher from 2009. He received his Habilitation à Diriger des Recherches (HDR) in 2014, from Univ. Nice Sophia Antipolis.
His research interests include graph theory, algorithms and combinatorial optimization. His work mainly focuses on combinatorial games in graphs (graph searching, cops and robber, etc.). He also works on information spreading problems in telecommunication networks (e.g. routing). His expertise concerns the design of algorithms using structural properties (e.g., graph decompositions) and metric properties of networks.
Nicolas Nisse is co-author of about 60 articles in international revues and more than 50 articles in peer reviewed international conference proceedings. He has participated to the PC of several international and national conferences and organized several of them. He supervised 9 Ph.D. theses (one in progress) and more than 50 internships of bachelor/master students. He participated to several national and international projects and, in particular,, is currently the head of the Inria associated team CANOE (with UFC). Since 2009, N. Nisse teaches (at least 50 hours per year) graph algorithms in master programs. Finally, he his strongly involved in scientific popularization (see Terra Numerica project).
