Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.05024 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914023989051392 |
|---|---|
| author | Potapov, Igor Prokopenko, Tymofii Sylvester, John |
| author_facet | Potapov, Igor Prokopenko, Tymofii Sylvester, John |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05024 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Capturing an Invisible Robber using Separators Potapov, Igor Prokopenko, Tymofii Sylvester, John Discrete Mathematics Data Structures and Algorithms Combinatorics 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. |
| title | Capturing an Invisible Robber using Separators |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2509.05024 |