Abstract
The game of Cops and oo-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 oo-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.