Finding a winning strategy in variations of Kayles

Abstract

Kayles is a two player game played on a graph. The game can be defined as follows: both players take turns picking a node from a graph G. They remove that node and all its neighbors. When there are no more nodes left, the player whose turn it is loses. An alternate but equivalent way of phrasing it is to say that both players take turns picking an unmarked node from graph G and marking it and its neighbors. When all nodes are marked, the player whose turn it is loses. In this paper a variation of the game Kayles is studied, where instead of removing or marking just the neighbors of the chosen node, the players remove or mark the nodes at a certain distance d. Note that in this variation there is a difference between marking and removing a node. When the players remove nodes, the distance between other nodes can change, but when the players mark nodes the distances stay the same. This paper proves that Kayles with marking is PSPACE complete and that Kayles with removing is PSPACE complete for distance two. Furthermore an exact algorithm for finding a winning strategy for Kayles with marking is given for distance two. It is also shown that both versions of Kayles can be solved in polynomial time on certain classes of graphs.