Impartial Games on Graphs: Solving Kayles via Dynamic Programming and Periodicity Properties
TL;DR
This work considers combinatorial games in which two players alternately choose vertices from a finite graph until a winning condition is achieved, and focuses on the well-known game Kayles, in which the selected vertices must form an independent set and the player who makes the last valid move wins.
Abstract
In this work, we consider combinatorial games in which two players alternately choose vertices from a finite graph until a winning condition is achieved. Specifically, we focus our investigation on the well-known game Kayles, in which the selected vertices must form an independent set, and the player who makes the last valid move wins (i.e., the player who chooses a vertex that completes a maximal independent set). Zermelo's Theorem guarantees that, in this scenario, one of the players has a winning strategy---that is, a sequence of moves that ensures a win regardless of the opponent's choices. Given a graph, the typical decision problem associated with this type of game consists of determining which player has a winning strategy. Answering this question means solving the game. We first consider Kayles played on caterpillars. Since caterpillars are interval graphs, an O(n3)-time algorithm for solving Kayles on this graph class is already known [Bodlaender and Kratsch, 2002]. However, we investigate scenarios in which this time complexity can be reduced to O(1) by extending the periodicity property presented in [Guignard and Sopena, 2009] to caterpillars. We prove that the nimber of any caterpillar is equal to the nimber of an equivalent reduced caterpillar, obtained by appropriately removing certain leaves from the original graph. By partitioning these reduced caterpillars into classes, we show that a period of 34 emerges in each investigated class, allowing the computation of nimbers to scale to graphs with a large number of vertices. We present a sufficient condition for a class of caterpillars to exhibit periodicity 34, using it to identify many periodic classes and to calculate the nimber of their caterpillars in O(1) time. Furthermore, we present an O(n2)-time dynamic programming algorithm for solving Kayles on powers of paths, improving upon the O(n4)-time complexity given in [Bodlaender and Kratsch, 2002]for graphs with an asteroidal number of at most 2. Finally, we show how this same O(n2)-time algorithm can be adapted to solve Kayles on powers of cycles, thereby reducing the O(n3)-time complexity previously established in [Bodlaender and Kratsch, 2002] for circular-arc graphs.