Cops and robbers is EXPTIME-complete

DOI10.1016/j.jctb.2014.11.002zbMath1307.05155arXiv1309.5405OpenAlexW2072757898MaRDI QIDQ2259861

William B. Kinnersley

Publication date: 5 March 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

cops and robbersvertex-pursuit gamesmoving target searchEXPTIME-complete

Mathematics Subject Classification ID

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

Related Items (32)

General cops and robbers games with randomness ⋮ Cops and robber on butterflies and solid grids ⋮ Unnamed Item ⋮ The lion and man game on polyhedral surfaces with obstacles ⋮ Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond ⋮ Cops and robbers on intersection graphs ⋮ A simple method for proving lower bounds in the zero-visibility cops and robber game ⋮ A faster algorithm for cops and robbers ⋮ An Introduction to Lazy Cops and Robbers on Graphs ⋮ The guarding game is E-complete ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ The complexity of zero-visibility cops and robber ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ Cops and robber on butterflies, grids, and AT-free graphs ⋮ Cops that surround a robber ⋮ The one-cop-moves game on graphs with some special structures ⋮ Zombie number of the Cartesian product of graphs ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Cops and robber on some families of oriented graphs ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Spy-game on graphs: complexity and simple topologies ⋮ The game of Cops and Robber on circulant graphs ⋮ Bounds on the length of a game of cops and robbers ⋮ The game of cops and eternal robbers ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Variations of cops and robbers game on grids ⋮ Unnamed Item ⋮ Hyperopic cops and robbers ⋮ Conjectures on Cops and Robbers ⋮ Approximate capture in Gromov-Hausdorff close spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations of \(k\)-copwin graphs
• The complexity of pursuit on a graph
• A game of cops and robbers
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• On the computational complexity of a game of cops and robbers
• Pursuing a fast robber on a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Cops and Robber with Constraints
• Provably Difficult Combinatorial Games
• Pursuit and evasion from a distance: algorithms and bounds

This page was built for publication: Cops and robbers is EXPTIME-complete