Exact algorithms for Kayles

In the game of Kayles, two players select alternatingly a vertex from a given graph G , but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W¿VW¿V is a K-set in a graph G=(V,E)G=(V,E), if G[W]G[W] is connected and there exists an independent set X such that W=V-N[X]W=V-N[X]. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G . We prove that the number of K-sets in a graph with n vertices is bounded by O(1.6052n)O(1.6052n). A computer-generated case analysis improves this bound to O(1.6031n)O(1.6031n) K-sets, and thus we have an upper bound of O(1.6031n)O(1.6031n) on the running time of the algorithm for Kayles. We also show that the number of K-sets in a tree is bounded by n·3n/3n·3n/3 and thus Kayles can be solved on trees in O(1.4423n)O(1.4423n) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games Gavoid(POSDNF2)Gavoid(POSDNF2) and Gseek(POSDNF3)Gseek(POSDNF3) can also be determined in O(1.6031n)O(1.6031n) time. In Gavoid(POSDNF2)Gavoid(POSDNF2), we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game Gseek(POSDNF3)Gseek(POSDNF3) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. Keywords: Graph algorithms; Exact algorithms; Combinatorial games; Analysis of algorithms; Moderately exponential time algorithms; Kayles; Independent sets