Further results on the Hunters and Rabbit game through monotonicity

Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, Nicolas Nisse

Abstract: Hunters and Rabbit game is played on a graph $G$ where the Hunter player shoots at $k$ vertices in every round while the Rabbit player occupies an unknown vertex and, if not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number $h(G)$ of a graph $G$ is the minimum integer $k$ such that the Hunter player has a winning strategy. This game has been studied in several graph classes, but the computational complexity of computing $h(G)$ remains open in general graphs and even in trees. To progress further, we propose a notion of monotonicity for the Hunters and Rabbit game imposing that a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. Let the monotone hunter number be denoted by $mh(G)$. We show that $pw(G) \leq mh(G) \leq pw(G)+1$ for any graph $G$ with pathwidth $pw(G)$, implying that computing $mh(G)$ is NP-hard. Then, we show that $mh(G)$ can be computed in polynomial time in split graphs, interval graphs, cographs and trees. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between $h$ and $mh$, i.e., that monotonicity does not help. In particular, we show that, for every $k\geq 3$, there exists a tree $T$ with $h(T)=2$ and $mh(T)=k$. We conclude by proving that computing $h$ (resp., $mh$) is FPT parameterised by the minimum size of a vertex cover.

1. Introduction to the Hunters and Rabbit Game

The Hunters and Rabbit game is a pursuit-evasion problem played on a graph. In each round, the Hunter player "shoots" at $k$ vertices, while an invisible Rabbit occupies a vertex and must move to an adjacent one. The Hunter wins if they eventually shoot the vertex occupied by the Rabbit. The minimum $k$ required to guarantee a win is the hunter number, $h(G)$.

Initial state of the game showing the set of possible rabbit positions $Z_0$.

Despite its simple rules, the computational complexity of finding $h(G)$ is notoriously difficult—it remains an open problem even for trees. This paper introduces a formal notion of monotonicity to see if it simplifies the complexity and how it relates to standard graph measures like pathwidth.

2. Monotonicity and Pathwidth

The authors define the monotone hunter number, $mh(G)$, where the Hunter must follow a strategy that ensures once a vertex is cleared, it stays cleared. A vertex is considered cleared if it is shot or if all its neighbors were shot in the previous round, preventing the Rabbit from entering.

A major insight of this research is the connection to pathwidth ($pw(G)$). The authors prove that for any graph, $pw(G) \leq mh(G) \leq pw(G) + 1$. This immediately establishes that computing the monotone hunter number is NP-hard, as pathwidth itself is NP-hard to compute. However, the authors develop polynomial-time algorithms for specific graph classes, including split graphs, interval graphs, cographs, and trees.

3. The Power of Recontamination

In many pursuit games, "recontamination" (letting the fugitive back into a cleared area) does not help the pursuer. In the Hunters and Rabbit game, however, it helps immensely. The authors show that for any integer $k \geq 3$, there exists a tree $T$ where the Hunter only needs 2 hunters to win if they allow recontamination, but needs $k$ hunters if they are forced to play monotonically.

Key steps in a non-monotone winning strategy, demonstrating how recontamination leads to capture.

This gap highlights that non-monotone strategies can be infinitely more efficient. The figure above illustrates a winning sequence where vertices like 'c' are re-occupied by potential rabbit positions ($Z_i$) after being shot, yet the hunter eventually clears the graph.

4. Complexity and Future Directions

Beyond the NP-hardness of the general case, the paper provides a Fixed-Parameter Tractable (FPT) result: deciding if $h(G) \leq k$ is FPT when parameterized by the minimum vertex cover size. This means the game is solvable efficiently for graphs that are "mostly" independent sets with a few central hubs.

The biggest remaining challenge is the original mystery: the computational complexity of the non-monotone hunter number $h(G)$ remains unknown, even for trees. Future work will likely focus on this "Holy Grail" of the field, as well as investigating the hunter number for grid graphs, which are critical for applications in robotics and motion planning.

Summary updated

Abstract

Hunters and Rabbit game is played on a graph $G$ where the Hunter player shoots at $k$ vertices in every round while the Rabbit player occupies an unknown vertex and, if not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number $h(G)$ of a graph $G$ is the minimum integer $k$ such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing $h(G)$ remains open in general graphs and even in trees. To progress further, we propose a notion of monotonicity for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot ``must not host the rabbit anymore''. This allows us to obtain new results in various graph classes. Let the monotone hunter number be denoted by $mh(G)$. We show that $pw(G) \leq mh(G) \leq pw(G)+1$ for any graph $G$ with pathwidth $pw(G)$, implying that computing $mh(G)$, or even approximating $mh(G)$ up to an additive constant, is NP-hard. Then, we show that $mh(G)$ can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between $h$ and $mh$, i.e., that monotonicity does not help. In particular, we show that, for every $k\geq 3$, there exists a tree $T$ with $h(T)=2$ and $mh(T)=k$. We conclude by proving that computing $h$ (resp., $mh$) is FPT parameterised by the minimum size of a vertex cover.
BibTeX
@article{dissaux2025further,
  author = {Thomas Dissaux and Foivos Fioravantes and Harmender Gahlawat and Nicolas Nisse},
  title = {{Further results on the Hunters and Rabbit game through monotonicity}},
  journal = {Inf. Comput.},
  year = {2025},
  doi = {10.1016/j.ic.2025.105302},
}

Loading related content...

Figure