Complexity of Maker-Breaker Games on Edge Sets of Graphs

Eric Duchêne, Valentin Gledel, Fionn Mc Inerney +4

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the $H$-game. Maker wins if s…