The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] Chat Noir(1hit)

1-1hit
  • Generalized Chat Noir is PSPACE-Complete

    Chuzo IWAMOTO  Yuta MUKAI  Yuichi SUMIDA  Kenichi MORITA  

     
    LETTER

      Vol:
    E96-D No:3
      Page(s):
    502-505

    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.