Metraipolis › archive › dc_0fc305cdd135
Blindfolded pursuit with delays of your choice — arXiv:2608.27347
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.27347
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T15:34:32.856Z
- SHA-256 of the archived text
25db8eb9e85836b262631c61f3122ea660694b9be11ada8ec5980b823beee1e7- Stable URL of this page
https://metraipolis.com/documento/dc_0fc305cdd135
How to cite
Blindfolded pursuit with delays of your choice — arXiv:2608.27347 — arXiv (en), https://arxiv.org/abs/2608.27347 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0fc305cdd135 (Metraipolis archive dc_0fc305cdd135, sha256 25db8eb9e85836b262631c61f3122ea660694b9be11ada8ec5980b823beee1e7)
BibTeX
@misc{dc0fc305cdd135,
title = {Blindfolded pursuit with delays of your choice — arXiv:2608.27347},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.27347},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0fc305cdd135; sha256 25db8eb9e85836b262631c61f3122ea660694b9be11ada8ec5980b823beee1e7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27347. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study pursuit-evasion games on graphs with a single pursuer and an invisible evader. The pursuer may assign integer travel times to the edges of the graph and specify a finite sequence of vertices to query, one per time step. The evader then chooses a walk over the same time horizon, aiming to elude all queries. With unit travel times, the setting in which the evader must move at every time step is known as the hunter and rabbit game, while the variant in which the evader can wait at a vertex can be phrased as a firefighting game: the vertices of a burning graph must be extinguished, and any vertex left burning reignites its neighbors. For both settings, we show that the power to choose travel times allows a single pursuer to succeed in polynomial time on any graph. This contrasts with unweighted graphs, where the number of hunters or firefighters needed can grow linearly in the number of vertices. If the evader, in addition to waiting, may start at an earlier time unknown to the pursuer, we show that the pursuer still wins on any graph given exponential time. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-28 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2608.27347 — 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-17T15:27:43.273Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).