Source-linked AI summary
Blindfolded pursuit with delays of your choice
Torben Schürenberg, Maximilian J. Stahlberg
TL;DR
The paper asks whether a single pursuer can search arbitrary graphs against an invisible evader without changing graph topology. It assigns integer travel times to edges and schedules vertex queries, proving polynomial-time success when the evader starts at time zero and exponential-time success when waiting and unknown early starts are allowed.
Problem
The paper studies whether one pursuer can search general graphs against an invisible evader without altering graph topology, where unweighted hunter and rabbit settings can require up to n −1 pursuers.
Method
The pursuer assigns integer delays to edges and uses finite vertex-query schedules, with constructions based on pruning short walks, scaled delays, interleaved queries, and recursive long-delay edges.
Results
Every graph is solvable in O(m3) time, waiting-solvable in O(nm3), and waiting-freestart-solvable in O(8n); small complete graphs have shorter waiting-freestart solutions of 4, 14, and 32 steps for n = 2, 3, and 4.
Takeaways & Limitations
Choosing travel times lets a single pursuer succeed on any graph, including evaders that wait or start before the search, though the strongest general guarantee is exponential-time.
Takeaways & Limitations
The free-start results assume the evader can wait, and the paper leaves polynomial-duration solutions without waiting as an open question.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper lets a lone pursuer reshape edge travel times without changing graph topology, and shows that every graph becomes searchable even against increasingly capable evaders. Polynomial durations suffice when the evader starts at time zero, while unknown early starts require exponential time in the general result.
- Classic setting: The classic hunter and rabbit game uses invisible evaders, vertex queries at each time step, and a hunting number that can reach n −1 on general graphs.The complete graph attains this upper scale for the number of pursuers needed.
- Model: The pursuer assigns each edge an integer delay and specifies a partial time-indexed query function, without altering the graph’s topology.Undefined query times are passes, and no query is allowed at time 0.
- Directed warm-up: In directed graphs, distinct delays for antiparallel arcs yield solvability in time n, whereas the same approach fails for undirected graphs because both directions share one delay.Waiting directed graphs are solvable in n2 + n time.
- Main result: Every graph is solvable by one pursuer, including settings where the evader may wait and may start at an unknown time in the past.The paper also presents a single-edge strategy that works across all model variants studied.
- Main result: Graphs of order n and size m are solvable in O(m3) time, waiting-solvable in O(nm3), and waiting-freestart-solvable in O(8n).For trees, the refined waiting-freestart strategy has duration O(4n).
- Strategy construction: The polynomial strategies prune short walks using lexicographically ordered queries and generalized-Sidon delays, while waiting requires scaled delays and interleaved queries that compel movement.The exponential strategies instead recursively add long-delay edges serving as fuses around winning substrategies.
2 Preliminaries
The preliminaries define delayed walks and generalized Bh-sets, which provide the notation and distinct-sum structure used to assign edge delays. They also introduce the lazy-walk model for evaders that may wait.
- Graphs are finite, undirected, and simple, with vertices labeled V = [n], order n, and size m.
- Lazy walks: A lazy walk extends an ordinary walk by allowing waiting times at vertices and an arbitrary start time.
- Generalized Bh-sets: Generalized Br,h-sets require unique sums for bounded-cardinality multisubsets with bounded multiplicity.
- Generalized Bh-sets: B2 0,3-sets are the specific delay-set structure used in this work to distinguish sums involving up to three edges.
- Generalized Bh-sets: For prime-power m, Bose–Chowla provides Bh-sets of size m with max A < mh, supporting small-diameter distinct-sum constructions.
3 A strategy for undirected graphs
The strategy orders the edges, assigns delays from a B2 0,3-set, and queries vertices at carefully selected sums of delays. These queries force every sufficiently long walk to reveal a queried endpoint, yielding a polynomial-duration strategy.
- The proof orders vertices and edges so evasive walks have increasing first vertices and decreasing first edges.This ordering makes the endpoint of a length-three walk with a given edge multiset uniquely identifiable.
- Theorem 3.1 establishes that all graphs are solvable in polynomial time, with the constructed duration bounded by O(m^3).The duration bound follows from max supp(q) ≤ 3 max T and max T ∈ O(m^3).
- The query function covers walks through four cases involving one, two, or three delayed edges and queries the corresponding endpoint vertex.The cases are illustrated by examples in Figure 3.
- B2 0,3-set delays ensure that the sums used by the query function are distinct and its cases are disjoint.The proof also establishes uniqueness of the queried vertex in each case.
- Any walk of length at least three is hit by a query at the endpoint of a suitable length-three prefix.If a walk avoided the earlier queries, the ordering conditions would force the fourth query case to hit its endpoint.
4 Catching a patient evader
The paper handles evaders that may wait by scaling edge delays and expanding the query schedule. This yields a single-pursuer strategy for every graph in polynomial time.
- The construction scales every edge delay by s := n + 1 to create slack for arbitrary waiting times.The modified query function first queries each vertex, then repeats original queries across n-time-step blocks and adds opposite-end queries.
- The auxiliary function r covers the opposite endpoints of walks of length one and two that the original query function q covers.
- Every lazy walk of length at most two with total waiting time at least n is hit by the expanded query schedule.
- Lazy walks of length at least three that avoid those early queries must have less than n waiting time at their first three vertices, after which the construction catches them using q and r.
- The resulting strategy has duration at most 2s max supp(q), yielding the stated polynomial bound.
5 Starting late
The paper extends delay-based pursuit to evaders that may wait and start before the search begins. It obtains an O(8^n) strategy for general graphs and improves this to O(4^n) for trees.
- 5.1 A strategy for general graphs: The general-graph strategy recursively extends a winning strategy on K_{n−1} by adding a universal vertex whose incident edges receive delay 2T.The construction uses a sub-strategy of duration T and produces a schedule of duration 8T.
- 5.1 A strategy for general graphs: Theorem 5.2 shows that every graph is waiting-freestart-solvable in time O(8^n).
- 5.1 A strategy for general graphs: The constructed strategy catches evaders starting at any vertex and at any unknown time before the search begins.
- 5.2 A faster strategy for trees: Consequently, trees are waiting-freestart-solvable in time O(4^n).
- 5.2 A faster strategy for trees: For trees, attaching a pendant vertex to a waiting-freestart-solvable graph with duration T yields a strategy of duration 4T + 2.
6 Discussion
The discussion emphasizes that controllable edge travel times let one pursuer solve every graph, while free-starting waiting evaders remain the main source of exponential duration.
- A single pursuer can control edge travel times and query arbitrary vertices on undirected graphs.
- Polynomial-time strategies suffice when the evader starts at time zero, including when waiting is allowed.
- Free-starting waiting evaders are still defeated on all graphs, but the known strategy requires exponential duration even for trees.
- For K_n with n from 2 to 4, computer searches found waiting-free-start strategies of durations 4, 14, and 32, versus 4, 32, and 256 for Theorem 5.2.
A Deferred proofs
The deferred material includes a normalization lemma for Bh-sets and explicit small-graph strategies, including a duration-4 strategy for K2 and a duration-14 strategy for K3.
- Deferred proofs: Lemma 2.4 derives a translated set by subtracting the minimum element and removing zero from a Bh-set.
- Deferred proofs: The lemma’s contradiction argument shows the translated nonzero set retains the relevant Bh-set property and is therefore also a Br,g,h-set for g,r ≤ h.
- Small strategies: K2 is waiting-freestart-solvable in time 4 using edge delay 2 and alternating queries between its two vertices.
- Small strategies: A K3 strategy against a waiting, free-starting evader has duration 14 with edge delays 2, 2, and 4.
B Short strategies for the most general setting
The paper presents explicit short strategies for the most general evader setting on K3 and K4, and compares them with longer recursive constructions.
- Explicit winning strategies for K3 and K4 have durations 14 and 32 when the evader may wait and start in the past.
- The recursive strategy takes 4, 32, and 256 time steps on K2, K3, and K4, respectively.
- The K4 strategy uses edge delays 2, 5, and 6, with each delay occurring twice.