On the computational complexity of a game of cops and robbers

2012/02/27 by Mamino, Marcello · 1 citation
#68Q17 #91A24 #91A43 #Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1202.6043

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.

Cited by

• Complexity of Firefighting on Graphs

Related

• Cops and Robbers is EXPTIME-complete
• The Cop Number of the One-Cop-Moves Game on Planar Graphs
• Complexity results for a cops and robber game on directed graphs
• The capture time in the game of cops and many robbers
• Simultaneously Moving Cops and Robbers