Pursuing a fast robber on a graph
Fomin
F
V
author
Golovach
P
A
author
Kratochvil
J
author
Nisse
N
author
Suchan
K
author
2010
English
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 we prove 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. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved.
Pursuit-evasion game on graphs
Cops and Robbers
Complexity
Parameterized complexity
Cliquewidth
Planar graph
WOS:000274886700020
exported from refbase (show.php?record=83), last updated on Thu, 01 Apr 2010 02:24:15 -0300
text
files/83_Fomin_etal2010.pdf
10.1016/j.tcs.2009.12.010
Fomin_etal2010
Theoretical Computer Science
Theor. Comput. Sci.
2010
Elsevier Science Bv
continuing
periodical
academic journal
411
7-9
1167
1181
0304-3975