Back to Search
Start Over
Exact algorithms for Kayles.
- Source :
-
Theoretical Computer Science . Jan2015, Vol. 562, p165-176. 12p. - Publication Year :
- 2015
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*GAME theory
*GRAPH theory
*SET theory
*MATHEMATICAL bounds
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 562
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 99791922
- Full Text :
- https://doi.org/10.1016/j.tcs.2014.09.042