Computer Science – Computer Science and Game Theory
Scientific paper
2011-12-28
Computer Science
Computer Science and Game Theory
Scientific paper
The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against a robber. The 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, the robber on the remaining vertices (the robber-region). The goal of the 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 the robber from entering the guarded region. Fomin et al. [Fomin, Golovach, Hall, Mihalak, Vicari, Widmayer: How to Guard a Graph? Algorithmica, DOI: 10.1007/s00453-009-9382-4] 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 for arbitrary graphs (directed or undirected) the problem is E-complete.
Samal Robert
Valla Tomas
No associations
LandOfFree
On the complexity of the guarding game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the complexity of the guarding game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of the guarding game will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-32595