The Game of Cops and Eternal Robbers

DOI10.1016/J.TCS.2021.05.014zbMATH Open1507.91027arXiv2003.03791MaRDI QIDQ6336347

Anthony Bonato, Fionn Mc Inerney, Trent G. Marbach, Melissa Huggan

Publication date: 8 March 2020

Abstract: We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer

t

is fixed, and the cops are required to capture the robber in at most

t

time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by

c_{t}^{i n f t y},

which equals the eternal domination number in the case

t = 1,

and the cop number for sufficiently large

t .

We study the complexity of Cops and Eternal Robbers, and show that game is NP-hard when

t

is a fixed constant and EXPTIME-complete for large values of

t

. We determine precise values of

c_{t}^{i n f t y}

for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids.

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Positional games (pursuit and evasion, etc.) (91A24)

This page was built for publication: The Game of Cops and Eternal Robbers