Patrolling cop vs omniscient robber
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911498759045120 |
|---|---|
| author | Chiarelli, Nina Dorbec, Paul Stojaković, Miloš Taranenko, Andrej |
| author_facet | Chiarelli, Nina Dorbec, Paul Stojaković, Miloš Taranenko, Andrej |
| contents | We study a variant of the classical Cops and Robbers game with one cop and one robber, in which the cop follows a fixed walk on the graph, a patrol, that is chosen before the game begins, while the robber is omniscient, he knows the entire patrol in advance. A capture occurs when the robber comes within a given radius of capture of the cop. This model arises naturally at the intersection of recent work on limited-visibility games and offline versions of pursuit-evasion problems.
By $\tildeρ{(G)}$ we denote the minimum radius of capture that the cop must have to always capture the robber on $G$ in this setting, under optimal play, where $G$ is a connected graph. We initiate a systematic study of this parameter for several graph classes. We determine the exact value of $\tildeρ{(G)}$ for trees, establish upper and lower bounds for grids, and analyze the parameter for various families of chordal graphs, including interval graphs and caterpillars. Along the way, we develop general tools and structural results that may be of independent interest for the study of pursuit-evasion games with predetermined patrols and limited information. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08052 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Patrolling cop vs omniscient robber Chiarelli, Nina Dorbec, Paul Stojaković, Miloš Taranenko, Andrej Combinatorics 05C57, 05C05 We study a variant of the classical Cops and Robbers game with one cop and one robber, in which the cop follows a fixed walk on the graph, a patrol, that is chosen before the game begins, while the robber is omniscient, he knows the entire patrol in advance. A capture occurs when the robber comes within a given radius of capture of the cop. This model arises naturally at the intersection of recent work on limited-visibility games and offline versions of pursuit-evasion problems. By $\tildeρ{(G)}$ we denote the minimum radius of capture that the cop must have to always capture the robber on $G$ in this setting, under optimal play, where $G$ is a connected graph. We initiate a systematic study of this parameter for several graph classes. We determine the exact value of $\tildeρ{(G)}$ for trees, establish upper and lower bounds for grids, and analyze the parameter for various families of chordal graphs, including interval graphs and caterpillars. Along the way, we develop general tools and structural results that may be of independent interest for the study of pursuit-evasion games with predetermined patrols and limited information. |
| title | Patrolling cop vs omniscient robber |
| topic | Combinatorics 05C57, 05C05 |
| url | https://arxiv.org/abs/2603.08052 |