Robert Šamal: Complexity of cops and robber game

Robert Šamal (Charles University, Prague): Complexity of cops and robber game.

Povzetek. We study the following game on a graph: cops guard a set Z of vertices, robber wants to intrude. If the robber moves to a vertex in Z (that is currently not occupied by a cop), he wins, if this never happens, cops win.

It was known previously, that deciding who wins is PSPACE-hard, and conjectured it is in fact PSPACE-complete. We show that it is in fact EXPTIME-complete.