Open Collections

Abstract

Hunter-Rabbit is a pursuit–evasion game played on the integers from 1 to n, where the hunter attempts to capture the rabbit in as few moves as possible. The hunter is restricted to moving only ±1 at each time step, while the rabbit is allowed more freedom in its movement. Sharp bounds on the expected capture time (𝔼[τ]) have been established in the case where the rabbit moves on the complete graph Kn, which allows it to jump to any vertex at each turn. In this paper, we extend the classical setting by considering the rabbit restricted to a random subgraph of Kn, aiming to determine whether similar asymptotic bounds can still be obtained under these constraints. We prove that, up to constant factors, the same sharp bounds for 𝔼[τ] continue to hold when the game involves a constant number of rabbits and a hunter who is able to catch a rabbit from a greater distance than in the original formulation. We further explore a dynamic version of the game, where the graph governing the rabbit’s movement evolves over time, and we make progress on bounding the capture time in this setting as well. Finally, we show that the problem of identifying a near-optimal evasion strategy for the rabbit on a random graph can be reduced to finding a weighted perfect matching in a related random bipartite graph, thereby providing a new approach to solving this game.