Paper Info
Title
Deciding the winner in k rounds for DISJOINT ARROWS, a new combinatorial partizan game
Abstract
We consider DISJOINT ARROWS, a new bounded-length two-player partizan combinatorial game. In this game the two players, Alice and Bob, alternate in choosing vertices on a directed graph and no player is allowed to select a vertex previously selected. At each round Alice selects a vertex u and Bob has to reply choosing a new vertex in the out-neighborhood of u. The first player who cannot move loses. We prove that deciding whether Bob can endure k rounds when k is part of the input is a PSPACE-complete problem. Moreover we prove that the parameterized version of the problem is AW[*]-complete. Thus we provide a new member for the small set of problems known complete for the class AW[*].
Year
DOI
Venue
2013
10.1016/j.tcs.2013.10.004
Theor. Comput. Sci.
Keywords
DocType
Volume
k round,new vertex,combinatorial game,new combinatorial partizan game,DISJOINT ARROWS,class AW,vertex u,round Alice,new member,new bounded-length two-player partizan,PSPACE-complete problem
Journal
513,
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
4
1
Name
Order
Citations
PageRank
Angelo Monti167146.93