Subtraction Games on Graphs: Regularity, complexity, algorithms

29th of April 2022, at 11:00 (morning)

Room: Online via Teams

https://teams.microsoft.com/l/meetup-join/19%3adacd63e97f9e48e896f537ace22a27bf%40thread.tacv2/1650924150445?context=%7b%22Tid%22%3a%2281e7c4de-26c9-4531-b076-b70e2d75966e%22%2c%22Oid%22%3a%22c00d08df-c86f-4f81-a9c8-6287a3bb947d%22%7d

Speaker: Antoine Dailly

Title: Subtraction Games on Graphs: Regularity, complexity, algorithms

Abstract:

Octal games are combinatorial games played on heaps of counters: two players alternate removing counters from a heap, and may split it into two nonempty heaps, under conditions expressed in the form of an octal code. The main problem is deciding which player wins (by playing the last legal move) from a heap of a given size. In order to answer to this question, the most used method consists in finding regularities in the sequence of its Grundy values (equivalence classes for games) on heaps of increasing sizes.

We propose a generalization of those games on graphs: the players remove connected subgraphs, and may disconnect the graph, under conditions similar to those of octal games. This definition includes several vertex deletion games, such as Arc-Kayles. We focus our study on subtraction games, a subfamily of octal games where the players cannot disconnect the graph.

In this talk, I will show several results related to subtraction games on graphs. Those results range from general (PSPACE-completeness, ultimate periodicity) to more specific (polynomial-time algorithms for some families of games on specific graph classes). Our study is mostly focused on subdivided stars, which are already difficult to tackle: the classical vertex deletion game Arc-Kayles is open in the family of subdivided stars, even with only three paths with one of length 1! In particular, we determined polynomial-time algorithms which allow to decide the winner of the game 0.33 on subdivided stars and bistars.