Generalized Chat Noir is PSPACE-Complete

Chuzo IWAMOTO; Yuta MUKAI; Yuichi SUMIDA; Kenichi MORITA

doi:10.1587/transinf.E96.D.502

Generalized Chat Noir is PSPACE-Complete

Chuzo IWAMOTO, Yuta MUKAI, Yuichi SUMIDA, Kenichi MORITA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.502-505

Publication Date: 2013/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.502

Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)

Category

Cite this

Copy

Chuzo IWAMOTO, Yuta MUKAI, Yuichi SUMIDA, Kenichi MORITA, "Generalized Chat Noir is PSPACE-Complete" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 3, pp. 502-505, March 2013, doi: 10.1587/transinf.E96.D.502.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.502/_p

Copy

@ARTICLE{e96-d_3_502,
author={Chuzo IWAMOTO, Yuta MUKAI, Yuichi SUMIDA, Kenichi MORITA, },
journal={IEICE TRANSACTIONS on Information},
title={Generalized Chat Noir is PSPACE-Complete},
year={2013},
volume={E96-D},
number={3},
pages={502-505},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.502},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Generalized Chat Noir is PSPACE-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 502
EP - 505
AU - Chuzo IWAMOTO
AU - Yuta MUKAI
AU - Yuichi SUMIDA
AU - Kenichi MORITA
PY - 2013
DO - 10.1587/transinf.E96.D.502
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
AB - 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.
ER -