Search
Abstract
The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”, generalizing a well-known game of Cops and Robber which has robber speed 1. We answer their open question about the computational complexity of the game on interval graphs with ∞-fast robber, showing it to be polynomially decidable. We also generalize the concept of k-defensive domination introduced by Farley and Proskurowski in “Defensive Domination” to A--defensive domination and use it as a main tool in our proof. The generalization allows specifying arbitrary attacks and limiting the number of defenders of each vertex. While this problem is NP-complete even for split graphs, we show that A-defensive domination is decidable in polynomial time on interval graphs.
Citations
-
5
CrossRef
-
0
Web of Science
-
5
Scopus
Authors (3)
-
Tomáš Gavenčiak
- Charles University Department of Applied Mathematics
-
Jan Kratochvíl
- Charles University Department of Applied Mathematics
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2018.09.031
- License
- Copyright (2018 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 794,
pages 47 - 58,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Dereniowski D., Gavenčiak T., Kratochvíl J.: Cops, a fast robber and defensive domination on interval graphs// THEORETICAL COMPUTER SCIENCE -Vol. 794, (2019), s.47-58
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2018.09.031
- Verified by:
- Gdańsk University of Technology
seen 102 times
Recommended for you
The complexity of zero-visibility cops and robber
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 authors
The Complexity of Zero-Visibility Cops and Robber
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 authors
Zero-Visibility Cops and Robber Game on a Graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 authors
Zero-visibility cops and robber and the pathwidth of a graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 authors