Capturing an Invisible Robber Using Separators

Potapov, Igor ORCID: 0000-0002-7192-7853, Prokopenko, Tymofii ORCID: 0009-0002-1922-7718 and Sylvester, John ORCID: 0000-0002-6543-2934 (2026) Capturing an Invisible Robber Using Separators In: International Symposium on Algorithmics of Wireless Networks (ALGOWIN 2025).

Text ALGOWIN.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (674kB) | Preview

Abstract

We study the zero-visibility cops and robbers game, where the robber is invisible to the cops until they are caught. This differs from the classic game where full information about the robber’s location is known at any time. A previously known solution for capturing a robber in the zero-visibility case is based on the pathwidth decomposition. We provide an alternative solution based on a separation hierarchy, improving capture time and space complexity without asymptotically increasing the zero-visibility cop number in most cases. In addition, we provide a better bound on the approximate zero-visibility cop number for various classes of graphs, where approximate refers to the restriction to polynomial time computable strategies.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences
Divisions:	Faculty of Science & Engineering
Depositing User:	Symplectic Admin
Date Deposited:	08 Sep 2025 08:15
Last Modified:	08 Jan 2026 20:25
DOI:	10.1007/978-3-032-09120-8_13
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3194302
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.