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 AM. (C) 2013 Elsevier B.V. All rights reserved.
Deciding the winner in k rounds for DISJOINT ARROWS, a new combinatorial partizan game / Monti, Angelo. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 513:(2013), pp. 96-108. [10.1016/j.tcs.2013.10.004]
Deciding the winner in k rounds for DISJOINT ARROWS, a new combinatorial partizan game
MONTI, Angelo
2013
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 AM. (C) 2013 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.