Shelters and Multiple Shots in a Hunters and Rabbit Game

ABSTRACT This paper studies the number of capture attempts required in several generalizations of the hunters and rabbit game played on a digraph , where the rabbit is given additional opportunities to escape. We consider three variants. In the first, some vertices act as shelters where shots have no effect, while the rabbit cannot remain within the set of shelters for more than consecutive time steps. In the second variant, the rabbit must be shot at least times before it is captured. In the third variant, these shots must be consecutive. For the shelter variant with , we show that the minimum number of shots required to capture the rabbit can be computed in polynomial time, and that the capture time is bounded by . We further prove that the case can be reduced to the unrestricted case by means of a layered digraph construction, leading to corresponding bounds on the capture time. For the variant in which the rabbit must be shot at least times, we prove that the minimum number of attempts equals , where denotes the capture attempt number of the original game and that this quantity can be computed in polynomial time. We also establish a connection with the ‐disjoint ‐cuts problem, which enables the computation of optimal capture strategies under time or shot constraints. Finally, for the variant where the rabbit must be shot consecutive times, we show that the minimum number of attempts can also be computed in polynomial time via a reduction to the shelter variant.