zbMATH — the first resource for mathematics

The cop number of the one-cop-moves game on planar graphs. (English) Zbl 06852645
Gao, Xiaofeng (ed.) et al., Combinatorial optimization and applications. 11th international conference, COCOA 2017, Shanghai, China, December 16–18, 2017. Proceedings. Part II. Cham: Springer (ISBN 978-3-319-71146-1/pbk; 978-3-319-71147-8/ebook). Lecture Notes in Computer Science 10628, 199-213 (2017).
Summary: Cops and robbers is a vertex-pursuit game played on graphs. In the classical cops-and-robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Frommer established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops-and-robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy-cops-and-robbers game, where at most one cop can move during any round. We show that Aigner and Frommer’s result does not generalise to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game. This answers a question recently raised by Sullivan, Townsend and Werzanski.
For the entire collection see [Zbl 1378.68013].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI