Exact algorithms for Kayles

Hans L. Bodlaender, Dieter Kratsch, Sjoerd T. Timmer

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    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 ⊆ V is a K-set in a graph G = ( V , E ) , if G [ W ] is connected and there exists an independent set X such that 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.6052^n). A computer-generated case analysis improves this bound to O(1.6031^n) K-sets, and thus we have an upper bound of O(1.6031^n) 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 ⋅ 3 n / 3 and thus Kayles can be solved on trees in O(1.4423^n) 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 G_avoid ( POS DNF 2 ) and G_seek ( POSDNF_3 ) can also be determined in O(1.6031^n) time. In G_avoid(POSDNF_2) , 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 G_seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game.
    Original languageEnglish
    Pages (from-to)165-176
    Number of pages12
    JournalTheoretical Computer Science
    Volume562
    DOIs
    Publication statusPublished - 11 Jan 2015

    Keywords

    • Graph algorithms
    • Exact algorithms
    • Combinatorial games
    • Analysis of algorithms
    • Moderately exponential time algorithms
    • Kayles
    • Independent sets

    Fingerprint

    Dive into the research topics of 'Exact algorithms for Kayles'. Together they form a unique fingerprint.

    Cite this