Generalized Chat Noir is PSPACE-Complete

Chuzo IWAMOTO  Yuta MUKAI  Yuichi SUMIDA  Kenichi MORITA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.502-505
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.502
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 —)
Category: 
Keyword: 
PSPACE-complete,  computational complexity,  two-player game,  Chat Noir,  

Full Text: PDF(244KB)>>
Buy this Article




Summary: 
We study the computational complexity of the following two-player game. The instance is a graph G = (V,E), an initial vertex sV, and a target set TV. 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.