The guarding game is E-complete

DOI10.1016/J.TCS.2013.11.034zbMATH Open1307.91043arXiv1112.6140OpenAlexW2080925544WikidataQ105337610 ScholiaQ105337610MaRDI QIDQ389949FDOQ389949

Authors: Robert Šámal, T. Valla 

Publication date: 22 January 2014

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

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.

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

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

zbMATH Keywords

computational complexitycops-and-robber gamepursuit gameE-completenessgames on propositional formulasgraph guarding game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Vertex-to-vertex pursuit in a graph
• The game of cops and robbers on graphs
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Provably Difficult Combinatorial Games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eternally secure sets, independence sets and cliques
• Title not available (Why is that?)
• Pursuing a fast robber on a graph
• Searching and sweeping graphs: a brief survey
• Comparing complexity classes
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• On the computational complexity of a game of cops and robbers
• Cops and robbers is EXPTIME-complete
• Tight bounds for eternal dominating sets in graphs
• Complexity of the cop and robber guarding game
• The guarding problem -- complexity and approximation
• Eternal security in graphs of fixed independence number
• Maximum-demand graphs for eternal security
• Complexity of eternal security
• Cop-robber guarding game with cycle robber-region
• Guard games on graphs: keep the intruder out!
• How to guard a graph?
• The complexity of pursuit on 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)