Metraipolis › archive › dc_96d99dd2f3af
Cops and Lethal Robber on Rings: A Distributed Perspective — arXiv:2609.06388
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06388
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:07:10.916Z
- SHA-256 of the archived text
9ba108278a81ea8640df361afceda4d585fe49f873914d76e01dcc81d458bbce- Stable URL of this page
https://metraipolis.com/documento/dc_96d99dd2f3af
How to cite
Cops and Lethal Robber on Rings: A Distributed Perspective — arXiv:2609.06388 — arXiv (en), https://arxiv.org/abs/2609.06388 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_96d99dd2f3af (Metraipolis archive dc_96d99dd2f3af, sha256 9ba108278a81ea8640df361afceda4d585fe49f873914d76e01dcc81d458bbce)
BibTeX
@misc{dc96d99dd2f3af,
title = {Cops and Lethal Robber on Rings: A Distributed Perspective — arXiv:2609.06388},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06388},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_96d99dd2f3af; sha256 9ba108278a81ea8640df361afceda4d585fe49f873914d76e01dcc81d458bbce},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06388. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Cops and Robber game is extensively studied in the sequential setting where the main goal is to capture the robber. Capturing the robber means at least one cop, and the robber will be at the same vertex together at some time. There are several variants, including variants where the goal of the cops is to surround the robber. Surrounding the robber means there is at least one cop in each of the neighboring vertices of the robber's position. In this paper, we introduce it in the distributed setting while empowering the robber by saying it can even kill cops. Specifically, in our model, the robber moves in odd rounds and has unbounded speed, cops move in even rounds, and if one or more cops move into a vertex where the robber is currently residing, all these cops get killed. We call this {\it lethal robber}. This also connects our work to the Intruder Capture and Black Hole Search problems by introducing an entity which is dynamic as well as lethal, a setting that, to the best of our knowledge, has not been studied. In this work, we introduce the lethal robber, define the {\it cops and lethal robber} problem in the distributed setting and study it on a static ring of size $n$. We prove $n$ cops are not enough, even if all start from the same vertex, and provide an algorithm starting from an arbitrary initial configuration that requires $n+\lfloor\log n \rfloor+4$ cops in the worst case.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2609.06388 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:02:21.557Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).