Keeping your distance is hard

02/19/2016 - 13:30
02/19/2016 - 14:30
Sylvie Heubach, California State University
201, av. du Président-Kennedy, LOCAL PK-4323, Montréal (Qc) H2X 3Y7

 We will look at the computational complexity of deciding who wins from a given position in specific two-player games. The players alternately color the vertices of a given graph with red or blue, subject to distance conditions. One example is the game of COL, where adjacent vertices cannot be colored with the same color. In general graph distance games, two sets describe at which distances like or different colors are not allowed.

Using the fact that some members of this family, namely COL, SNORT, and NODEKAYLES, are PSPACE-hard, we can show that a large number of graph distance games are also PSPACE-hard. The proof uses the insertion of a subgraph that creates a bijection between the positions of a game with known computational complexity and a game whose complexity is to be determined. This talk does not require prior knowledge of combinatorial games or computational complexity. Come prepared to play! (Joint work with Kyle Burke, Melissa Huggan, and Svenja Huntemann.)

Last edited by on Fri, 02/12/2016 - 14:44