Abstract: The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of Robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent Robber from entering the guarded region. Fomin et al. [Fomin, Golovach, Hall, Mihalak, Vicari, Widmayer: How to Guard a Graph? Algorithmica 61(4), 839--856 (2011)] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs.
Recommendations
- Foolproof eternal domination in the all-guards move model
- Guard games on graphs: keep the intruder out!
- Guard games on graphs: keep the intruder out!
- scientific article; zbMATH DE number 508925
- Guarded subgraphs and the domination game
- scientific article; zbMATH DE number 1678371
- Guarding polyominoes
- Logic games are complete for game logics
- An evasion game on a graph
- Complexity of the cop and robber guarding game
Cites work
- scientific article; zbMATH DE number 5575574 (Why is no real title available?)
- scientific article; zbMATH DE number 2174620 (Why is no real title available?)
- scientific article; zbMATH DE number 2104838 (Why is no real title available?)
- A game of cops and robbers
- An annotated bibliography on guaranteed graph searching
- Comparing complexity classes
- Complexity of eternal security
- Complexity of the cop and robber guarding game
- Cop-robber guarding game with cycle robber-region
- Cops and robbers is EXPTIME-complete
- Eternal security in graphs of fixed independence number
- Eternally secure sets, independence sets and cliques
- Guard games on graphs: keep the intruder out!
- How to guard a graph?
- Maximum-demand graphs for eternal security
- On the computational complexity of a game of cops and robbers
- Provably Difficult Combinatorial Games
- Pursuing a fast robber on a graph
- Searching and sweeping graphs: a brief survey
- Some results about pursuit games on metric spaces obtained through graph theory techniques
- The complexity of pursuit on a graph
- The game of cops and robbers on graphs
- The guarding problem -- complexity and approximation
- Tight bounds for eternal dominating sets in graphs
- Vertex-to-vertex pursuit in a graph
Cited in
(7)- How to guard a graph?
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Spy-game on graphs: complexity and simple topologies
- The guarding problem -- complexity and approximation
- Complexity of the cop and robber guarding game
- Guarding a subgraph as a tool in pursuit-evasion games
This page was built for publication: The guarding game is E-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q389949)
