Pursuing a fast robber on a graph
From MaRDI portal
Publication:2268876
The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper it is proved that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is \(W[2]\)-hard; the proof extends to the case where the robber moves \(s\) time faster than the cops. It is shown that on split graphs, the problem is polynomially solvable if \(s = 1\) but is NP-hard if \(s = 2\). It is also proved that on graphs of bounded cliquewidth the problem is polynomially solvable for \(s < 3\). Finally, it is shown that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.
Recommendations
Cites work
- A better bound for the cop number of general graphs
- A game of cops and robbers
- A note on \(k\)-cop, \(l\)-robber games on graphs
- A partial k-arboretum of graphs with bounded treewidth
- A short note about pursuit games played on a graph with a given genus
- An annotated bibliography on guaranteed graph searching
- Asteroidal Triple-Free Graphs
- Cops and robbers in graphs with large girth and Cayley graphs
- Fast Robber in Planar Graphs
- Graph Classes: A Survey
- Graph searching and a min-max theorem for tree-width
- Graph searching on some subclasses of chordal graphs
- scientific article; zbMATH DE number 1665333 (Why is no real title available?)
- scientific article; zbMATH DE number 177438 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 887776 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 5241699 (Why is no real title available?)
- scientific article; zbMATH DE number 2187680 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Note on a pursuit game played on graphs
- On a game of policemen and robber
- On a pursuit game on Cayley digraphs
- On a pursuit game on Cayley graphs
- On a pursuit game played on graphs for which a minor is excluded
- On miniaturized problems in parameterized complexity theory
- On the cop number of a graph
- On the pathwidth of chordal graphs
- Searching and sweeping graphs: a brief survey
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Some combinatorial game problems require Ω( n k ) time
- Some results about pursuit games on metric spaces obtained through graph theory techniques
- The complexity of pursuit on a graph
- Vertex-to-vertex pursuit in a graph
- Which problems have strongly exponential complexity?
Cited in
(52)- The lion and man game on polyhedral surfaces with obstacles
- Spy-game on graphs: complexity and simple topologies
- Cops and Robber game with a fast robber on expander graphs and random graphs
- On the computational complexity of a game of cops and robbers
- Study of a combinatorial game in graphs through linear programming
- A faster algorithm for cops and robbers
- Catching an infinitely fast robber on a grid
- Edge degeneracy: algorithmic and structural results
- Cops that surround a robber
- Zombie number of the Cartesian product of graphs
- Cops and robbers is EXPTIME-complete
- Cops, a fast robber and defensive domination on interval graphs
- Catching a fast robber on the grid
- To satisfy impatient web surfers is hard
- Spy game: FPT-algorithm, hardness and graph products
- Spy game: FPT-algorithm and results on graph products
- Cops and robber on subclasses of \(P_5\)-free graphs
- Variations on cops and robbers
- Cops and robber with constraints
- Chasing a fast robber on planar graphs and random graphs
- Catching a fast robber on interval graphs
- scientific article; zbMATH DE number 7232976 (Why is no real title available?)
- A probabilistic version of the game of zombies and survivors on graphs
- Cops and invisible robbers: the cost of drunkenness
- The guarding game is E-complete
- The fast robber on interval and chordal graphs
- Fine-grained Lower Bounds on Cops and Robbers
- Study of a combinatorial game in graphs through linear programming
- Escaping an infinitude of lions
- Lower bounds for the cop number when the robber is fast
- Fast Robber in Planar Graphs
- Conjectures on cops and robbers
- Connected Search for a Lazy Robber
- Variations of cops and robbers game on grids
- Cops and robbers from a distance
- Connected search for a lazy robber
- Primal-dual cops and robber
- Cops and robber on butterflies, grids, and AT-free graphs
- Guard games on graphs: keep the intruder out!
- A cops and robber game and the meeting time of synchronous directed walks
- Cops and robbers on 1-planar graphs
- Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
- The complexity of pursuit on a graph
- Parameterized analysis of the cops and robber problem
- A covering pursuit game
- On the cop number of string graphs
- Cops and robber game without recharging
- COP numbers of periodic graphs
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Linguistic geometry approach for solving the cops and robber problem in grid environments
- General cops and robbers games with randomness
- Cops and robber on butterflies and solid grids
This page was built for publication: Pursuing a fast robber on a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268876)
