On the computational complexity of a game of cops and robbers

DOI10.1016/J.TCS.2012.11.041MaRDI QIDQ1945941zbMATH OpenOpenAlexFDO

Authors Marcello Mamino

Publication date 17 April 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.6043

zbMATH Keywords

computational complexitycops and robberpursuit game

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We study the computational complexity of a perfect-information two-player game proposed by Aigner and Fromme. The game takes place on an undirected graph where n simultaneously moving cops attempt to capture a single robber, all moving at the same speed. The players are allowed to pick their starting positions at the first move. The question of the computational complexity of deciding this game was raised in the '90s by Goldstein and Reingold. We prove that the game is hard for PSPACE.

Recommendations

• The complexity of pursuit on a graph
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• Cops and Robber game without recharging
• Cops and robber game without recharging

Cited in

(15)

• Computability and the game of cops and robbers on graphs
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• Pursuing a fast robber on a graph
• Cops and robber on butterflies, grids, and AT-free graphs
• A cops and robber game and the meeting time of synchronous directed walks
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Fine-grained Lower Bounds on Cops and Robbers
• The complexity of zero-visibility cops and robber
• The complexity of Scotland Yard
• Cops and robbers is EXPTIME-complete
• Bounds on the length of a game of cops and robbers
• The complexity of zero-visibility cops and robber
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• To satisfy impatient web surfers is hard
• The guarding game is E-complete

This page was built for publication: On the computational complexity of a game of cops and robbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945941)