Patrolling cop vs omniscient robber

Nina Chiarelli, Paul Dorbec, Miloš Stojaković, Andrej Taranenko · 2026

Read Patrolling cop vs omniscient robber by Nina Chiarelli, Paul Dorbec, Miloš Stojaković, Andrej Taranenko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08052.txt.

Description

Chiarelli and colleagues study a variant of Cops and Robbers with one cop and one robber, where the cop follows a fixed patrol walk chosen before play begins. The robber is omniscient and knows the patrol in advance, and capture happens when the robber comes within a set distance of the cop. They define the patrol capture radius as the smallest radius that lets the cop always capture the robber on a connected graph under optimal play. The work opens a systematic study of this parameter across several graph classes.

Catalog record

CREATORNina Chiarelli, Paul Dorbec, Miloš Stojaković, Andrej Taranenko
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33729
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.08052

Browse the full library · About the Tower of Babel