For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Generalized Chat Noir is PSPACE-Complete
Chuzo IWAMOTO Yuta MUKAI Yuichi SUMIDA Kenichi MORITA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
PSPACE-complete, computational complexity, two-player game, Chat Noir,
Full Text: PDF(244KB)>>
We study the computational complexity of the following two-player game. The instance is a graph G = (V,E), an initial vertex s ∈ V, and a target set T ⊆ V. A “cat” is initially placed on s. Player 1 chooses a vertex in the graph and removes it and its incident edges from the graph. Player 2 moves the cat from the current vertex to one of the adjacent vertices. Players 1 and 2 alternate removing a vertex and moving the cat, respectively. The game continues until either the cat reaches a vertex of T or the cat cannot be moved. Player 1 wins if and only if the cat cannot be moved before it reaches a vertex of T. It is shown that deciding whether player 1 has a forced win on the game on G is PSPACE-complete.