On the computational complexity of a game of cops and robbers

DOI10.1016/J.TCS.2012.11.041zbMATH Open1290.68050arXiv1202.6043OpenAlexW1978284948MaRDI QIDQ1945941FDOQ1945941

Authors: Marcello Mamino 

Publication date: 17 April 2013

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

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.

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

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

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)

Cited In (15)

• Computability and the game of cops and robbers on graphs
• Title not available (Why is that?)
• 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
• Fine-grained Lower Bounds on Cops and Robbers
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• The complexity of Scotland Yard
• The complexity of zero-visibility cops and robber
• 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)