Thomas Dissaux

Foivos Fioravantes

Harmender Galhawat

Nicolas Nisse

Further results on the Hunters and Rabbit game through monotonicity *

The 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 it is 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 more restricted graph classes such as trees.

To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as graph searching games) 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.

More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G) + 1 for any graph G with pathwidth pw(G), which implies 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 ≥ 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.

Introduction

The Hunters and Rabbit game is played on a graph G and with a fixed integer k (the number of hunters), where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is 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 Hunters and Rabbit game was first introduced in [START_REF] Britnell | Finding a princess in a palace: a pursuit-evasion problem[END_REF], in the case k = 1, where it was shown that the Hunter player wins in a tree T if and only if T does not contain as subgraph any tree obtained from a star with 3 leaves by subdividing each edges twice. This result was also observed in [START_REF] Haslegrave | An evasion game on a graph[END_REF], where the authors also consider the minimum number of rounds needed for the Hunter player to win. The version where k > 1 was first considered in [1]. Observe that, if k = |V (G)| -1, the Hunter player can win in any connected graph G (in two rounds) by shooting twice a subset of k vertices of G. Hence, let the hunter number of G, denoted by h(G), be the minimum integer k such that k hunters can win in G whatever be the rabbit strategy. The exact value of h(G) has been determined for several specific families of graphs G. For any n ≥ 2, h(P n ) = 1 where P n is the path with n vertices [1] (because the rabbit is forced to move at every round, h(P 1 ) = 0). For any n ≥ 3, h(C n ) = 2 and h(K n ) = n -1, where C n and K n are the cycle and complete graph on n vertices respectively [1]. Moreover, h(G n×m ) = ⌊ min{n,m} 2 ⌋ + 1 [1] and h(Q n ) = 1 + Σ n-2 i=0 i ⌊i/2⌋ [6], where G n×m is the n × m grid and Q n is the hypercube with dimension n. By taking advantage of the bipartiteness of trees, it was proven that, for any tree T , h(T ) ≤ ⌈ 1 2 log 2 (|V (T )|)⌉ [START_REF] Gruslys | Catching a mouse on a tree[END_REF]. Surprisingly, the computational complexity of the problem that takes a graph G and an integer k as inputs and aims at deciding whether h(G) ≤ k is still open, even if G is restricted to be a tree.

In this paper, we progress further in this research direction by exhibiting new classes of graphs G where h(G) can be determined in polynomial time. We also define some monotone variants of the game which allow us to get new results on the initial game.

Graph searching games. The Hunters and Rabbit game takes place in the larger class of Graph Searching games initially introduced in [START_REF] Breisch | An intuitive approach to speleotopology[END_REF][START_REF] Parsons | Pursuit-evasion in a graph[END_REF]. In these pursuit-evasion games, one player plays with a team of searchers (also called cops, hunters, etc.) that must track a fugitive (or robber, rabbit, etc.) moving in a graph. There are many games that can fall under this framework, each one specifying its own rules on, for example, the available moves of the searchers, the speed of the fugitive, whether the fugitive is visible or not, and so on. Several variations of graph searching games have been studied in the literature due to their numerous applications in artificial intelligence [START_REF] Isaza | A cover-based approach to multi-agent moving target pursuit[END_REF], robot motion planning [START_REF] Chung | Search and pursuit-evasion in mobile robotics: A survey[END_REF], constraint satisfaction problems and database theory [START_REF] Gottlob | Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width[END_REF], and distributed computing [START_REF] Nisse | Network decontamination[END_REF]. Graph Searching games have mostly been studied for their significant implications in graph theory and algorithms. In particular, many variants of these games provide algorithmic interpretations of several width measures of graphs like treewidth [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF], pathwidth [START_REF] Parsons | Pursuit-evasion in a graph[END_REF], tree-depth [START_REF] Giannopoulou | Lifo-search: A min-max theorem and a searching game for cycle-rank and treedepth[END_REF], hypertree-width [2], cycle-rank [START_REF] Giannopoulou | Lifo-search: A min-max theorem and a searching game for cycle-rank and treedepth[END_REF], and directed tree-width [START_REF] Johnson | Directed tree-width[END_REF]. The connection between Graph Searching games and structural parameters, such as the treewidth or the pathwidth, is based on the notion of monotonicity [4,[START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF][START_REF] Mazoit | Monotonicity of non-deterministic graph searching[END_REF][START_REF] Ilcinkas | The cost of monotonicity in distributed graph searching[END_REF]. In short, a searchers' strategy is monotone if it ensures that the fugitive can never "recontaminate" a vertex, i.e., it can never access a vertex that has already been "visited" (or "searched") by a searcher. The main question is then, given a game, whether "recontamination does not help in this game" [START_REF] Lapaugh | Recontamination does not help to search a graph[END_REF], i.e., whether there always exists, in this game, an optimal (in terms of number of searchers) monotone winning strategy for the searchers. In particular, the monotonicity played a central role in the proof that the minimum number of searchers to capture an invisible (resp., visible) fugitive in the node-searching game played in a graph G equals its pathwidth plus one [4] (resp., treewidth plus one [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF]).

Not surprisingly, the Hunters and Rabbit game has also a close relationship with the pathwidth of graphs. Precisely, the hunter number of any graph is at most its pathwidth plus one [1]. In this paper, we investigate further this relationship and, for this purpose, we define a notion of monotonicity adapted to the Hunters and Rabbit game and study the monotone variant of the game.

Our contribution. In Section 2, we first give the main notation and definitions used throughout this paper, and we prove (or recall from previous works) several basic properties of the hunter number of graphs. In Section 3, we introduce the notion of monotonicity for the Hunters and Rabbit game. As discussed in Section 3, some peculiar behaviours of the Hunters and Rabbit game makes the definition of monotone hunter strategies not as straightforward as in classical Graph Searching games. We then prove, in Section 3.1, some technical properties (used later) of the monotone hunter number mh(G) of a graph G, i.e., the minimum number of hunters needed by a monotone strategy to win against the rabbit whatever it does in G. In Section 3.2, we prove that mh(G) ∈ {pw(G), pw(G) + 1} in any graph G. This result has interesting implications. Along with implying that it is NP-hard to compute mh(G) for a graph G, it also implies that it is NP-hard to approximate mh(G) up to an additive error of |V (G)| ε , for 0 < ε < 1. On the positive side, we give polynomial-time algorithms to determine h(G) and/or mh(G) in particular graph classes G in Section 4. Precisely, in Section 4.1, we show that ω(G) ≤ h(G) ≤ mh(G) ≤ ω(G) + 1 in any split graph G with maximum clique of size ω(G) and precisely characterise when each bound is reached. We also precisely characterise mh(G) for any interval graph G. In Section 4.2, we design a linear-time algorithm that computes mh(G) for any cograph G and give bounds for h(G) in that case. In Section 4.3, we adapt the Parsons' Lemma [START_REF] Parsons | Pursuit-evasion in a graph[END_REF] to the case of the monotone Hunters and Rabbit game which leads to a polynomial-time algorithm that computes mh(T ) for any tree T . In Section 5, we investigate the monotonicity property in the case of the "bipartite" variant of the Hunters and Rabbit game (see [1,[START_REF] Gruslys | Catching a mouse on a tree[END_REF]). In particular, this allows us to show that, for any k ∈ N, there exist trees T such that h(T ) = 2 and mh(T ) ≥ k. That is, "recontamination helps a lot" in the Hunters and Rabbit game. Finally, in Section 6, we show as a general positive result that the problem of deciding if h(G) ≤ k, for some given integer k, is in FPT when parameterised by the vertex cover number of G. This is done through kernelisation. We close our study by providing directions for further research in Section 7.

Preliminaries

Unless mentioned otherwise, in this paper we will always deal with graphs G = (V, E) that are non empty, finite, undirected, connected and simple. For any two adjacent vertices x, y ∈ V , let xy ∈ E denote the edge between x and y. Given a set S ⊆ V , let G[S] denote the subgraph of G induced by (the vertices in) S and let G \ S denote the subgraph G[V \ S]. For any v ∈ V and X ⊆ V , let N X (v) = {u ∈ X | uv ∈ E} be the open neighbourhood of v in X and let the closed neighbourhood of v in X be N X [v] = (N X (v) ∪ {v}) ∩ X. If X = V , we simply write N (v) and N [v] respectively. For any S ⊆ V , let N (S) = v∈S N (v) \ S and N [S] = N (S) ∪ S. The degree d(v) = |N (v)| is the number of neighbours of v and let δ(G) = min v∈V d(v). An independent set of a graph G = (V, E) is a subset I of V such that, for every u, v ∈ I, uv / ∈ E. A graph is bipartite if its vertex-set can be partitioned into two independent sets.

Hunters and Rabbit game. The Hunters and Rabbit game is played between two players, Hunter and Rabbit, on a non empty, finite, undirected, connected and simple graph G = (V, E). Let k ∈ N * . The Hunter player controls k hunters and the Rabbit player controls a single rabbit. First, the Rabbit player places the rabbit at a vertex r 0 ∈ V . The rabbit is invisible, that is, the position of the rabbit is not known to the hunters. Then, the game proceeds in rounds. In each round i ≥ 1, first, the Hunter player selects a non empty subset S i ⊆ V of at most k vertices of G (we say that the vertices in S i are shot at round i). If the current position r i-1 of the rabbit is shot, i.e., if r i-1 ∈ S i (we say that the rabbit is shot), then the Hunter player wins, and the game stops. Otherwise, the rabbit must move from its current position r i-1 to a vertex r i ∈ N (r i-1 ), and the next round starts. The Rabbit wins if it avoids being shot forever.

A hunter strategy in G = (V, E) is a finite sequence S = (S 1 , . . . , S ℓ ) of non empty subsets of vertices of G. Let h(S) := max 1≤i≤ℓ |S i | and let us say that S uses h(S) hunters. A rabbit trajectory in G starting from W ⊆ V (W will always be assumed non empty) is any walk (r 0 , . . . , r ℓ ) starting from W , i.e., r 0 ∈ W and r i ∈ N (r i-1 ) for every 1 ≤ i ≤ ℓ. A hunter strategy is winning with respect to W if, for every rabbit trajectory (r 0 , . . . , r ℓ ) starting from W , there exists 0 ≤ j < ℓ such that r j ∈ S j+1 , that is, the rabbit is eventually shot whatever be its trajectory starting from W . Given a hunter strategy S = (S 1 , . . . , S ℓ ), a rabbit trajectory (r 0 , . . . , r ℓ ) starting from W is winning against S if r i / ∈ S i+1 for every 0 ≤ i < ℓ. A winning hunter strategy is any winning hunter strategy with respect to V and a rabbit trajectory is any rabbit trajectory starting from V .

The hunter number of G = (V, E) with respect to W ⊆ V , denoted by h W (G), is the minimum integer k such that there exists a winning hunter strategy with respect to W and using k hunters. Let h(G) = h V (G) be the hunter number of G. Note that, for technical reasons, for a single vertex graph G, we set h(G) = 0. This goes in accordance with "the locating part" of the game since the rabbit is already located. The Rabbit player has a strategy R starting from W ⊆ V against k ≥ 1 hunters if, for every hunter strategy S using k hunters, there exists a rabbit trajectory R(S) that is winning against S. Note that, if such a strategy R exists, then h W (G) > k.

The following lemmas will be used throughout this paper. In [1], it is shown that the hunter number is closed under taking subgraphs. We first show that this result trivially extends to the case when the starting positions of the rabbit are restricted.

Lemma 1. Let G = (V, E) be any graph and let H be a subgraph of G, and let

W ⊆ V with W ∩ V (H) ̸ = ∅. Then, h W ∩V (H) (H) ≤ h W (G) ≤ h(G).

Proof. By definition, h W (G) ≤ h(G). Let us show the other inequality.

Let S = (S 1 , . . . , S ℓ ) be a winning hunter strategy in G with respect to W . Let S ′ = (S ′ 1 , S ′ 2 , . . . , S ′ ℓ ) be such that, for every 1

≤ i ≤ ℓ, S ′ i = S i ∩ V (H) if S i ∩ V (H) ̸ = ∅ and S ′ i
consists of any vertex of V (H) otherwise. Then, S ′ is a winning hunter strategy in H with respect to W ∩ V (H). Indeed, any rabbit trajectory (r 0 ∈ W ∩ V (H), r 1 , . . . , r ℓ ) in H is also a trajectory starting from W in G. Since S is winning w.r.t. W , there exists i < ℓ such that r i ∈ S i+1 ∩ V (H) ⊆ S ′ i+1 , and so S ′ is winning w.r.t. W ∩ V (H). Moreover, h(S ′ ) ≤ h(S).

For any hunter strategy S = (S 1 , . . . , S ℓ ), it will be convenient to identify the potential positions of a rabbit (starting in W ⊆ V ) after each round. Precisely, let Z W (S) = (Z W 0 (S), . . . , Z W ℓ (S)) be defined as follows. Let Z W 0 (S) = W and, for every 0 < i ≤ ℓ, let Z W i (S) be the set of vertices v such that there exists a rabbit trajectory (r 0 , r 1 , . . . , r i = v) such that r 0 ∈ W and, for every 0 ≤ j < i, r j / ∈ S j+1 . Formally, for any 1

≤ i ≤ ℓ, let Z W i (S) = {x ∈ V (G) | ∃y ∈ (Z W i-1 (S) \ S i ) ∧ (xy ∈ E(G))}. Intuitively, Z W i (S)
is the set of vertices that the rabbit (starting from some vertex in W ) can have reached at the end of the i th round without having been shot. We will refer to the vertices in Z W i (S) as the contaminated vertices after round i. Note that, if S is winning, then

Z W ℓ (S) = ∅.
In what follows, we write Z i (resp., Z i (S)) instead of Z W i (S) when S and W (resp., when W ) are clear from the context. We now show that we can only consider hunter strategies that consist only of "useful shots". A hunter strategy S = (S 1 , . . . , S ℓ ) is said to be parsimonious if, for every 1 ≤ i ≤ ℓ, S i ⊆ Z i-1 (S). Note that, if S is parsimonious, then Z i ̸ = ∅ for every i < ℓ. Note that if S is parsimonious, then it can be retrieved only from the sequence Z(S) = (Z 0 , . . . , Z ℓ ) of the contaminated sets. Indeed, for any 1

≤ i ≤ ℓ, S i = {w ∈ Z i-1 | ∃x ∈ N (w)\Z i }.
In the following lemma, we establish that we can hunt the rabbit in a parsimonious manner without increasing the number of required hunters. Lemma 2. For any graph G = (V, E) and any non empty subset W ⊆ V , there is a parsimonious winning hunter strategy in G with respect to W and that uses h W (G) hunters.

Proof. Let S = (S 1 , . . . , S ℓ ) be a winning hunter strategy with respect to W ⊆ V using at most k ≥ 1 hunters. Let Z(S) = (Z 0 (S), . . . , Z ℓ (S)) be the set of contaminated vertices for each round of S. If there exists an integer ℓ ′ < ℓ such that Z ℓ ′ (S) = ∅, then S = (S 1 , . . . , S ℓ ′ ) is also a winning hunter strategy with respect to W ⊆ V using at most k hunters. Hence, we may assume that Z i (S) ̸ = ∅ for every 0 ≤ i < ℓ.

Moreover, if there exists an integer 1 ≤ i ≤ ℓ such that S i ∩ Z i-1 (S) = ∅, let h be the smallest such integer and let v ∈ Z h-1 (S). Then, S ′ = (S 1 , . . . , S h-1 , {v}, S h+1 , . . . , S ℓ ) is also a winning strategy with respect to W ⊆ V using at most k ≥ 1 hunters (since

S h ∩ Z h-1 (S) = ∅).
By repeating this process, we may assume that, for every 1

≤ i ≤ ℓ, S i ∩ Z i-1 (S) ̸ = ∅. Let S ′ = (S ′ 1 , S ′ 2 , . . . , S ′ ℓ ′ ) be such that, for every 1 ≤ i ≤ ℓ ′ , S ′ i = S i ∩ Z i-1 (S)
. It is easy to see that, for every i ≤ ℓ ′ , Z i (S) = Z i (S ′ ), and then S ′ is parsimonious. Furthermore, S ′ is a winning hunter strategy with respect to W . Indeed, since S is winning w.r.t. W , for any rabbit trajectory (r 0 , r 1 , . . . , r ℓ ), there exists an integer j < ℓ such that r j ∈ S j+1 . Let i be the smallest such integer. By definition, r i ∈ Z i ∩ S i+1 = S ′ i+1 and so S ′ is winning w.r.t. W . Moreover, h(S ′ ) ≤ h(S).

It must be noticed that there exist graphs G = (V, E) and hunter strategies (S 1 , . . . , S ℓ ) that are winning in G without shooting to all vertices, i.e., such that V \ 1≤i≤ℓ S i ̸ = ∅. For instance, in the graph G that consists of a single edge uv, the strategy ({u}, {u}) is a winning hunter strategy using one hunter and without shooting at v. Note that, in that example, there exists no winning parsimonious hunter strategy using one hunter and that shots to both u and v. The next lemma, that characterises the set of such unshot vertices, will be used throughout the paper. Lemma 3. Let H be any non-empty connected subgraph of any graph G = (V, E). Let W ⊆ V such that W ∩ V (H) ̸ = ∅. Let S = (S 1 , . . . , S ℓ ) be any winning hunter strategy in G with respect to W .

If S i ∩ V (H) = ∅ for all 1 ≤ i ≤ ℓ, then |V (H)| = 1. Proof. Let x ∈ V (H)∩W . Towards a contradiction, assume that |V (H)| ≥ 2. Let y ∈ N H (x) (it exists since H is connected). Note that since S i ∩V (H) = ∅ for all 1 ≤ i ≤ ℓ, {x, y}∩ 1≤i≤ℓ S i = ∅.
Thus, the rabbit can oscillate between x and y during the whole game without being shot. That is, R = (r 0 = x, r 1 = y, r 2 = x, . . . , r ℓ ) is a winning rabbit trajectory against S starting from W ∩ V (H). This contradicts that S is a winning hunter strategy in G with respect to W .

In what follows, we will use the following result of [6]:

Lemma 4. [6] For any graph G, h(G) ≥ δ(G).
The Hunters and Rabbit game has been particularly studied in bipartite graphs [1,6,[START_REF] Gruslys | Catching a mouse on a tree[END_REF] and we continue this study in Section 5. In what follows, bipartite graphs are referred to as G = (V r ∪ V w , E) where (V r , V w ) is implicitly a bipartition of V (G) such that V r and V w are independent sets respectively. We refer to the vertices in V r (resp., in V w ) as the red (resp., white) vertices.

In [1], it is shown that, in bipartite graphs, it is sufficient to consider winning hunter strategies with respect to one of the independent sets of the bipartition. For completeness and to further motivate some of our results, we briefly recall their result. Precisely:

Lemma 5. [1] For any bipartite graph G = (V r ∪ V w , E), h(G) = h Vr (G) = h Vw (G). Proof. By definition, max{h Vr (G), h Vw (G)} ≤ h(G). To show that h(G) ≤ h Vr (G) (resp., h(G) ≤ h Vw (G))
, let S r = (S 1 , . . . , S ℓ ) be a winning hunter strategy in G with respect to V r (resp., w.r.t. V w ). If ℓ is odd, then (S 1 , . . . , S ℓ , S 1 , . . . , S ℓ ) is a winning hunter strategy, and otherwise, (S 1 , . . . , S ℓ , {u}, S 1 , . . . , S ℓ ) where u is any arbitrary vertex is a winning hunter strategy.

Note that, in most of the paper, we will consider hunter strategies with respect to V , but in section 5. More precisely, in Section 5, we will consider the Hunters and Rabbit game in bipartite graphs when the rabbit must start at some vertex of V r . We will refer to this variant as the red variant of the game. The following remark will be widely used.

Remark. Let G = (V r ∪ V w , E) be a bipartite graph and S r = (S 1 , . . . , S ℓ ) be a parsimonious hunter strategy in G with respect to V r . Then, for every 1

≤ i ≤ ⌈ℓ/2⌉, S 2i-1 ⊆ Z 2i-2 ⊆ V r and (if 2i ≤ ℓ) S 2i ⊆ Z 2i-1 ⊆ V w .
Indeed, in a bipartite graph, if the rabbit starts at a vertex in V r (resp., V w ), it must occupy a vertex of V r at the end of every even (resp., odd) round and a vertex of V w at the end of every odd (resp., even) round.

Monotonicity

In classical graph pursuit-evasion games, an important notion is that of monotonicity. Without going into the details, in these games, a strategy is monotone if the area reachable by the fugitive never increases. Said differently, in the particular case of graph searching games, a strategy is monotone if, once a searcher is removed from one vertex, it is never necessary to occupy this vertex during a subsequent round (note that, in some specific cases, for instance in directed graphs, these two definitions are not rigorously equivalent [3]). Monotone strategies have been widely studied [4,[START_REF] Yang | Sweeping graphs with large clique number[END_REF][START_REF] Mazoit | Monotonicity of non-deterministic graph searching[END_REF] because, on the one hand, it is generally easier to design them and, on the other hand, monotone strategies have length polynomial in the size of the graph and, so, corresponding decision problems (is there a monotone strategy using k searchers?) can be proven to be in NP.

It is clear that such a definition is not suitable to the Hunters and Rabbit game. Indeed, consider the graph that consists of a single edge uv: the hunter must shoot at some vertex, say u, and, if the rabbit was at v, it will move to u, i.e., the vertex u is "recontaminated". Therefore, we propose to define monotonicity in the Hunters and Rabbit game as follows (see the formal definition below): once a vertex has been "cleared", if the rabbit can access it in a subsequent round, then the vertex must be shot immediately.

In classical graph searching games, a vertex being cleared at some round means that the searchers' strategy ensures that the fugitive cannot occupy this vertex at this round. Being recontaminated can then be intuitively defined by the fact that a vertex can be reached by the fugitive while having been cleared in a previous round. This intuitive definition does not make any sense in the Hunters and Rabbit game and, in particular, in its red variant in bipartite graphs. Indeed, in such case, every red vertex is cleared at every odd round and so, looking for a strategy without recontamination would be meaningless. To overcome this difficulty, we propose to define the clearing of a vertex at some round by the fact that the actions of the hunters ensure that this vertex cannot be occupied by the rabbit at this round.

A related difficulty comes from the fact that, contrary to classical graph searching games, a vertex may be "cleared" without having been shot during the game. Recall, for instance, our previous discussion for the graph consisting of a single edge. As a less trivial example, Example of a bipartite graph (where V r = {a, c, e, g} corresponds to the red part of the bipartition, illustrated by the red vertices in the figures) and of a parsimonious winning strategy with respect to V r , such that no vertex in {a, e, g} is ever shot. Each subfigure depicts the situation at the end of the corresponding round. In round 0, the rabbit occupies any vertex in {a, c, e, g}. Then, in round 1, the hunter shoots the vertex c (depicted as the cross over the corresponding vertex of subfigure (b)) and the rabbit moves to one of the vertices in {b, d, f }.

The game continues until the end of round 6 (subfigure (g)), at which point the hunter is sure to shoot the rabbit in vertex b. Formally, we have S = ({c}, {d}, {c}, {f }, {c}, {b}) and Z(S) = ({a, c, e, g}, {b, d, f }, {a, c}, {b}, {a, c}, {b}, ∅). consider a star with three leaves whose edges have been subdivided once each. Then, assuming that the leaves and the centre are red, in the red variant, it is possible for one hunter to win without shooting any of the leaves (while any of the leaves may be occupied by the rabbit initially). Indeed, consider the strategy for one hunter where on every odd round it shoots on the centre and on every even round it shoots on an arbitrary neighbour of the centre that was not previously shot. Figure 1 illustrates the above strategy. Therefore, two actions of the hunters may clear a vertex: either a hunter shoots a vertex v at round i and does not shoot the rabbit (i.e. there is no rabbit trajectory, such that r i-1 = v, that is winning against a strategy shooting at v at round i), or the hunters shoot at every contaminated vertex in the neighbourhood of v. In this case, either v was occupied and the rabbit has to leave v, or it was not and cannot be occupied after the move of the rabbit. In both cases, v / ∈ Z i . This discussion motivates the following definition for the monotonicity of hunter strategies.

Definition of monotone strategies and first properties

Given a graph G, a winning hunter strategy S in G with respect to W ⊆ V , is monotone if for every vertex v ∈ V , once v has been "cleared", then it is shot again every time the rabbit can potentially reach v. Formally, we say that a vertex v is cleared

at round i if either v ∈ S i or N (v) ∩ Z i-1 ̸ = ∅ and N (v) ∩ Z i-1 ⊆ S i .
Note that, in the second condition, the fact that we require that N (v) ∩ Z i-1 ̸ = ∅ comes from technicalities when W ̸ = V . A strategy S = (S 1 , . . . , S ℓ ) is monotone if, for every vertex v ∈ V , if there exists an i such that v is cleared at round i, then for every j > i such that v ∈ Z j , the strategy ensures that v ∈ S j+1 . A vertex v is recontaminated at round j if there exists i ≤ j such that v is cleared at round i and v ∈ Z j \ S j+1 .

The monotone hunter number of a graph G with respect to W ⊆ V (G), denoted by mh W (G), is the minimum number k such that k hunters have a monotone winning hunter strategy in G with respect to W . Let us denote the monotone hunter number mh V (G) of G by mh(G). Note that, by definition:

Proposition 1. For every graph G = (V, E) and W ⊆ V , h W (G) ≤ mh W (G) ≤ mh(G).
In this subsection, we prove some general properties of (non-)monotone strategies. Let us start with two technical claims that will be used in several proofs below. Proposition 2. Let S = (S 1 , . . . , S ℓ ) be a hunter strategy in a graph G = (V, E). Let v ∈ V and 1 ≤ i ≤ ℓ. If there exists a vertex u ∈ N (v) and a vertex x ∈ N (u) (possibly x = v) such that u / ∈ j≤i S j and x / ∈ j<i S j , then v ∈ Z p for each p ≤ i.

Proof. This clearly holds if p = 0 since Z 0 = V . If p = 1, there exists a rabbit trajectory (r 0 = u ∈ N (v) \ S 1 , r 1 = v) and so v ∈ Z 1 . Hence, we assume that p > 1.

The rabbit can follow the following strategy depending on whether p is odd or even:

1. p is odd: The rabbit can follow the following trajectory: (r 0 = u, r 1 = x, r 2 = u, . . . , r p-2 = x, r p-1 = u, r p = v) where, for q < p, r q = u if q is even and r q = x if q is odd.

2. p is even: The rabbit can follow the following trajectory: (r 0 = x, r 1 = u, r 2 = x, . . . , r p-2 = x, r p-1 = u, r p = v) where, for q < p, r q = x if q is even and r q = u if q is odd.

In both cases, for every 0 ≤ j < p, r j / ∈ S j+1 since p ≤ i, u / ∈ j≤i S j and x / ∈ j<i S j . Therefore, v ∈ Z p .

The next lemma shows that, as expected, if the hunters follow a monotone strategy, the set of potential positions for the rabbit cannot increase. Lemma 6. Let G = (V, E) be a graph with at least two vertices. Let S = (S 1 , . . . , S ℓ ) be a monotone hunter strategy in G. For any

0 ≤ p ≤ i ≤ ℓ, Z i ⊆ Z p .
Proof. This clearly holds if p = 0 or i = 1 since Z 0 = V . Hence, let us assume that p ≥ 1 and i > 1. Let v ∈ Z i . Since v ∈ Z i , there exists a rabbit trajectory R = (r 0 , . . . , r i-2 = x, r i-1 = u, r i = v) such that, for any 0 ≤ j < i, r j / ∈ S j+1 . By definition of a rabbit trajectory, u ∈ N (v) and x ∈ N (u). Moreover, by monotonicity of S, since u ∈ Z i-1 \ S i (resp. x ∈ Z i-2 \ S i-1 ), u / ∈ q≤i S q (resp. x / ∈ q≤i-1 S q ). By Proposition 2, v ∈ Z p for each p ≤ i.

The next lemma states that, for any non-monotone strategy, there must exist a vertex that has been shot at some round and that is recontaminated later (recall that it is not trivial since a vertex may be recontaminated without being previously shot).

Lemma 7. Let S = (S 1 , . . . , S ℓ ) be a non-monotone winning hunter strategy in a graph G = (V, E). Then, there exist a vertex v ∈ V and

1 ≤ i ≤ ℓ such that v ∈ Z i-1 \ S i and v ∈ p<i S p .
Proof. Towards a contradiction, assume that the statement of the lemma is false, i.e., for every vertex v ∈ V and every 1

≤ i ≤ ℓ, if v ∈ Z i-1 \ S i then v /
∈ p<i S p . Since S is non-monotone and winning, there exists a vertex u such that u is cleared at a round 1 ≤ q ≤ ℓ -2, and then recontaminated at a round j > q (i.e., u ∈ Z j \ S j+1 ). Moreover, by our assumption, u is cleared by shooting each contaminated vertex in N (u) at round q, i.e., Z q-1 ∩ N (u) ⊆ S q .

Let us show that N (u) ⊆ p≤q S p . Let us assume that there exists a vertex x ∈ N (u) such that x / ∈ p<q S p . Since both u, x / ∈ p<q S q and u ∈ N (x), by Proposition 2, we get that x ∈ Z q-1 . Therefore, x ∈ Z q-1 ∩ N (u) ⊆ S q . Hence, N (u) ⊆ p≤q S p .

Since u ∈ Z j then there exists w ∈ (N (u) ∩ Z j-1 ) \ S j and w ∈ p<j S p , i.e., w satisfies the statement of the lemma, a contradiction. Now, let us generalise Lemmas 1 and 2 to monotone strategies. Lemma 8. For any non-empty connected subgraph H of a graph G = (V, E), mh(H) ≤ mh(G). More precisely, if there exists a monotone winning hunter strategy S = (S 1 , . . . , S ℓ ) in G, then there exists a monotone winning hunter strategy S ′ in H using at most max 1≤i≤ℓ |S i ∩ V (H)| hunters.

Proof. Let S = (S 1 , . . . , S ℓ ) be a monotone winning hunter strategy for G.

If |V (H)| = 1, the result clearly holds since mh(H) = 0. Hence, let us assume that |V (H)| > 1. Let m be the minimum integer such that S m ∩V (H) ̸ = ∅ and let u ∈ S m ∩V (H) (by Lemma 3, such an integer m exists because |V (H)| > 1). Let S ′ = (S ′ 1 , . . . , S ′ ℓ ) be the hunter strategy, such that for every 1 ≤ i ≤ ℓ,

S ′ i = S i ∩ V (H), if S i ∩ V (H) ̸ = ∅ {u}, otherwise
First, we have the following claim.

Claim 1. For every 0 ≤ i ≤ ℓ and for any vertex

v ∈ V (H), if v ∈ Z i (S ′ ), then v ∈ Z i (S).
Proof of Claim. Let R = (r 0 , . . . , r i = v) be a rabbit trajectory in H such that for any 0 ≤ j < i, r j r j+1 ∈ E(H), r j / ∈ S ′ j+1 and r i = v (such a trajectory exists since v ∈ Z i (S ′ )). By construction of S ′ , for any 1 ≤ j ≤ ℓ, S j ∩ V (H) ⊆ S ′ j . Therefore, R is also a rabbit trajectory in G with r j / ∈ S j+1 , for all 0 ≤ j < i. Thus, v ∈ Z i (S). ⋄

Let us show that S ′ is a monotone winning hunter strategy in H. First, we show that S ′ is indeed a winning hunter strategy in H. Towards a contradiction, assume that S ′ is not a winning strategy in H. This implies that Z ℓ (S ′ ) ̸ = ∅. Hence, Claim 1 implies that Z ℓ (S) ̸ = ∅, contradicting the fact that S is a winning hunter strategy in G.

Thus, S ′ is a winning strategy in H. Next, we establish that S ′ is indeed monotone. Towards a contradiction, let us assume that S ′ is non-monotone. Hence, by Lemma 7, there exist v ∈ V (H) and 1

≤ q < i ≤ ℓ such that v ∈ S ′ q and v ∈ Z i (S ′ ) \ S ′ i+1 . By Claim 1 and because v ∈ Z i (S ′ ), v ∈ Z i (S). Since S p ∩ V (H) ⊆ S ′ p for any 1 ≤ p ≤ ℓ and because v / ∈ S ′ i+1 , v / ∈ S i+1 . If v = u, i + 1 > m (since u ∈ S ′
p for all 1 ≤ p ≤ m) and so v ∈ S m and in Z i (S) \ S i+1 , contradicting the monotonicity of S.

Otherwise, v ̸ = u. By construction of S ′ , S ′ p \ {u} ⊆ S p for all 1 ≤ p ≤ ℓ. Hence, v ∈ S q and v ∈ Z i (S) \ S i+1 , contradicting the monotonicity of S.

Finally, the fact that h(S ′ ) ≤ max 1≤i≤ℓ |S i ∩ V (H)| ≤ h(S) completes the proof.

Lemma 9. For a graph G = (V, E) and any k ≥ mh(G), there exists a parsimonious monotone winning hunter strategy in G using at most k hunters.

Proof. Let S = (S 1 , . . . , S ℓ ) be a monotone winning hunter strategy in G using at most k ≥ mh(G) hunters such that ℓ is minimum. If S is parsimonious, we are done. Otherwise, among such strategies, let us consider S that maximizes the first round 1 ≤ j ≤ ℓ that makes S not parsimonious. There are several cases to be considered.

• Let Z(S) = (Z 0 (S), . . . , Z ℓ (S)) be the set of contaminated vertices for each round of S.

If there exists an integer ℓ ′ < ℓ such that Z ℓ ′ (S) = ∅, then S = (S 1 , . . . , S ℓ ′ ) is also a monotone winning hunter strategy in G using at most k hunters, contradicting the minimality of ℓ.

Hence, we may assume that Z i (S) ̸ = ∅ for every 0 ≤ i < ℓ.

• Let 1 ≤ j ≤ ℓ be the smallest integer such that S j \ Z j-1 (S) ̸ = ∅ (if no such integer exists, then S is parsimonious and we are done

). If S j ∩ Z j-1 (S) ̸ = ∅, replace S j by S j ∩ Z j-1 (S).
This leads to a winning monotone hunter strategy S ′ (indeed, Z h (S) = Z h (S ′ ) for all 1 ≤ h ≤ ℓ) contradicting the maximality of j.

Hence, we may assume that S j ∩ Z j-1 (S) = ∅. Note that this implies that j < ℓ (since otherwise, S would not be winning).

• If any, let 0 < i be the minimum integer such that

S j+i ∩ Z j+i-1 (S) ̸ = ∅. Let v ∈ S j+i ∩ Z j+i-1 (S). Since v ∈ Z j+i-1 (S), by Lemma 6, v ∈ Z j-1+i ′ (S) for every 0 ≤ i ′ < i.
Then, for every 0 ≤ i ′ < i, replace S j+i ′ by {v}. Let us prove that this leads to a monotone hunter strategy contradicting the maximality of j.

Let S ′ be the strategy obtained by the above modifications. First, note that, for any 0 ≤ h < j, S h = S ′ h and so

Z h (S) = Z h (S ′ ). By definition, Z j (S) = {x ∈ V | ∃y ∈ Z j-1 (S) \ S j ∧ (xy ∈ E)} and, since S j ∩ Z j-1 = ∅, we get Z j (S) = {x ∈ V | ∃y ∈ Z j-1 (S) ∧ (xy ∈ E)}. On the other hand, Z j (S ′ ) = {x ∈ V | ∃y ∈ Z j-1 (S ′ ) \ S ′ j ∧ (xy ∈ E)} = {x ∈ V | ∃y ∈ Z j-1 (S) \ {v} ∧ (xy ∈ E)} since Z j-1 (S ′ ) = Z j-1 (S) and S ′ j = {v}. Hence, Z j (S ′ ) ⊆ Z j (S)
. By induction on j ≤ i ′ ≤ ℓ and using the same arguments, we get that

Z i ′ (S ′ ) ⊆ Z i ′ (S) for every j ≤ i ′ ≤ ℓ. Thus, S ′ is a winning hunter strategy in G using at most k ≥ mh(G) hunters (because Z ℓ (S ′ ) ⊆ Z ℓ (S) = ∅). It remains to show that S ′ is monotone.
For purpose of contradiction, let us assume that S ′ is non-monotone. By Lemma 7, there exists a vertex x and 1

< m ≤ ℓ such that x ∈ Z m-1 (S ′ ) \ S ′ m and x ∈ h<m S ′ h . If x ̸ = v,
then by definition of S ′ (for every 1 ≤ r ≤ ℓ, either S ′ r = S r or S ′ r = {v}) and because Z r (S ′ ) ⊆ Z r (S) for all 1 ≤ r ≤ ℓ, we get that x ∈ h<m S h and x ∈ Z m-1 (S) \ S m which contradicts the monotonicity of S. Hence, let us assume that x = v. Recall that we proved that v ∈ Z j-1 (S) \ S j . Therefore, by monotonicity of S, v / ∈ r<j S r which implies that v / ∈ r<j S ′ r . Since v ∈ S ′ j+i ′ for all 0 ≤ i ′ ≤ i, we get that m > j + i. This means that v ∈ Z m-1 (S) \ S m (because Z r (S ′ ) ⊆ Z r (S) for all 1 ≤ r ≤ ℓ and S ′ r = S r for all r ≥ m > j + i) and v ∈ S j+i , which contradicts the monotonicity of S.

Hence, we may assume that S j+i ′ ∩ Z j+i ′ -1 (S) = ∅ for all 0 ≤ i ′ such that j + i ′ ≤ ℓ.

• Let us recall that j < ℓ and that Z j-1 (S) ̸ = ∅. Thus, let v ∈ Z j-1 (S). So, there exists

w ∈ N (v) ∩ Z j-2 (S) \ S j-1 . Moreover, since w ∈ Z j-2 (S) \ S j-1 (resp. v ∈ Z j-1 (S) \ S j ), w / ∈ S r (resp. v / ∈ S r
) for any r ≤ j (otherwise, it contradicts the monotonicity of S). Let us recall that for any 0

≤ i ′ such that j + i ′ ≤ ℓ, S j+i ′ ∩ Z j+i ′ -1 (S) = ∅. Therefore, w /
∈ S r and v / ∈ S r for any r ≤ ℓ. By Proposition 2, v ∈ Z ℓ (S), which contradicts that S is winning.

This completes the proof.

To conclude this subsection, we give an alternative point of view of Lemma 6. In particular, we show that, if the hunters follow a monotone parsimonious strategy, after having shot at one vertex, the hunters must always shoot at this vertex until it cannot be reached by the rabbit anymore.

Lemma 10. Let G = (V, E) be a graph and S = (S 1 , . . . , S ℓ ) be a parsimonious monotone winning hunter strategy in G.

• If there exist 1 ≤ i < j ≤ ℓ such that v ∈ S i ∩ S j , then v ∈ S i+1 . • If there exists an integer 1 ≤ i < ℓ such that v / ∈ Z i-1 , then v / ∈ S j for every j ≥ i. Proof. First assume that v ∈ S i ∩ S j . Since S is parsimonious, it implies that v ∈ Z i-1 ∩ Z j-1 .
By Lemma 6 and since v ∈ Z j , v ∈ Z i ′ for all i ′ < j. Since v ∈ S i and v ∈ Z p-1 for all i ≤ p ≤ j, by monotonicity of S, v ∈ S p for all i ≤ p ≤ j.

For the second statement, the fact that v / ∈ Z i-1 and Lemma 6 imply that v / ∈ Z j for all j ≥ i. Since S is parsimonious, v / ∈ S j for every j ≥ i.

Surprisingly, the above lemma is not a characterisation of monotone strategies. Indeed, consider the path (a, b, c, d) on four vertices. It can be checked that the hunter strategy ({a}, {b, c}, {b, c}) is parsimonious and winning (with respect to V ) and satisfies the condition of the previous lemma, but this strategy is non-monotone (since a ∈ S 1 and a ∈ Z 1 \ S 2 ).

Monotone Hunter Number and Pathwidth

In this subsection, we relate the monotone hunter number of a graph to its pathwidth. Our result might be surprising since the pathwidth of a graph G is equivalent to the number of searchers required to (monotonously) capture an arbitrary fast invisible fugitive [4] while, in our case, the invisible rabbit seems much weaker than the fugitive: the rabbit is "slow" (it moves only to neighbours) and constrained to move at every round. In this view, we might guess that the monotone hunter number of a graph could be arbitrary smaller than its pathwidth. On the contrary, we show that both parameters differ by at most one.

A path-decomposition of a graph G = (V, E) is a sequence P = (X 1 , . . . , X p ) of subsets of vertices, called bags, such that (1) i≤p X i = V ; (2) for every uv ∈ E, there exists i ≤ p with {u, v} ⊆ X i ; and (3): for every 1 ≤ i ≤ j ≤ q ≤ p, X i ∩ X q ⊆ X j . The width w(P ) of P is the size of a biggest bag of P , i.e., w(P ) = max i≤p |X i | -1. The pathwidth pw(G) of G is the minimum width of its path-decompositions. A path-decomposition of G of width pw(G) is said to be optimal. A path-decomposition is reduced if no bag is contained in another one. It is well known that any graph admits an optimal reduced path-decomposition.

Theorem 1. For any graph

G = (V, E), pw(G) ≤ mh(G) ≤ pw(G) + 1.
Proof. First, let P = (X 1 , . . . , X ℓ ) be a reduced path-decomposition of G with width k. Then, P is a monotone hunter strategy in G using k + 1 hunters. This directly comes from the well known fact that, for every 1 ≤ i < ℓ, X i ∩ X i+1 separates 1≤j≤i X j \ X i+1 from i<j≤ℓ X j \ X i , and so Z i ⊆ i<j≤ℓ X j for every 1 ≤ i ≤ ℓ. In particular, mh(G) ≤ pw(G) + 1.

To show the other inequality, let S = (S 1 , . . . , S ℓ ) be a parsimonious winning monotone hunter strategy in G using at most k ≥ mh(G) hunters (it exists by Lemma 9).

Claim 2. For every v ∈ V \ 1≤i≤ℓ S i , there exists 1 ≤ j ≤ ℓ such that N (v) ⊆ S j .
Proof of Claim. For the purpose of contradiction, let v / ∈ 1≤i≤ℓ S i such that, for every 1

≤ i ≤ ℓ, there exists u i ∈ N (v) \ S i . Then, R = (r 0 = v, u 1 , v, u 3 , . . . , u 2i-1 , v, u 2i+1 , v . . .
) is a winning rabbit trajectory against S, contradicting the fact that S is a winning hunter strategy. ⋄

Let us build a path-decomposition P of G as follows. Start with P 0 = ∅ and let Y 0 = V \ 1≤i≤ℓ S i (Y 0 is the set of vertices that are never shot by S). Assume, by induction, that the sequence P i and the set Y i have been built for some 0 ≤ i < ℓ. Let us define P i+1 and Y i+1 as follows. Let

H i+1 = {u i+1 1 , . . . , u i+1 r i+1 } = {v ∈ Y i | N (v) ⊆ S i+1 }. Let ⊙ denote the concatenation of two sequences. Let P i+1 = P i ⊙ (S i+1 ∪ {u i+1 1 }, . . . , S i+1 ∪ {u i+1 r i+1 }) and let Y i+1 = Y i \ H i+1 . Finally, let P = (X 1 , . . . , X r ) = P ℓ .
Note that, by construction, for every 1 ≤ i ≤ r, |X i | ≤ k + 1, and so w(P) ≤ k. Let us show that P satisfies the three properties of a path-decomposition.

By construction, 1≤i≤ℓ S i ⊆ 1≤i≤r X i . Moreover, by Claim 2, Y 0 ⊆ 1≤i≤r X i . Hence, 1≤i≤r X i = V and the Property (1) of path-decomposition is satisfied. By construction, for every v ∈ Y 0 , there exists a unique 1

≤ i ≤ r such that v ∈ X i . Now, for any v ∈ V \ Y 0 , let 1 ≤ i ≤ j ≤ r such that v ∈ X i ∩ X j . Let 1 ≤ i ′ ≤ ℓ (resp., i ′ ≤ j ′ ≤ ℓ)
such that X i has been built from S i ′ (resp., X j has been built from S j ′ ). By Lemma 10, v ∈ S p ′ for all i ′ ≤ p ′ ≤ j ′ . Hence, by construction, v ∈ X p for all i ≤ p ≤ j. Therefore, Property (3) of the path-decomposition is satisfied for every v ∈ V .

Let uv ∈ E. First, let us assume that u ∈ Y 0 . By Claim 2, v / ∈ Y 0 . Let 1 ≤ j ≤ r such that u ∈ X j , then by construction, N (u) ⊂ X j and so u, v ∈ X j . Second, assume that u, v ∈ V \ Y 0 . For purpose of contradiction, let us assume that, for every 1

≤ i ≤ r, |{u, v} ∩ X i | ≤ 1. W.l.o.g., M = max{1 ≤ j ≤ r | u ∈ X j } < m = min{1 ≤ j ≤ r | v ∈ X j } (both
integers m and M are well defined since Properties (1) and ( 3

) are satisfied). Let 1 ≤ M ′ ≤ ℓ (resp., M ′ ≤ m ′ ≤ ℓ) such that X M has been built from S M ′ (resp., X m has been built from S m ′ ). By definition of P, u / ∈ M ′ <i≤ℓ S i and v ∈ S m ′ \ 1<i<m ′ S i . Because S is parsimonious, v ∈ Z m ′ -1 (S) and so, there exists a w ∈ N (v) ∩ Z m ′ -2 (S) \ S m ′ -1 . By monotonicity of S, w / ∈ 1≤i<m ′ S i . By Proposition 2, u ∈ Z m ′ -1 (S). Since u ∈ (Z m ′ -1 (S) ∩ S M ′ ) \ S m ′ ,
the vertex u is recontaminated, contradicting the monotonicity of S. Therefore, in all cases, for every uv ∈ E, there exists 1 ≤ j ≤ r such that u, v ∈ X j . Hence, Property (2) of path-decompositions is satisfied.

Hence, P is a path-decomposition of width at most k. In particular, pw(G) ≤ mh(G).

Theorem 1 has important consequences.

Corollary 1. Given an n-node graph G and k ∈ N, it is NP-hard to decide whether mh(G) ≤ k. Moreover, it is NP-hard to approximate mh(G) up to an additive error of n ε , for 0 < ε < 1.

Proof. This comes from Theorem 1 and the fact that it is NP-hard to approximate the pathwidth of a graph up to an additive error of n ε , for 0 < ε < 1 [5].

Moreover, Theorem 1 implies that recontamination may help in the Hunters and Rabbit game.

Corollary 2. There exists ε > 0 such that, for any k ∈ N, there exists a tree T with h(T ) ≥ k and mh(T ) ≥ (1 + ε)h(T ).

Proof. For any n ∈ N, let T n be the rooted tree defined as follows: T 0 is a single node, and, for any n > 0, T n is obtained from three copies of T n-1 and a new node r (the root of T n ) such that r is made adjacent to each of the three roots of the copies of T n-1 . We have that

|V (T n )| = 3 n+1 -1 2
and, by the Parsons' Lemma [START_REF] Parsons | Pursuit-evasion in a graph[END_REF], pw(T n ) = n = Θ(log 3 (V (T ))). On the other hand, it is shown in [START_REF] Gruslys | Catching a mouse on a tree[END_REF] that, for any tree T , h(T

) ≤ ⌈ log 2 |V (T )| 2 ⌉. The result follows for (1 + ε) = 2 ln(2)
ln(3) .

(Monotone) hunter number of some graph classes

In this section, we characterise the monotone hunter number of several graph classes such as split graphs, interval graphs, cographs and trees. In particular, in all these cases, our results lead to a polynomial time algorithm to compute the monotone hunter number. The following theorem fully characterises the hunter number of split graphs. Proof. First we show that if, for every two distinct vertices x, y ∈ C, there exists a vertex z ∈ I such that xz ∈ E and yz ∈ E, then h(G) = |C|. We prove this by showing that there exists a winning rabbit strategy against |C| -1 hunters. That is, for any (fixed) hunter strategy S = (S 1 , . . . , S ℓ ) such that |S i | ≤ |C| -1 for every i ≥ 1, we design a rabbit trajectory R = (r 0 , r 1 , . . . , r ℓ-1 ) such that for every i ≥ 0,

Split and interval graphs

A graph G = (V, E) is a split graph if V = C ∪ I can
r i / ∈ S i+1 . Since |S 1 | ≤ |C| -1, there is at least one vertex, say, v ∈ C, such that v / ∈ S 1 . Let r 0 = v.
Hence the rabbit is safe for the first round (since r 0 / ∈ S 1 ). Now, for i ≥ 0, let us assume that we have built (r 0 , . . . , r i ) such that r j / ∈ S j+1 for every 0 ≤ j ≤ i and r i ∈ C. If there is at least one vertex u ̸ = r i in C such that u is not shot in round i + 2 (i.e., u / ∈ S i+2 ), then let r i+1 = u. Otherwise, S i+2 = C \ {r i }. Moreover, observe that there is at least one vertex w ∈ C such that w / ∈ S i+3 (since |S i+3 | < |C|). We note here that w may be the same vertex as r i . Due to our assumptions, there exists a vertex z ∈ I such that wz, r i z ∈ E. Let us set r i+1 = z and r i+2 = w. Observe that r i+1 / ∈ S i+2 (since S i+2 = C \ {r i } and z ∈ I), r i+2 / ∈ S i+3 , and r i+2 ∈ C. Therefore, using the above strategy, we can design R such that it is a winning trajectory against S. Therefore, h(G) ≥ |C|. Since h(G) ≤ |C| (due to Proposition 3), we have that h(G) = |C|.

To prove the reverse direction, we show that if there exist two distinct vertices x, y ∈ C such that N I (x)∩N I (y) = ∅ (i.e., there is no z ∈ I such that xz ∈ E and yz ∈ E), then h(G) ≤ |C|-1 (and so h(G) = |C| -1 by Proposition 3). We prove this by giving a (simple) winning hunter strategy S using |C| -1 hunters. Let S = (S 1 , S 2 , S 3 , S 4 , S 5 ) where S 1 = S 2 = S 5 = C \ {y} and S 3 = S 4 = C \ {x}. Let R = (r 0 , . . . , r 4 ) be any rabbit trajectory. If the rabbit is not shot at the first round, i.e., r 0 / ∈ S 1 , then either r 0 = y or r 0 ∈ I. Accordingly, we consider both these cases below to show that S is a winning hunter strategy. Case 1. r 0 = y : In this case, assume r 1 / ∈ S 2 (otherwise, the rabbit will be shot). Note that

r 1 ∈ N I (y). Since N I (x) ∩ N I (y) = ∅, r 2 ∈ C \ {x}. As S 3 = C \ {x}, r 2 ∈ S 3 ,
and therefore, S is a winning hunter strategy. Case 2. r 0 ∈ I : In this case, if r 1 / ∈ S 2 , then r 1 = y. Now, assuming that r 2 / ∈ S 3 , the rabbit can either move to x (i.e, r 2 = x) or the rabbit can move to N I (y) (i.e., r 2 ∈ N I (y)). We have the following two cases accordingly: Since pw(G), h(G) ∈ {|C| -1, |C|} by Lemma 11 and Proposition 3, let us assume first that h(G) = |C|. By Theorem 2, for any two distinct vertices x, y ∈ C, there exist z ∈ N I (x) ∩ N I (y). For purpose of contradiction, let us assume that there exists a reduced optimal path-decomposition P = (X 1 , . . . , X ℓ ) of width |C| -1. It is well known that there exists 1 ≤ i ≤ ℓ with C ⊆ X i . Moreover, since P has width |C| -1, X i = C. Let us prove now that 1 < i < ℓ. Let us suppose by contradiction that i = 1, i.e., X 1 = C (the case i = ℓ is symmetric). Since P has width |C| -1 and is reduced, let v ∈ X 1 \ X 2 and let z ∈ N I (v) (z exists since |C| > 1 and any two distinct vertices of C have a common neighbour in I). Since v ∈ X 1 = C and v / ∈ 1<j≤ℓ X j , no bag contains both v an z, contradicting the definition of a path-decomposition. Hence, 1 < i < ℓ. Now, let x ∈ C \ X i-1 and y ∈ C \ X i+1 (x and y exists since P is reduced and Next, let us characterise the monotone hunter number of split graphs. We start with the following general lemma.

X i = C). Let z ∈ N I (x) ∩ N I (y). If x = y, no bag contains both x and z (since x appears only in X i = C). If x ̸ = y, there must exist 1 ≤ j ≤ ℓ such that {y, z} ⊆ X j . Since y / ∈ i<h≤ℓ X h , j < i and since z ∈ X j \ X i , z / ∈ i<h≤ℓ X h . Finally, since x / ∈ 1≤h<i X h ,
Lemma 12. Let G be a graph that contains a complete subgraph C such that N (v) \ C ̸ = ∅ for every v ∈ C. Then, mh(G) ≥ |C|. Proof. By Lemmas 1, 4 and Proposition 1, mh(G) ≥ h(G) ≥ h(C) ≥ |C| -1. Let H = G[N [C]].
We will show that mh(H) ≥ |C| and so, the result will follow from Lemma 8.

Let us assume by contradiction that mh(H) = |C| -1. By Lemma 9, there exists a parsimonious monotone winning hunter strategy S = (S 1 , . . . , S ℓ ) in H using |C| -1 hunters.

There must be an index 1

≤ i ≤ ℓ such that |S i ∩ C| = |C| -1.
Otherwise, (r 0 , . . . , r ℓ ) where r 0 ∈ C \ S 1 and r j ∈ C \ (S j+1 ∪ {r j-1 }) for every 1 ≤ j ≤ ℓ is a winning rabbit trajectory, contradicting the fact that S is winning. Hence, let i be the smallest integer such that |S i ∩ C| = |C| -1, let {v} = C \ S i and let w ∈ N (v) \ C (which exists by hypothesis). Let us define a rabbit trajectory R = (r 0 , . . . , r i-

1 = v) such that r j ∈ C \ (S j+1 ∪ {r j-1 }) for every 1 ≤ j < i -1, which is possible since |S j ∩ C| < |C| -1 for all j < i. Thus v ∈ Z i-1 \ S i . Therefore, v /
∈ 1≤j≤i S j since otherwise, v would have been recontaminated. Let us show now that w / ∈ 1≤j<i S j . Towards contradiction, let us assume that w / ∈ 1≤j<i S j . If w / ∈ S i+1 , then let r i = w: this contradicts the monotonicity of S (since w ∈ Z i ∩ 1≤j<i S j ) \ S i+1 ). Hence, w ∈ S i+1 and so there exists z ∈ C \ (S i+1 ∪ {v}). In this latter case, let r i = z, contradicting the monotonicity of S (since

z ∈ Z i ∩ S i ) \ S i+1 ).
Since w / ∈ 1≤j<i S j , let j > i be the smallest integer such that w ∈ S j , or, if w is never shot, let j > i be the smallest integer such that v ∈ S j (it must exists otherwise the rabbit may oscillate between v and w without being never shot). In both cases, let z ∈ C \ (S j ∪ {v}). Thus, by Proposition 2, z ∈ Z j-1 \ S j , contradicting the monotonicity of S.

Recall that a vertex in a graph G is simplicial if its neighbourhood induces a clique. In particular, in a split graph G = (C ∪I, E), a vertex v ∈ C is simplicial if and only if N (v)\C = ∅ (recall that C is supposed to be an inclusion-maximal clique). Note that above results imply that there exist split graphs G for which mh(G) ̸ = h(G), i.e., recontamination helps in split graphs. For instance, let G be the split graph obtained from a clique C and an independent set I by adding a perfect matching between C and I. By Theorems 3 and 2, we get that mh(G) = n and h(G) = n -1.

To conclude this section, let us show another application of Lemma 12. Recall that an interval graph is the intersection graph of a set of intervals in the real line. It is well known that, for any interval graph G, pw(G) = ω(G) -1 where ω(G) is the maximum size of a clique in G, and that G admits an optimal path-decomposition where each bag induces a complete graph.

Theorem 4. Let G be an interval graph. Then, h(G) = mh(G) = ω(G) -1 if every maximum clique has a simplicial vertex. Otherwise, mh(G) = ω(G).

Proof. By Theorem 1, pw(G) ≤ mh(G) ≤ pw(G) + 1 = ω(G). Moreover, by Lemma 4, h(G) ≥ ω(G) -1. If there exists a clique of maximum size that does not contain any simplicial vertex, then by Lemma 12, mh(G) = ω(G). Otherwise, let (X 1 , . . . , X ℓ ) be an optimal path-decomposition of G such that all bags induce a complete graph. For every 1

≤ i ≤ ℓ, if X i contains a simplicial vertex v i , let Y i = {v i } and let Y i = ∅ otherwise. Then, (X 1 \ Y 1 , X 1 \ Y 1 , X 2 \ Y 2 , X 2 \ Y 2 , X 3 \ Y 3 , . . . , X ℓ \ Y ℓ , X ℓ \ Y ℓ ) is a monotone winning hunter strategy using ω(G) -1 hunters. It follows that ω(G) -1 ≤ h(G) ≤ ω(G).
But, the question of deciding h(G) in interval graph when some maximum clique has no simplicial vertex seems more challenging.

Cographs

The class of cographs can be defined recursively as follows [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF]. One vertex is a cograph. Given two cographs A and B, their disjoint union A ∪ B is a cograph, and their join A ⋊ ⋉ B (where all edges between A and B are added) is a cograph. Note that a decomposition of a cograph (i.e., a building sequence of unions and joins performed from single vertices) can be computed in linear time [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF].

Theorem 5. mh(G) can be computed in linear time in the class of cographs.

Proof. Let A and B be two cographs. We prove that:

• mh(A ∪ B) = max(mh(A), mh(B)), and

• mh(A ⋊ ⋉ B) = min(mh(A) + |V (B)|, |V (A)| + mh(B)).
The result then follows from the linear time algorithm to compute the recursive decomposition of cographs [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF].

The first statement is obvious, so let us prove the second one. Let G = A ⋊ ⋉ B and let S A = (S A 1 , . . . , S A ℓ ) and S B be two monotone winning hunter strategies for A and B and using respectively mh(A) and mh(B) hunters. Note that Let S = (S 1 , . . . , S ℓ ) be a parsimonious monotone winning hunter strategy in G using at most k ≥ mh(G) hunters (it exists by Lemma 9) and such that ℓ is minimized among all such strategies

S A ∪ V (B) = (S A 1 ∪ V (B), . . . , S A ℓ ∪ V (B)
. If ℓ = 1, then k = |S 1 | = |V (G)| ≥ min(mh(A) + |V (B)|, |V (A)| + mh(B)).
Hence, let us assume that ℓ > 1. Let Z = (Z 0 , . . . Z ℓ ) be the set of contaminated vertices with respect to S. Note first that since ℓ is minimum, (S 2 , . . . , S ℓ ) is not a winning hunter strategy, and so

Z 1 ̸ = V . Let v ∈ V \ Z 1 . Let us assume that v ∈ V (A) (the case v ∈ V (B) is symmetric). Since v / ∈ Z 1 and Z 0 = V , N (v) ⊆ S 1 . Since B ⊆ N (v), we have that V (B) ⊆ S 1 . Moreover, V (B) ⊆ Z 1 .
Otherwise, there exists w ∈ B such that N (w) ⊆ S 1 and since V (A) ⊆ N (w), we would have

S 1 = V (A) ∪ V (B) = V (G), a contradiction to the fact that ℓ > 1.
Let us prove by induction on i that, for every 1 ≤ i < ℓ, V (B) ⊆ Z i and V (B) ⊆ S i . This statement holds for i = 1 by the previous paragraph. By induction, let us assume that

V (B) ⊆ Z i and V (B) ⊆ S i for some 1 ≤ i < ℓ -1. Since S is monotone, V (B) ⊆ S i+1 . Let us assume that there exists b ∈ V (B) such that b / ∈ Z i+1 . It implies that V (A) ∩ Z i ⊆ S i+1 . Therefore, Z i = (V (A)∩Z i )∪(V (B)∩Z i ) ⊆ S i+1
, which implies that Z i+1 = ∅, contradicting the minimality of ℓ. Thus V (B) ⊆ Z i+1 and the induction hypothesis holds for i + 1. In particular, V (B) ⊆ Z ℓ-1 and so, by monotonicity, Once again, the case of the hunter number seems more challenging. In particular, the following lemma shows that recontamination may help in cographs.

V (B) ⊆ S ℓ . Therefore, V (B) ⊆ S i for all 1 ≤ i ≤ ℓ. Since V (B) ⊆ S i for all 1 ≤ i ≤ ℓ, the strategy S ∩ V (A) = (S 1 ∩ V (A), . . . , S ℓ ∩ V (A))
Lemma 13. For every k ≥ 2, there exists a cograph G such that h(G) ≥ k and mh(G)

≥ 3 2 h(G) -1.
Proof. Let a ≥ 1. Let A and B be two (isomorphic) cographs that consist of the disjoint union of a complete graph with a vertices (denoted by K A and K B respectively) and a independent vertices (so

|V (A)| = |V (B)| = 2a). Let G = A ⋊ ⋉ B. Clearly, h(A) = mh(A) = h(B) = mh(B) = a -1
and, by the proof of Theorem 5, mh(G) = 3a -1. Note also that h(G) ≥ 2a by Lemma 4. Now, (A, K A ∪ K B , K B , A) is a (non-monotone) winning hunter strategy in G using 2a hunters and so h(G) = 2a.

Trees

This section is devoted to showing that the monotone hunter number of trees can be computed in polynomial time. Roughly, we show that a Parsons' like lemma [START_REF] Parsons | Pursuit-evasion in a graph[END_REF] holds for the monotone hunter number in trees and then the algorithm follows the one for computing the pathwidth of trees in [START_REF] Ellis | The vertex separation and search number of a graph[END_REF].

Let us start with the easy case of paths.

Proposition 4. Let P be any path with at least 4 vertices. Then, 1 = h(P ) < mh(P ) = 2.

Proof. The fact that h(P ) = 1 has been proven in [1], and the fact that mh(P ) ≤ 2 is easy. Towards a contradiction, let us assume that there exists a winning monotone hunter strategy in P using one hunter and let S = (S 1 , . . . S ℓ ) be a shortest such strategy (i.e., minimizing ℓ). Let Z = (Z 1 , . . . , Z ℓ ) be the set of contaminated vertices with respect to S. Let w ∈ V (P ) such that S 1 = {w}. Note that w ∈ Z 1 and so, ℓ > 1. Since P has length at least 4, there exist x, y ∈ V (P ) such that x ∈ N (w) and y ∈ N (x) \ {w}. We will prove by induction on i that S i = {w} for all 1 ≤ i ≤ ℓ. The base case (i = 1) is already proven. Assume now that for some 1 ≤ q < ℓ, it holds that S j = {w} for all 1 ≤ j ≤ q. Thus, x, y / ∈ 1≤j≤q S j and so, by Proposition 2, w ∈ Z q . Hence, by the monotonicity of S, we have that w ∈ S q+1 , showing the step of the induction. Therefore, x, y / ∈ 1≤j≤ℓ S j and so, by Proposition 2, w, x, y ∈ Z ℓ , contradicting the fact that S is a winning strategy in P . Therefore, mh(P ) ≥ 2.

We then need the following two technical results.

Proposition 5. Let G = (V, E) be any connected graph and H be a connected subgraph of G. Let S = (S 1 , . . . , S ℓ ) be any parsimonious monotone winning hunter strategy in G. Moreover, let 1 ≤ i ≤ ℓ and x, y ∈ V (H) such that x ∈ j<i S j , y ∈ Z i-1 and minimising the distance between such x and y in H. If x, y / ∈ S i , then xy ∈ E(H).

Proof. Note first that x ̸ = y. Indeed, assuming otherwise would imply that S is not monotone since y = x ∈ ( j<i S j ∩ Z i-1 ) \ S i . Hence, we may assume that x ̸ = y. Let P be a shortest path from x to y in H. Let a be the neighbour of x in P . If a = y, then {x, y} ∈ E(G), and the claim holds. Hence, we may assume that a ̸ = y. By minimality of the distance between x and y, a / ∈ Z i-1 and a / ∈ j<i S j . Let b ̸ = x be the other neighbour of a in P . We show that b / ∈ j<i S j . If b ̸ = y, then, by minimality of the distance between x and y, b / ∈ j<i S j . If b = y, since y ∈ Z i-1 \ S i , then y / ∈ j<i S j , because otherwise this would contradict the monotonicity of S. Therefore, by Proposition 2, a ∈ Z q for every q < i. In particular, a ∈ Z i-1 , a contradiction. Lemma 14. Let G = (V, E) be any graph and S = (S 1 , . . . , S ℓ ) be a parsimonious monotone winning hunter strategy in G that uses at most k hunters. Let H be a connected subgraph of

G with |V (H)| > 1. If S i ∩ V (H) ̸ = ∅ and S j ∩ V (H) ̸ = ∅ for some 1 ≤ i < j ≤ ℓ, then S z ∩ V (H) ̸ = ∅ for every i ≤ z ≤ j.
Proof. Let 2 ≤ i + 1 < j ≤ ℓ be such that V (H) ∩ S i ̸ = ∅ and V (H) ∩ S j ̸ = ∅. Towards a contradiction, let us assume that there exists i < z < j such that S z ∩ V (H) = ∅. Let X = V (H)∩ q<z S q . Since V (H)∩S i ̸ = ∅ and i < z, we get that X ̸ = ∅. Let Y = V (H)∩Z z-1 . Since S j ∩V (H) ̸ = ∅ and S is parsimonious, we have that Z j-1 ∩V (H) ̸ = ∅. Let u ∈ Z j-1 ∩S j ∩V (H). By Lemma 6, u ∈ Z q for every q < j. In particular, u ∈ Z z-1 and so Y ̸ = ∅. Let x ∈ X and y ∈ Y such that the distance bewteen x and y in H is minimum. By Proposition 5, xy ∈ E. Thus, since y ∈ Z z-1 \ S z , we get that x ∈ Z z . Therefore, since S is monotone and x ∈ q<z S q , we must have x ∈ S z+1 . By Lemma 10, since x ∈ q<z S q and x ∈ S z+1 , then x ∈ S z . Hence,

V (H) ∩ S z ̸ = ∅, a contradiction.
Let T be a tree and v ∈ V (T ). A branch at v is any connected component of T -v. A star is any tree with at least two vertices and at most one vertex with degree at least two. Roughly speaking, Parsons' Lemma [START_REF] Parsons | Pursuit-evasion in a graph[END_REF] states that, for any tree T and k ∈ N, pw(T ) ≥ k + 1 if and only if there exists a vertex v such that at least three branches at v have pathwidth at least k.

Here, we adapt this lemma in the case of the monotone hunter number of trees.

Lemma 15 (Parsons' like lemma). Let T = (V, E) be any tree.

• mh(T ) = 0 if and only if |V | = 1;

• mh(T ) = 1 if and only if T is a star;

• mh(T ) = 2 if and only if T is not a star and contains a path P such that T \ P is a forest of stars and isolated vertices;

• For every k ≥ 3, mh(T ) ≥ k if and only if there exists a vertex v ∈ V such that at least three branches at v have monotone hunter number at least k -1.

Proof. The first item is trivial. Then, if T is a star, then shooting twice at the vertex of maximum degree is a monotone winning hunter strategy using one hunter, and so, (since |V (T )| ≥ 2), mh(T ) = 1. If T is not a star (and |V (T )| > 1), then it contains a path with at least 4 vertices as a subgraph. By Proposition 4 and Lemma 8, it follows that mh(T ) ≥ 2, which concludes the proof of the second item. If T is not reduced to a star and contains a path P such that T \ P is a forest of stars and isolated vertices, it is easy to show that mh(T ) ≤ 2. Otherwise, T contains a vertex v such that at least three components of T -v contain a path with 4 vertices. The "if" statement of the fourth item then shows that mh(T ) > 2 and concludes the proof of the third item.

Let us prove the fourth item. Let k ≥ 3. Proof of ⇐: Let us first assume that there exists some vertex v and three branches B 1 , B 2 and B 3 at v, such that mh(B 1 ), mh(B 2 ), mh(B 3 ) ≥ k -1. We will show that mh(T ) ≥ k. Towards a contradiction, let us assume that mh(T ) < k. By Lemma 9, there exists a parsimonious monotone strategy S = (S 1 , . . . , S ℓ ) in T that uses at most k -1 hunters. Let Z = (Z 1 , . . . , Z ℓ ) be the set of contaminated vertices with respect to S.

For j ∈ {1, 2, 3}, let 1 ≤ i j ≤ ℓ be the minimum integer such that V (B j ) ∩ Z i j = ∅. Note that, by Lemma 6, V (B j )∩Z q = ∅ for all i j ≤ q ≤ ℓ, and since S is parsimonious, V (B j )∩S q = ∅ for all i j < q ≤ ℓ. Note also that, since mh(B j ) ≥ k -1 ≥ 2, B j has at least two vertices.

Since Z i j -1 ∩ V (B j ) ̸ = ∅ and Z i j ∩ V (B j ) = ∅, it implies that S i j ∩ V (B j ) ̸ = ∅ (otherwise, let w ∈ (Z i j -1 ∩ V (B j )) and u ∈ N (w) ∩ V (B j ), then u ∈ Z i j ∩ V (B j
), a contradiction with the definition of i j ). W.l.o.g., let us assume that i 1 ≤ i 2 ≤ i 3 .

We will show that there exists a round j 2 during which all the k -1 hunters will have to shoot on vertices of B 2 , and that v ∈ Z j 2 -1 , which will lead to a contradiction.

For any 1 ≤ i ≤ 3, let j i be an index such that |S j i ∩ V (B i )| = k -1. These indices exist as, otherwise, by Lemma 8, mh(B i ) < k -1. We will first show that j 2 < i 3 , which will be used to prove that v ∈ Z j 2 -1 . Observe that j 2 ≤ i 2 ≤ i 3 . Moreover,

j 2 ̸ = i 3 since S i 3 ∩ V (B 3 ) ̸ = ∅, |S j 2 ∩ V (B 2 )| = k -1
and S uses at most k -1 hunters. Hence, j 2 < i 3 . Therefore, by Proposition 2 and Lemma 14, V (B 3 ) ∪ {v} ⊆ Z q for all q ≤ j 2 . In particular,

v ∈ Z j 2 -1 . Moreover, since S j 2 ⊆ V (B 2 ), v / ∈ S j 2 . Hence, x ∈ Z j 2 where x is the neighbour of v in B 1 , i.e., Z j 2 ∩ V (B 1 ) ̸ = ∅. Since Z i 1 ∩ V (B 1 ) = ∅, if i 1 < j 2 ,
then there is a contradiction to Lemma 6. Otherwise, j 2 < i 1 ≤ i 2 (because j 2 ̸ = i 1 ) and so either j 1 < j 2 < i 1 or j 2 < j 1 < i 2 (because j 1 ̸ = j 2 , j 1 ≤ i 1 ≤ i 2 and j 1 ̸ = i 2 ), both contradicting Lemma 14.

Proof of ⇒: Now let us assume that, for every v ∈ V , at most two branches at v have monotone hunter number at least k -1. Let us prove that there exists a parsimonious monotone winning hunter strategy S in T using at most k -1 hunters.

First, let us assume that there exists a path P = (v 1 , . . . , v p ) such that for any connected component C of T \ P , mh(C) < k -1. The following hunter strategy is parsimonious monotone winning and uses at most k -1 hunters. The strategy consists of p phases executed sequentially from i = 1 to p. Phase i consists in shooting v i at each round, and in using the k -2 remaining shots to clear sequentially each connected component of T \ P that is adjacent to v i (this is possible since each of these branches at v has monotone hunter number at most k -2). Finally, the last round of Phase i (except for i = p) consists in shooting to both v i and v i+1 (recall that k -1 ≥ 2).

Let us now show that a path P , defined as in the previous paragraph, exists. Let X be the set of vertices v such that exactly two branches at v have monotone hunter number at least k-1. First, let us assume that X ̸ = ∅ and let us show that it induces a path. Let x, y ∈ X and let z be any internal vertex of the path between x and y. Let B (resp., B ′ ) be the branch at z that contains x (resp., that contains y). One branch B x at x with mh(B x ) ≥ k -1 is a subgraph of B and so, by Lemma 8, mh(B) ≥ k -1. Similarly, mh(B ′ ) ≥ k -1 and so, z ∈ X and therefore X induces a subtree of T . If there exists a node w of degree at least three in T [X], by similar arguments, there are at least three branches at w with monotone hunter number at least k -1, a contradiction with the initial hypothesis. Hence, X induces a path (v 2 , . . . , v p-1 ). Let B 1 be the branch at v 2 not containing v 3 such that mh(B 1 ) = k -1 (if v 3 does not exist, B 1 is any branch at v 2 with mh(B 1 ) ≥ k -1) and let v 1 be the neighbour of v 2 in B 1 . Symmetrically, let B p be the branch at v p-1 not containing v p-2 such that mh(B p ) = k -1 (if p -1 = 2, let B p be the branch at v 2 , distinct from B 1 , and with mh(B p ) ≥ k -1) and let v p be the neighbour of v p-1 in B p . Then, P = (v 1 , v 2 , . . . , v p-1 , v p ) satisfies the desired conditions.

Finally, if X = ∅, let v 1 be any vertex of T . We build the path P starting from v 1 as follows. Let us assume that a path (v 1 , . . . , v i ) has already been built for some i ≥ 1. If there exists a branch B at v i , not containing v i-1 (if i > 1), and with monotone hunter number at least k -1 (if any, such a branch must be unique since X = ∅), then, let v i+1 be the neighbour of v i in B. The process ends when no such branch B exists and the obtained path satisfies the desired conditions.

This completes the proof.

by u ∈ V (T ) and all the descendent of u. For any ) ≤ k and so there is at most 1 branch at w that has monotone hunter number at least k + 1. To conclude, note that the hunter strategy consisting in applying sequentially all the monotone winning hunter strategies for the branches at v, while shooting continuously on v, is a monotone winning hunter strategy in T using at most k + 1 hunters, i.e., mh(T ) ≤ k + 1.

x 1 , • • • , x p ∈ V (T [u]), let T [u,
The upcoming corollary, obtained from Lemmas 15 and 16, describes how to compute mh(T ) of a rooted tree T , bottom-up, from its leaves to the root, such that, for any u ∈ V (T ), mh(T [u]) is computed from the values (mh(T [u i ])) u i child of u and from the critical vertices the subtrees T [u i ] contain. We need the following technical definition to finally describe our algorithm, which will recursively build a "label" for each vertex from the labels of its children. Recall that, for any

u, x 1 , • • • , x p ∈ V (T [u]
), the tree T [u, x 1 , . . . , x p ] denotes the subtree obtained from T [u] after the vertices of i≤p V (T [x i ]) have been removed. Definition 1. For any tree T [u], the label λ(u, T [u]) of u is a list of integers (a 1 , . . . , a p ), where a 1 > a 2 > • • • > a p ≥ 0, possibly a p may be marked with a star, and there exists a set of vertices {ℓ 1 , . . . , ℓ p }, such that:

• mh(T [u]) = a 1 . • For 1 ≤ i < p, mh(T [u, ℓ 1 , . . . , ℓ i ]) = a i+1 and ℓ i is an a i -critical vertex in T [u, ℓ 1 , . . . , ℓ i-1 ].
We will say that ℓ i is associated to a i .

• ℓ p = u. If a p is not marked with a star ( * ), then there is no a p -critical vertex in T [u, ℓ 1 , . . . , ℓ p-1 ]. If a p is marked (with a star), then ℓ p is an a p -critical vertex. In both cases, T [u, ℓ p ] = T [u, u] is the empty tree.

exists a vertex ℓ 1 in T [v] such that ℓ 1 is 1-critical (because a 1 = 1) and moreover ℓ 1 ̸ = v because λ ̸ = (a 1 )
. By the definition of a vertex being 1-critical, we get that ℓ 1 has a child y such that mh(T [y]) = 1. Since mh(T [y]) = 1, we get that T [y] contains at least one edge and so there exists x ∈ N (y). Since T [v] is connected, there exists a (ℓ 1 , v)-path P = (p 1 = ℓ 1 , . . . p q = v). Thus, P ′ = (x, y, p 1 = ℓ 1 , . . . , p q = v) is a path with at least 4 vertices. Hence, mh(T [v]) > 1 and which contradicts that

λ(v) = (1, 0) since a 1 = mh(T [v]).
The following notation is used in Algorithm 1 and in its proof (Lemma 17). For any sequence λ = (a 1 , . . . , a p ) and any integer a > a 1 , let a⊙λ = (a ′ 1 = a, a ′ 2 = a 1 , . . . , a ′ p ′ -1 = a p-1 , a ′ p ′ = a p ), i.e., ⊙ denotes the concatenation. Moreover, let pref (λ) = (a 1 , • • • , a p-1 ) (the prefix of λ) and t(λ) = a p (the tail of λ).

Lemma 17. Algorithm 1 takes a tree T rooted at some vertex v ∈ V (T ) and the label of each child of v as inputs and it returns the label of

v in T [v].
Proof. Our goal is to prove that the algorithm returns the label of v in

T [v], denoted as λ(v, T [v]) = (a v 1 , . . . , a v p v ). Let d T [v] (v) = d.
Let λ alg be the value computed by Algorithm 1. Observe first that if d = 0, by Corollary 4, mh(T [v]) = 0, and so, by definition of a label, λ(v, T [v]) = (0). Note that Algorithm 1 returns (0) in line 2. Hence,

λ alg = λ(v, T [v]) = (0). Thus let us assume that d > 0. Let v 1 , . . . v d be the d children of v in T [v]. For any 1 ≤ i ≤ d, let λ i = λ(v i , T [v i ]) = (a i 1 , . . . , a i p i ) be the label of v i in T [v i ]. W.l.o.g., let us assume that a 1 1 ≥ a 2 1 ≥ • • • ≥ a d 1 and let k = a 1 1 = max i∈{1,...,d} max q∈{1,...,|λ i |} a i q . For each 1 ≤ i ≤ d, let T i k = T [v i ]. Also, for 0 ≤ m ≤ k, if m = a i j for any 1 ≤ j ≤ p i , let T i m-1 be obtained from T i m by removing T [ℓ i j ]
where ℓ i j is the vertex associated to a i j . Otherwise, let

T i m-1 = T i m , i.e., T i m = T [v i ] \ a i j ∈λ i ,a i j >m T [a i j ]. Finally, for any 0 ≤ m ≤ k, let T m be the subtree of T [v] induced by 1≤i≤d V (T i m ).
Intuitively, T m is the subtree obtained from T [v] by removing the substrees T [w] for every vertex w ̸ = v such that mh(T [w]) ≥ m + 1. Note that T k = T [v] = T and that mh(T m ) ≤ m + 1 for every m ≤ k. Note also that T 0 consists of v and, possibly, some of its children.

Let us prove by induction on 0 ≤ m ≤ k that after the (m + 1)-th iteration of the loop of the algorithm, the current value of λ, the variable of Algorithm 1, denoted by λ m , is equal to the label λ(v, T m ), i.e., the label of v in T m . If this induction holds, then, when m = k, the algorithm returns

λ alg = λ k = λ(v, T k ) = λ(v, T [v]
), which concludes the proof.

Let n(m) be the number of children w of v, such that m or m * is in the label of w.

The base case is for m = 0.

• Let us assume first that n(0) ≥ 1. Recall that, by the definition of T 0 , for any child w of v in T 0 , mh(T 0 [w]) ≤ 0, i.e., T 0 [w] only contains w. Therefore, v is not 1-critical in T 0 . Thus, by Case 2 of Corollary 4 and by the definition of the labelling, mh(T 0 ) = 1 and λ(v, T 0 ) = (1), which corresponds to λ 0 (line 9 of Algorithm 1).

• Let us assume now that n(0) = 0, i.e. T 0 only contains v. By Case 1 of Corollary 4, mh(T 0 ) = 0. Thus, λ(v, T 0 ) = (0). Moreover, since, n(m) = 0, λ 0 = (0) (line 11 of Algorithm 1).

Let us assume now that m = 1. It follows from the case m = 0 that λ 0 = λ(v, T 0 ). Before analysing the several subcases for m = 1, let us recall that λ(v, T m ) cannot have label (1, 0) by Claim 3.

• Assume first that n(1) = 0. This implies that T 1 = T 0 , and so, we get that λ 1 = λ 0 = λ(v, T 0 ) = λ(v, T 1 ) (in this case, Algorithm 1 does nothing during the 2-nd iteration of the loop).

Algorithm 1 Let T be a tree rooted in a vertex v. Let v 1 , . . . , v d be the d children of v in T [v] and let λ 1 , . . . , λ d be their corresponding labels.

1: if d = 0 then 2:
return (0); 3: end if 4: Let λ = () and let k = max i∈{1,...,d} max q∈{1,...,|λ i |} λ i ; 5: for m from 0 to k do 6:

Let n(m) be the number of children with m or m * in their label; else if m = 1 then 14: //Case 3: one child of v has 1 in its label, its subtree does not contain any 1-critical vertex and no child of v has 0 in its label

15: if n(m) = 1, ∀1 ≤ i ≤ d, m / ∈ pref (λ i ) and t(λ i ) ̸ = m * and λ = (0) then 16:
λ ← (1 * ); 17: //Case 4: v has a unique child, and moreover, this child is a 1-critical vertex, or 18: //Case 5: v has at least 2 children with at least one having 1 in its label

else if n(m) = 2 and ∃1 ≤ i ≤ d, m ∈ pref (λ i ) or t(λ i ) = m * then 29:
λ ← (m + 1); 30: //Case 8: two children of v have m or m * in their label. Moreover, their subtrees do not contain any m-critical vertex 31:

else if n(m) = 2 and, ∀1 ≤ i ≤ d, m / ∈ pref (λ i ) and t(λ i ) ̸ = m * then 32:
λ ← (m * ); 33: //Case 9: one child of v has m or m * in its label. Moreover, its subtree contains an m-critical vertex and mh(T m-1 ) = m 34: λ ← (m + 1); 36: //Case 10: one child of v has m or m * in its label. Moreover, its subtree contains an m-critical vertex and mh(T m-1 ) < m 37: end if 44: end for 45: return λ;

else if n(m) = 1, ∃1 ≤ i ≤ d, m ∈ pref (λ i ) or t(λ i ) = m * ,
else if n(m) = 1, ∃1 ≤ i ≤ d, m ∈ pref (λ i ) or t(λ i ) = m * ,
• Assume next that n(1) = 1, and let v i be the child of v such that (1) or (1 * ) is in the label of v i .

-Let us first assume that we are in Case 3 (line 16 of Algorithm 1), i.e. 1 (not 1 * ) is the last element of the label of v i , and λ 0 = (0). Recall that since λ 0 = (0), and by the case m = 0, T 0 is a single vertex. Thus, v has only one child w in T 1 , and mh(T 1 [w]) = 1 (because n(1) = 1), i.e., T 1 is a star centred in w (but rooted in v). So, by Case 3 of Corollary 4, mh(T 1 ) = 1. Moreover, v is 1-critical in T 1 . Thus, λ(v, T 1 ) = (1 * ), which correspond to λ 1 (line 16 of Algorithm 1).

-Let us then assume that we are in Case 5 (line 20 of Algorithm 1), i.e. 1 (not 1 * ) is the last element of the label of v i , and λ 0 = (1). Observe that if λ 0 = (1), and by the case m = 0, then T 0 is a star centred (and rooted) in v. Thus, v has at least

2 children in T 1 (since v i ∈ V (T 1 ) \ V (T 0 )
) but there is one child of v, v i , that is not a leaf (i.e., v i is the root of a subtree with monotone hunter number 1). So, by Case 5 of Corollary 4, mh(T 1 ) = 2. By Lemma 16, for any vertex w ∈ T 1 , there is at most 1 branch at w that has monotone hunter number at least 2 (so there are no 2-critical vertices). Therefore, λ(v, T 1 ) = ( 2), which corresponds to λ 1 (line 20 of Algorithm 1).

-Let us consider the Case 4 (line 20 of Algorithm 1), i.e. the last element of the label of v i is 1 * and moreover, v i is the unique child of v. By Case 4 of Corollary 4, mh(T 1 ) = 2. By Lemma 16, for any vertex w ∈ T 1 , there is at most 1 branch at w that has monotone hunter number at least 2 (so there are no 2-critical vertices). Thus, λ(v, T 1 ) = ( 2), which corresponds to λ 1 (line 20 of Algorithm 1).

• Finally, assume that n(m) = n(1) ≥ 2. Hence, in T 1 , v has at least two children which are the roots of subtrees with monotone hunter number 1. By Case 5 of Corollary 4, mh(T 1 ) = 2 (recall that by definition of T 1 , mh(T 1 ) ≤ 2). Moreover, by Lemma 16, for any vertex w ∈ T 1 , there is at most 1 branch at w that has monotone hunter number at least 2 (so there are no 2-critical vertices). Therefore, λ(v, T 1 ) = (2), which corresponds to λ 1 (line 20 of Algorithm 1).

We are now ready to prove the induction step. Let m ≥ 2 and let us assume that λ(v, T m-1 ) = λ m-1 . We will prove that λ(v, T m ) = λ m .

• Case 6. We are in the case where n(m) ≥ 3 (line 26 of Algorithm 1). Since n(m) ≥ 3, in T m , v has at least 3 children v j , v j ′ and v j ′′ such that mh(T j m ) = mh(T j ′ m ) = mh(T j ′′ m ) = m (and mh(T i m ) ≤ m for every 1 ≤ i ≤ d). Thus, we are in the Case 6 of Corollary 4, and so, mh(T m ) = m + 1. Note also that, by Lemma 16 and for any vertex w ∈ T m , there exists at most 1 branch B at w with mh(B) ≥ m + 1. Therefore, T m has no m + 1-critical vertex, and so λ(v, T m ) = (m + 1). To conclude, line 26 of Algorithm 1 precisely returns λ m = (m + 1). Hence, λ m = λ(v, T m ).

• Case 7. We are in the case where n(m) = 2 and there exists 1 ≤ i ≤ d such that m ∈ pref (λ i ) or t(λ i ) = m * , i.e., T i m contains an m-critical vertex (line 29 of Algorithm 1). Let us denote by y i be the m-critical vertex in T i m . Since n(m) = 2, in T m , v has exactly 2 children v j and v j ′ (and i ∈ {j, j ′ }) such that mh(T j m ) = mh(T j ′ m ) = m and mh(T q m ) < m for every other child v q of v in T m . Since y i is critical, we are in the Case 7 of Corollary 4. Thus, mh(T m ) = m + 1. Note also that, by Lemma 16, for any vertex w ∈ T m , there exists at most 1 branch B at w with mh(B) ≥ m + 1. Therefore, T m has no m + 1-critical vertex, and so λ(v, T m ) = (m + 1). To conclude, line 29 of Algorithm 1 precisely returns λ m = (m + 1). Hence, λ m = λ(v, T m ).

• Case 8. We are in the case where n(m) = 2 and m / ∈ pref (λ i ) and t(λ i ) ̸ = m * for all 1 ≤ i ≤ d, i.e., T i m does not contain any m-critical vertex (line 32 of Algorithm 1). Since n(m) = 2, in T m , v has exactly 2 children v j and v j ′ such that mh(T j m ) = mh(T j ′ m ) = m and mh(T q m ) < m for every other child v q of v in T m . Since v j and v j ′ are not m-critical, we are in the Case 8 of Corollary 4. Thus, mh(T m ) = m. Since n(m) = 2, v is clearly an m-critical vertex, and so λ(v, T m ) = (m * ). To conclude, line 32 of Algorithm 1 precisely returns λ m = (m * ). Hence, λ m = λ(v, T m ).

• Case 9. We are in the case where n(m) = 1, there exists 1

≤ i ≤ d such that m ∈ pref (λ i ),
or m * = t(λ i ) (i.e., there is an m-critical vertex in T i m ) and λ m-1 contains m or m * , i.e., mh(T m-1 ) = m (line 35 of Algorithm 1). Let y i denote the m-critical vertex in T i m . Since n(m) = 1, in T m , v has exactly 1 child v j (and so, i = j) such that mh(T j m ) = m and mh(T q m ) < m for every other child v q of v in T m , and therefore

T m-1 = T m [v, y i ].

Thus, by definition of the labelling and since

m ∈ λ m-1 , mh(T m-1 ) = mh(T m [v, y i ]) = m.
Therefore, we are in the Case 9 of Corollary 4. Thus, mh(T m ) = m + 1. Note also that, by Lemma 16, for any vertex w ∈ T m , there exists at most 1 branch B at w with mh(B) ≥ m + 1. Therefore, T m has no (m + 1)-critical vertex, and so λ(v, T m ) = (m + 1). To conclude, line 35 of Algorithm 1 precisely returns λ m = (m+1). Hence, λ m = λ(v, T m ).

• Case 10. We are in the case where n(m) = 1, there exists 1

≤ i ≤ d such that m ∈ pref (λ i ), or m * = t(λ i ) (i.e.
, there is an m-critical vertex in T i m ), and m / ∈ λ m-1 (line 38 of Algorithm 1). Let us denote by y i be the m-critical vertex in

T i m . Since n(m) = 1, in T m , v i is the single child of v such that mh(T i m ) = m and mh(T q m ) < m for every other child v q of v in T m . Therefore, T m-1 [v] = T m [v, y i ].

Thus, by definition of the labelling and since

m / ∈ λ m-1 , mh(T m-1 [v]) = mh(T m [v, y i ]) < m.
Therefore, we are in the Case 10 of Corollary 4. Thus, mh(T m ) = m. Let λ m-1 = λ(v, T m-1 ) = (a 1 , . . . , a p ). Recall that, there exist vertices ℓ 1 , ℓ 2 , . . . , ℓ p-1 such that ℓ h is a

h -critical in T m-1 [v, ℓ 1 , • • • , ℓ h-1 ] for every 1 ≤ h < p. Since T m-1 [v] = T m [v, y i ], ℓ h is a h -critical in T m [v, y i , ℓ 1 , • • • , ℓ h-1 ] for every 1 ≤ h < p. Moreover, for every 1 ≤ h ≤ p, T m-1 [v, ℓ 1 , . . . , ℓ h-1 ] = T m [v, y i , ℓ 1 , . . . , ℓ h-1 ], and so mh(T m [v, y i , ℓ 1 , . . . , ℓ h-1 ]) = mh(T m-1 [v, ℓ 1 , . . . , ℓ h-1 ]) = a h . Therefore, λ(v, T m ) = (m, a 1 , . . . , a p ). To conclude, line 38 of Algorithm 1 precisely returns λ m = (m) ⊙ λ m-1 . Hence, λ m = λ(v, T m ).
• Case 11. Finally, we are in the case where n(m) = 1 and m / ∈ pref (λ i ) and t(λ i ) ̸ = m * for all 1 ≤ i ≤ d, i.e., T i m does not contain any m-critical vertex (line 41 of Algorithm 1). Since n(m) = 1, in T m , v has exactly 1 child v i such that mh(T i m ) = m and mh(T q m ) < m for every other child v q of v in T m . Since, there is no m-critical vertex in T m , we are in the Case 11 of Corollary 4. Thus, mh(T m ) = m. Note also that v is not m-critical since n(m) = 1. Therefore, T m has no m-critical vertex, and so λ(v, T m ) = (m). To conclude, line 41 of Algorithm 1 precisely returns λ m = (m). Hence,

λ m = λ(v, T m ).
The main result of this section follows: Theorem 6. The monotone hunter number of any tree can be computed in polynomial time.

Monotone hunter number in the red variant in trees

So far, we have investigated the Hunters and Rabbit game with the additional monotonicity property since monotone strategies are often easier to deal with. Previous works on the Hunters and Rabbit game in bipartite graphs G = (V r ∪ V w , E) have shown that studying the red variant of the Hunters and Rabbit game, i.e., when the rabbit is constrained to start in a vertex in V r , could be very fruitful. For instance, recall Lemma 5 which states that h(G) = h Vr (G) for every bipartite graph G = (V r ∪ V w , E) and which helped to get many results on the Hunters and Rabbit game [1,6,[START_REF] Gruslys | Catching a mouse on a tree[END_REF]. Therefore, it is interesting to consider the monotonicity constraint when restricted to the red variant of the Hunters and Rabbit game. This section is dedicated to this study in the case of trees. Recall that mh Vr (G) denotes the minimum number of hunters required to win against a rabbit starting at V r in a bipartite graph G = (V r ∪ V w , E) and in a monotone way. It can be checked that, in [START_REF] Gruslys | Catching a mouse on a tree[END_REF], it is actually shown that, for any tree T , mh Vr (T ) ≤ ⌈ log 2 |V (T )| 2 ⌉ (a monotone strategy with respect to V r is described in [START_REF] Gruslys | Catching a mouse on a tree[END_REF]). Therefore, the proof of Corollary 2 actually shows that: Corollary 5. There exists ε > 0 such that, for any k ∈ N, there exists a tree T with mh Vr (T ) ≥ k and mh(T ) ≥ (1 + ε)mh Vr (T ).

Therefore, Proposition 4 and Corollary 5 already show that there exist graphs G for which mh Vr (G) < mh(G). The main result of this section is that there exists an infinite family of trees T such that the difference between mh Vr (T ) and h Vr (T ) is arbitrarily large. In particular, this improves the result of Corollary 2 since mh Vr (G) ≤ mh(G) and h Vr (G) = h(G) for any graph G.

More precisely, this section is devoted to proving: Theorem 7. For every i ≥ 3, there exists a tree T such that mh Vr (T ) ≥ i and h Vr (T ) = h(T ) = 2.

Proof. In Section 5.1, we define a family (T i,2i ) i≥3 of trees such that h Vr (T i,2i ) = 2 for every i ≥ 3 (Lemma 24). Then, in Section 5.2, Lemma 27 proves that mh Vr (T i,2i ) ≥ i for every i ≥ 3.

In order to prove the Lemmas 24 and 27 below, we first need to adapt several technical lemmas and propositions above in the case of the red variant in bipartite graphs. Since the proofs of Proposition 6 and Lemma 18 (in the red variant) share many similarities with the previous, already proven, versions, we decided to postpone their proofs in the appendix.

Next proposition is an adaptation of Proposition 2 in the red variant of the game.

Proposition 6. Let S = (S 1 , . . . , S ℓ ) be a hunter strategy in a bipartite graph

G = (V r ∪ V w , E) with respect to V r . Let v ∈ V r (resp. v ∈ V w ) and 1 ≤ i ≤ ℓ.
If there exists a vertex u ∈ N (v) and a vertex x ∈ N (u) (possibly x = v) such that u / ∈ j≤i S j and x / ∈ j<i S j , then v ∈ Z 2p for every 2p ≤ i (resp. v ∈ Z 2p+1 for every 2p + 1 ≤ i).

Next lemma adapts Lemma 6 in the red variant of the game.

Lemma 18. Let G = (V r ∪ V w , E) be a bipartite graph with at least two vertices. Let S = (S 1 , . . . , S ℓ ) be a monotone hunter strategy in G with respect to V r . For any 0 ≤ p < i ≤ ⌈ℓ/2⌉, Z 2i ⊆ Z 2p and Z 2i+1 ⊆ Z 2p+1 .

Lemma 19 is a direct adaptation, in the red variant of the game, of Lemma 7. The only difference in their proofs is that, in the case of Lemma 19, Proposition 6 must be used instead of Proposition 2. Therefore, we present the proof of Lemma 19 only in the appendix. Lemma 19. Let S = (S 1 , . . . , S ℓ ) be a non-monotone winning hunter strategy in a bipartite graph G = (V r ∪ V w , E) with respect to V r . Then, there exist a vertex v ∈ V and

1 ≤ i ≤ ℓ such that v ∈ Z i-1 \ S i and v ∈ p<i S p .
Lemma 20 is a direct adaptation, in the red variant of the game, of Lemma 8. The only difference in their proofs is that, in the case of Lemma 20, Proposition 6 and Lemma 19 must be used instead of Proposition 2 and of Lemma 7. Therefore, we present the proof of Lemma 20 only in the appendix.

Lemma 20. For any non-empty connected subgraph H of a bipartite graph G = (V r ∪ V w , E), mh Vr∩V (H) (H) ≤ mh Vr (G). Moreover, if |V (H)| > 1, we get that, if there exists a monotone winning hunter strategy S = (S 1 , . . . , S ℓ ) in G with respect to V r , then there exists a monotone winning hunter strategy S ′ in H with respect to V r ∩ V (H) using at most max 1≤i≤ℓ |S i ∩ V (H)| hunters.

Since the proofs of upcoming Lemmas 21 and 22 (in the red variant) share many similarities with the proofs of Lemmas 9 and 10, respectively, we decided to postpone their proofs in the appendix.

Lemma 21. For any bipartite graph G = (V r ∪ V w , E) and any k ≥ mh Vr (G), there exists a parsimonious monotone winning hunter strategy in G with respect to V r and that uses k hunters.

Lemma 22. Let G = (V r ∪ V w , E) be a bipartite graph and S = (S 1 , . . . , S ℓ ) be a parsimonious monotone winning hunter strategy with respect to V r .

• If there exist 1 ≤ i < j ≤ ℓ such that v ∈ S i ∩ S j , then v ∈ S i+2 .

• If v ∈ V r (resp., v ∈ V w ) and there exists an odd (resp., even) integer 1 ≤ i < ℓ such that v / ∈ Z i-1 , then v / ∈ S j for every j ≥ i.

5.1

The family of trees (T i,q ) i≥3,q≥6 : definition and hunter number

In this section, we will prove that the gap between the hunter number and the monotone hunter number in the red variant of the game may be arbitrary large. More precisely, we will design an infinite family (T i ) i≥3 of trees which exhibits this behaviour. Let S k,q be the rooted tree obtained from q ≥ 6 paths of length k ≥ 3 (with k edges) by identifying an endpoint of each path into a common vertex called the root of S k,q and denoted by c. Equivalently, S k,q can be obtained from a star with root c of degree q by subdividing each edge k -1 times. From now on, let (V r , V w ) be the bipartition of V (S k,q ) and let us assume that c ∈ V r . Lemma 23. For any k, q ∈ N such that k ≥ 3 and q ≥ 6, it holds that h(S k,q ) = mh Vr (S k,q ) = 2.

Proof. The fact that h(S k,q ) > 1 comes from the characterisation of trees with hunter number one in [START_REF] Britnell | Finding a princess in a palace: a pursuit-evasion problem[END_REF]. W.l.o.g., let us suppose that the centre c of S k,q is in V r . We now prove that mh Vr (S k,q ) ≤ 2 and the result then follows from Lemma 5 and Proposition 1.

The strategy S with respect to V r and using two hunters proceeds as follows. At every odd round, the first hunter shoots at c. The second hunter considers sequentially each path P = (v 1 , . . . , v k ) of S k,q \ c by iteratively shooting at v 1 , v 2 , . . . , v k (starting by shooting v 1 at an even round).

Formally, let P 1 , . . . , P q be the q branches of c in S k,q , and let P i = (v i 1 , . . . , v i k ) for every 1 ≤ i ≤ q where v i 1 is the neighbour of c in P i . Then, the strategy S equals ({c},

{v 1 1 }, {c, v 1 2 }, {v 1 3 }, {c, v 1 4 }, . . . , {v 1 k-1 }, {c, v 1 k }, {v 2 1 }, {c, v 2 2 }, . . . , {v i j-1 }, {c, v i j }, . . . , {c, v q k }) if k is even, and S equals ({c}, {v 1 1 }, {c, v 1 2 }, {v 1 3 }, {c, v 1 4 }, . . . , {c, v 1 k-1 }, {v 1 k }, {c}, {v 2 1 }, {c, v 2 2 }, . . . , {v i-1 k }, {c}, {v i 1 } , {c, v i 2 }, . . . , {v i j-1 }, {c, v i j }, . . . , {v q k }) if k is odd.
Clearly, this is a monotone winning hunter strategy in S k,q with respect to V r .

Let us denote the strategy described in the previous proof by S 1 and let ℓ 1 be the smallest even integer greater or equal to the length of S 1 (this length equals to 1 + qk if k is even and to q(k + 1) otherwise).

The construction of the tree T i,q . For every i ≥ 2 and q ≥ 6, let T i,q be the tree recursively built as follows. First, T 1,q = S 3,q . Then, for i > 1, let us assume that T i-1,q has been defined recursively and that there exists a winning hunter strategy, of length ℓ i-1 , using 2 hunters in the red variant in T i-1,q (this holds for i -1 = 1 from the previous lemma and it will be proven to hold for every i ≥ 2 in the next lemma). Let T i,q be obtained from q vertex disjoint copies T 1 i , . . . , T q i of T i-1,q and from a vertex c i , the root of T i,q . Then, for every 1 ≤ j ≤ q, add a path P j i of length p j i (defined below) between the root c j i of T j i and c i (that is, c i and c j i are at distance p i j in T i,q ). The lengths p j i are defined recursively as follows. Let p 1 i = 2 and, for every 1 < j ≤ q, let p j i be the minimum even integer greater or equal to ℓ i-1 + 1≤k<j p k i (it will be shown in the next lemma that ℓ i equals the smallest even integer greater or equal to qℓ i-1 + 1≤j≤q jp j i ). Finally, let us assume that c i ∈ V r and note that, since p j i is even, this implies that c i , c 1 i , . . . , c q i all belong to V r .

Lemma 24. For any i ∈ N * and q ≥ 6, h Vr (T i,q ) = 2.

Proof. The fact that h Vr (T i,q ) ≥ 2 follows from Lemmas 23 and 1 and since T i,q contains S 3,q as a subgraph. We prove that h Vr (T i,q ) ≤ 2 by induction on i. More precisely, we prove that there exists a winning hunter strategy S i = (S 1 , . . . , S ℓ i ) for T i,q , with respect to V r , using 2 hunters and such that, for any j ≥ 1, if the root c i of T i,q is in Z j , then c i ∈ S j+1 . This holds for i = 1 by Lemma 23. Let i > 1 and let us assume by induction that such a strategy S i-1 has already been defined for T i-1,q .

Recall that, for all 1 ≤ j ≤ q, c j i denotes the root of the copy T j i of T i-1,q linked to the root c i of T i by a path P j i of length at least ℓ i-1 + 1≤k<j p k i . Moreover, recall that c i ∈ V r . Let us define the strategy S i as follows. It proceeds in q phases and ensures that, at every round h, if c i ∈ Z h , then c i ∈ S h+1 and that, for every round h arising after the j th phase,

(Z h \ c i ) ∩ k≤j (V (T k i ) ∪ V (P k i )) = ∅.
This implies that, at the round ℓ i , if the rabbit is still alive, it has to be on c i . But during the last phase, we ensured that the rabbit cannot reach c i . Thus, S i is a winning strategy.

Let 1 ≤ j ≤ q, let i j 0 be the last round of phase j (i 0 0 = 0) and assume by induction on j that i j 0 is even. Let us moreover assume by induction on j that (Z i j-1

0 \c i )∩ k≤j-1 (V (T k i )∪V (P k i )) = ∅.
The j th phase proceeds into two sub-phases as follows.

Very informally, in the first sub-phase, the hunters "push" the rabbit toward the subtrees T q i , then T q-1 i until the subtree T j i . Then, in the second sub-phase, the two hunters clear the subtree T j i (without the rabbit being able to leave T j i if it was there). The lengths of the paths linking the roots of the subtrees to c i (illustrated in Figure 3) guarantee that the rabbit cannot reach c i before T j i has been cleared. Formally, during the first sub-phase, the first hunter shoots at c i at every odd round. Hence, the rabbit cannot leave the component of T i,q \c i that it was occupying at the end of the (j -1) th

c 1 i-1 c 2 i-1 c 3 i-1 c 4 i-1 c 5 i-1 c 6 i-1 c i p 1 i = 2 p 2 i > ℓ i-1 + p 1 i p 3 i p 4 i p 5 i p 6 i > ℓ i-1 + 5 k=1 p k i T 1 i-1,6 T 2 i-1,6 T 3 i-1,6 T 4 i-1,6 T 5 i-1,6 T 6 i-1,6
Figure 3: The graph T i,6 . The labels on the edges are used to represent their respective lengths.

In particular, for every 2 ≤ j ≤ 6, we have that p j i > 1≤k≤j-1 p k i + ℓ i-1 , where p 1 i = 2 and ℓ i-1 is equal to the number of rounds needed to clear any copy of the T i-1,6 graph.

phase. During the same first sub-phase, the second hunter sequentially shoots the vertices of P q i , P q-1 i , . . . , P j i in this order and from the neighbours of c i to the vertices c q i , c q-1 i , . . . , c j i . More precisely, for every j ≤ k ≤ q, let P

k i = (v k 0 = c i , v k 1 , . . . , v k p k i = c k i ).
The second hunter starts at round i j 0 + 2 by shooting v q 1 and then sequentially shoots v q 2 , v q 3 , . . . , v q p q i = c q i , v q-1 1 , v q-1 2 , . . . , v q-1 p q-1 i = c q-1 i , v q-2 1 , . . . , c j i . Note that, after the round when the second hunter shoots at c q i , if the rabbit was occupying a vertex in T q i ∪ P q i at the beginning of the j th phase, then it must occupy a vertex at distance at least p q i from c i . Similarly, after the round when the second hunter shoots at c q-1 i , if the rabbit was occupying a vertex in T q-1 i ∪ P q-1 i at the beginning of the j th phase, then it must occupy a vertex at distance at least p q-1 i from c i . Moreover, if the rabbit was occupying a vertex in T q i ∪ P q i at the beginning of the j th phase, then it must occupy a vertex at distance at least p q i -p q-1 i from c i (since there have been p q-1 i rounds between the shots of c q i and of c q-1 i

). With similar arguments, and by the definition of p k i for j < k ≤ q, after the round when the second hunter shoots at c j i , the rabbit must be at distance at least ℓ i-1 from c i if it was occupying a vertex of j<k≤q T k i ∪ P k i at the end of the (j -1) th phase. Moreover, the rabbit cannot occupy any vertex in k≤j-1 (V (T k i )∪V (P k i )) since the first hunter is always shooting c i during the odd rounds. Finally, the rabbit cannot occupy a vertex in P j i since the second hunter has just shot sequentially the vertices v j 1 , v j 2 , . . . , v j p j i = c j i . Then, the second sub-phase of phase j starts, during which both hunters execute the strategy S i-1 in the subtree T j i (the shot of c j i by the second hunter during the first sub-phase, i.e., the last round of the first sub-phase, may be used as the first round of S i-1 ). By the induction hypothesis, the strategy S i-1 ensures that the rabbit cannot reach the root c j i of T j i without being shot immediately (if c j i is in Z h for some round h, then c j i ∈ S h+1 ). Thus, if the rabbit was cleaned according to any monotone hunter strategy, there must be some other branches of r whose vertices have never been shot.

Lemma 26. Let T = (V r ∪ V w , E) be a tree rooted in some vertex c ∈ V r with neighbours N (c) = {v 1 , . . . , v d }, d ≥ 2k. For every 1 ≤ i ≤ d, let B i be the branch at c containing v i and assume that |V (B i )| ≥ 2. Let S = (S 1 . . . , S ℓ ) be any parsimonious monotone winning hunter strategy in T with respect to V r using at most k -1 hunters. Let 1 ≤ j ≤ ℓ be the smallest index such that there exists an 1 ≤ α ≤ d such that V (B α ) is definitively cleaned at the round j. Then, there exist

1 ≤ β < γ ≤ d, α / ∈ {β, γ}, such that ( 1≤i≤j S i ) ∩ V (B β ) = ∅ and ( 1≤i≤j S i ) ∩ V (B γ ) = ∅.
Proof. Let j and α be defined as in the statement and, w.l.o.g., let us assume that α = 1. That is, the branch B 1 is definitively cleaned at round j, and no other branch has been definitively cleaned before round j. Claim 4. For any vertex v ∈ V (T ) such that there exist a least 3 branches at v with at least two vertices, let q be the minimum index such that such a branch B is definitively cleaned at round q. Then, S q ∩ V (B) ̸ = ∅.

Proof of Claim. By the minimality of q, either Z q-1 ∩ V (B) ̸ = ∅ or S q ∩ V (B) ̸ = ∅. If S q ∩ V (B) ̸ = ∅, then the statement holds. Thus, let us assume that S q ∩ V (B) = ∅. Then Z q-1 ∩ V (B) ̸ = ∅, as otherwise B would have been definitively cleaned at round prior to q. Let x ∈ Z q-1 ∩ V (B). Since x / ∈ S q , N B (x) ⊆ Z q . Since B is connected and contains at least two vertices, we have that N B (x) ̸ = ∅. Thus Z q ∩ V (B) ̸ = ∅, which contradicts that B is definitively cleaned at round q. ⋄ It follows by Claim 4 that V (B 1 ) ∩ S j ̸ = ∅. Thus, since |S j | ≤ k -1, there are at most k -2 branches at c, other than B 1 , which can be shot during the round j. W.l.o.g., let us assume that B 2 , . . . , B k-1 are the branches at c that are also shot during round j. That is, S j ⊆ {c} ∪ 1≤h<k V (B h ).

For purpose of contradiction, let us assume that there exists at most one branch, w.l.o.g., say B k , such that 1≤i≤j S i ∩ V (B k ) = ∅. Hence, we assume that for every k < h ≤ d, there exists j h < j and x h ∈ V (B h ) ∩ S j h .

For any k < h ≤ d, let us denote by j * h the minimum index such that B h is definitively cleaned at round j * h . By Claim 4, for any k < h ≤ d, S j * h ∩ V (B h ) ̸ = ∅. Thus, since V (B h ) ∩ S j = ∅ for every k < h ≤ d, we have that j * h ̸ = j for every k < h ≤ d. In particular, it follows by the minimality of j that j * h > j. Let us prove that, for some k < h ≤ d, there exists a vertex y h ∈ Z j-1 ∩ V (B h ). Towards a contradiction, let us assume that for every k < h ≤ d, we have Z

j-1 ∩ V (B h ) = ∅. Recall that S j * h ∩ V (B h ) ̸ = ∅, and let z ∈ S j * h ∩ V (B h ) (for some k < h ≤ d). Since S is parsimonious, z ∈ Z j * h -1 .
Thus, there exists a rabbit trajectory (r 0 , . . . , r j

* h -1 = z) such that r q / ∈ S q+1 for every 0 ≤ q < j * h -1. Moreover, r j-1 / ∈ V (B h ), since Z j-1 ∩V (B h ) = ∅.
Since a rabbit trajectory is a walk, and any walk between a vertex from

V \ V (B h ) to a vertex of V (B h ) contains c, there exists j -1 ≤ m < j * h -1 such that r m = c. Since r m / ∈ S m+1 , it follows that v 1 ∈ Z m+1
, where v 1 is the neighbour of c in B 1 . This contradicts that B 1 is definitively cleaned at round j. Hence, there exists some vertex y h ∈ Z j-1 ∩ V (B h ).

Finally, for every k < h ≤ d, let us choose the vertices x h and y h , such that x h ∈ V (B h ) ∩ 1≤i<j S i and y h ∈ Z j-1 ∩ V (B h ) and the distance between x h and y h is minimised. Note that y h / ∈ 1≤i<j S i , since, otherwise, S would not be monotone as y h ∈ Z j-1 \ S j . Since S j ∩ V (B h ) = ∅ and by Lemma 25, we obtain that x h y h ∈ E(B h ). Thus, x h ∈ Z j for every k < h ≤ d. Since S is a monotone strategy, x h ∈ S j h ∩ Z j (with j h < j), that x h ∈ S j+1 for every k < h ≤ d. However, d ≥ 2k and so |S j+1 | ≥ k, a contradiction. z s . Note also that if w s = γ s , then the neighbour of γ s in B s 1 is in Z zs-1 , a contradiction since z s > j 1 and B s 1 is definitively cleaned at round j s ≤ j 1 . Hence, w s ̸ = γ s and so w s ∈ V (B s 3 ). Similarly, there exists a vertex w ′ s ∈ N (w s ) ∩ Z zs-3 \ S zs-2 such that w ′ s has not been cleaned before round z s -1. Hence, we have two adjacent vertices w s and w ′ s in N [B s 3 ] that have never been shot before the round z s -1. Thus, since {w s , w ′ s } ∩ V r ̸ = ∅, there exists a rabbit trajectory (. . . , w s , w ′ s , w s , w ′ s , . . . ) consisting in oscillating between w s and w ′ s which implies that {w s , w ′ s } ∩ Z j ̸ = ∅ for all j < z s . In particular, since j 1 -1 < z s , there exists a vertex y ′ s ∈ N [B s 3 ] ∩ Z j 1 -1 . For every 1 ≤ s ≤ 2i, let x s and y s be two vertices in V (H s ) such that x s ∈ V (H s ) ∩ 1≤q≤j 1 S q , y s ∈ V (H s ) ∩ Z j 1 -1 and the distance between x s and y s is minimised. Let P = {s | 1 ≤ s ≤ 2i, y s ∈ S j 1 ∪ S j 1 +1 or x s ∈ S j 1 ∪ S j 1 +1 }, i.e. P is the set of indices s such that at least one of y s or x s is shot during the round j 1 or j 1 + 1. Since S 2i uses at most i -1 hunters, we have that |P| ≤ 2(i -1). Thus, let 1 ≤ s * ≤ 2i such that s * / ∈ P, i.e., x s * , y s * / ∈ S j 1 ∪ S j 1 +1 . It follows from Lemma 25 that x s * y s * ∈ E(T 2i,d ). Since y s * ∈ Z j 2i -1 \ S j 1 , we have that that x s * ∈ Z j 1 . However, x s * ∈ 1≤q≤j 1 S q \ S j 1 +1 and so, x s * is recontaminated, contradicting the monotonicity of S 2i .

Kernelization by vertex cover

Let us first remind some of the basic definitions regarding parameterised complexity. An instance of a parameterised version Π p of a decision problem Π is a pair (I, t), where I is an instance of Π and t is a non-negative integer, called a parameter, associated with I. We say that Π p is fixed-parameter tractable (FPT) if there exists an algorithm (called as FPT algorithm) that, given an instance (I, t) of Π p , solves it in time f (t) • |I| O (1) , where f is any computable function of t.

Definition 2 (Equivalent Instances). Let Π 1 and Π 2 be two parameterised problems. Two instances, (I, t) ∈ Π 1 and (I ′ , t ′ ) ∈ Π 2 , are equivalent when (I, t) is a Yes-instance if and only if (I ′ , t ′ ) is a Yes-instance.

A parameterised (decision) problem Π p admits a kernel of size f (t), for some function f that depends only on t, if the following is true: there exists an algorithm (called a kernelization algorithm) that, given as input an instance (I, t) of Π p , runs in (|I| + t) O (1) time and outputs an equivalent instance (I ′ , t ′ ) of Π p such that |I ′ | ≤ f (t) and t ′ ≤ t. If the function f is polynomial, then the problem is said to admit a polynomial kernel. It is well-known that a decidable parameterised problem is FPT if and only if it admits a kernel [START_REF] Cygan | Parameterized Algorithms[END_REF].

Recall that a vertex cover of a graph G is any set U ⊆ V (G) such that for every edge uv ∈ E(G), U ∩ {u, v} ̸ = ∅. The order of a minimum size vertex cover of G is usually referred to as the vertex cover number of G and denoted by vc(G). In what follows, we consider the Hunters and Rabbit Problem parameterised by the vertex cover number. That is, an instance ((G, k), t) is defined by an input (G, k) where the problem aims at deciding whether h(G) ≤ k and the parameter t is any upper bound on vc(G).

First, we have the following observation. Proof. Let U be a vertex cover in G and I be the independent set V (G) \ U . The hunter player can win simply by shooting all the vertices of U twice. If the rabbit starts at a vertex u ∈ U , then it gets shot in the first round. Otherwise, the rabbit was on a vertex v ∈ I, and then it has to move to a vertex in U (since I is an independent set) that is, Z 1 = U and then, the rabbit is shot by a hunter in the next round. Finally, note that this strategy is also monotone.

Let U be a vertex cover of size t ≥ vc(G) of G and I be the independent set V (G) \ U . For each subset S ⊆ U , we define the following equivalence class: C S = {v | v ∈ I and N (v) = S}. Next, we have the following crucial lemma.

Lemma 28. Let G = (V, E) be a connected graph, U ⊆ V be a vertex cover of G, k ≥ 1 and let S ⊆ U be such that |C S | > k + 1. Let C S = {v 1 , . . . , v q }. Then, h(G) ≤ k (resp., mh(G) ≤ k) if and only if h(G[V \ {v k+2 , . . . , v q }]) ≤ k (resp., mh(G[V \ {v k+2 , . . . , v q }]) ≤ k).

Proof. By Lemma 1, h(G[V \ {v k+2 , . . . , v q }]) ≤ h(G). Similarly, due to Lemma 8, mh(G[V \ {v k+2 , . . . , v q }]) ≤ mh(G). So, it only remains to prove that, if h(G) > k (resp., mh(G) > k), then h(G[V \ {v k+2 , . . . , v q }]) > k (resp., mh(G[V \ {v k+2 , . . . , v q }]) > k). Let H = G[V \ {v k+2 , . . . , v q }] and let X = {v 1 , . . . , v k+1 } (i.e., X = V (H) ∩ C S ).

In the following we show that if h(G) > k (resp., mh(G) > k), then h(H) > k (resp., mh(H) > k). To this end, we establish that if the rabbit has a winning strategy in G against k hunters, then the rabbit has a winning strategy in H against k hunters.

(1) h(G) > k =⇒ h(H) > k: Let S = (S 1 , S 2 , . . . , S ℓ ) be any hunter strategy (not necessarily winning) in H using at most k hunters. Then, S is a hunter strategy (not necessarily winning) in G using at most k hunters. Since h(G) > k, there exists a rabbit-trajectory R ′ = (r ′ 0 , r ′ 1 , . . . , r ′ ℓ-1 ) in G such that r ′ i / ∈ S i+1 for every 0 ≤ i < ℓ. Let R = (r 0 , . . . , r ℓ-1 ) be such that, for every 0 ≤ i < ℓ, let r i = r ′ i if r ′ i ∈ V (H) and, otherwise, let r i be any vertex of X \ S i+1 (such a vertex exists since |S i+1 | ≤ k and |X| > k). Note that r ′ i ̸ = r i only if r ′ i / ∈ V (H) and therefore r ′ i ∈ C S . This implies that, if r ′ i / ∈ V (H), then r ′ i-1 , r ′ i+1 ∈ S ⊂ V (H) (since N (r ′ i ) = S). Therefore, r i-1 = r ′ i-1 and r i+1 = r ′ i+1 and r i-1 , r i+1 ∈ N H (r i ) (since r i ∈ X and so N G (r i ) = N H (r i ) = S). Therefore, R is a rabbit trajectory in H and, by construction, r i / ∈ S i+1 for every 0 ≤ i < ℓ. Hence, S is not a winning hunter strategy. Therefore, h(H) > k.

(2) mh(G) > k =⇒ mh(H) > k: Let S = (S 1 , S 2 , . . . , S ℓ ) be any hunter strategy (not necessarily winning) in H using at most k hunters. Then, S is a hunter strategy (not necessarily winning) in G using at most k hunters. Since mh(G) > k, for every hunter strategy S in G using at most k hunters, there is a rabbit trajectory R ′ that either is a winning rabbit trajectory (the rabbit never gets shot) or recontaminates a vertex (rabbit may be shot at a later round). Now, let R be built from R ′ similarly to the previous case. If the rabbit never gets shot in R ′ , then due to the arguments presented in (1), the rabbit evades getting shot in R as well. Hence, we assume that the rabbit gets shot in R ′ , during, say, a round p, but recontaminates a vertex, say x, during a round p ′ < p. Since only vertices of H can be shot in the hunter strategy S, only the vertices of H can be recontaminated by R ′ (recall Lemma 7). Hence x ∈ V (H). Therefore, x gets recontaminated by R in H as well. Thus, mh(H) > k.

Finally, we present our kernelization result.

Theorem 9. The problem that takes an n-node connected graph G and an integer k ≥ 1 as inputs and decides whether h(G) ≤ k (resp., mh(G) ≤ k), parameterised by any upper bound t on vc(G), admits a kernel of size at most 4 t (t + 1) + 2t. Moreover, this problem can be solved in FPT time (4 t (t + 1) + 2t) t+1 • n O (1) .

Proof. The kernelization proceeds as follows. First, if k > t, then answer that h(G) ≤ mh(G) ≤ k (this is correct by Proposition 7). Otherwise, let U be a vertex cover of size at most 2t of G (which can be computed in time O(tn) by classical 2-approximation for vertex cover using maximal matching [START_REF] Williamson | The Design of Approximation Algorithms[END_REF]). Let H be the graph obtained from G as follows. Proposition 7). Hence, the above algorithm is the desired kernelization algorithm. Finally, applying the XP-algorithm [1], it can be decided in time |V (H)| k+1 whether h(H) ≤ k. Since, by Proposition 7, k ≤ t, this gives the FPT algorithm that decides whether h(G) ≤ k (resp., mh(G) ≤ k) in time (4 t (t + 1) + 2t) t+1 + n O (1) .

Some Future Directions

In this paper, we studied the Hunters and Rabbit game by defining the notion of monotonicity for this game. Using this notion of monotonicity, we characterised the monotone hunter number for various classes of graphs. Moreover, we established that, unlike several graph searching games, the monotonicity helps in this game, i.e., the h(G) can be arbitrary smaller than mh(G). Furthermore, our results also establish that the monotonic hunter number does not behave "nicely" with taking minors and subdivisions, unlike its other counterparts such as pathwidth and treewidth.

There are still several challenging open questions in this area. The most important among them is the computational complexity of Hunters and Rabbit. Although our results establish that computing mh(G) is NP-hard, the computational complexity of computing/deciding h(G) remains open, even if G is restricted to be a tree graph.

We also established that both Hunters and Rabbit, as well as its monotone variant, are FPT parameterised by vc(G) by designing exponential kernels. It is not difficult to see that both of these variants admit AND Composition parameterised by the solution size (by taking the disjoint union of the instances). Thus, since computing mh(G) is NP-hard and pw(G) ≤ mh(G) ≤ pw(G) + 1, it is unlikely for Monotone Hunters and Rabbit parameterised by k + pw(G) to admit a polynomial compression. Note that the same cannot be argued about Hunters and Rabbit since it is not yet proved to be NP-hard. Moreover, since mh(G) is closely related to pw(G) and pathwidth admits a polynomial kernel with respect to vc(G) [START_REF] Chapelle | Treewidth and pathwidth parameterized by the vertex cover number[END_REF], it might be interesting to see if deciding mh(G) ≤ k (resp., h(G) ≤ k) also admits a polynomial kernel when parameterised by vc(G). Moreover, another interesting research direction is to study the parameterised complexity of both these games by considering parameters such as solution size, treewidth, and pathwidth.

Finally, we propose some open questions concerning the computation of h(G) for various graph classes including trees, cographs, and interval graphs. Specifically, it will be interesting to design a polynomial time algorithm, similar to Algorithm 1, to compute h(T ) for a tree T , a question that was already proposed in [1]. The natural way that one could tackle this question is through the notion of monotonicity, which we defined and studied in this paper. Unfortunately, Theorem 7 implies that such an approach will not work. This means that a positive answer to this question (if any) would require the introduction of new tools and techniques. Moreover, it would be interesting to know the monotone hunter number of grids.

• If there exist 1 ≤ i < j ≤ ℓ such that v ∈ S i ∩ S j , then v ∈ S i+2 .

• If v ∈ V r (resp., v ∈ V w ) and there exists an odd (resp., even) integer 1 ≤ i < ℓ such that v / ∈ Z i-1 , then v / ∈ S j for every j ≥ i.

Proof. First, for purpose of contradiction, let us assume that v ∈ S i ∩ S j and v / ∈ S i+2 with i < j. Note that, since G is bipartite, that S is a parsimonious strategy with respect to V r and S i ∩ S j ̸ = ∅, thus i and j must have the same parity and so, j ≥ i + 4 (because v / ∈ S i+2 ). Since S is parsimonious, v ∈ Z i-1 ∩ Z j-1 . Thus, by Lemma 18, v ∈ Z i+1 \ S i+2 and v ∈ S i , contradicting the monotonicity of S. Hence, the first statement holds.

Let us now prove the second statement. Let us assume now that v ∈ V r (the case v ∈ V w can be handled similarly). If v / ∈ Z i-1 for any odd 1 ≤ i < ℓ, then v / ∈ Z j-1 for any odd i ≤ j ≤ ℓ by Lemma 18. Therefore, since S is parsimonious, v / ∈ S j for any odd i ≤ j ≤ ℓ. Moreover, since G is bipartite and that S is a parsimonious strategy with respect to V r , for any even 1 ≤ j ≤ ℓ, v / ∈ S j .

Figure 1 :

 1 Figure1: Example of a bipartite graph (where V r = {a, c, e, g} corresponds to the red part of the bipartition, illustrated by the red vertices in the figures) and of a parsimonious winning strategy with respect to V r , such that no vertex in {a, e, g} is ever shot. Each subfigure depicts the situation at the end of the corresponding round. In round 0, the rabbit occupies any vertex in {a, c, e, g}. Then, in round 1, the hunter shoots the vertex c (depicted as the cross over the corresponding vertex of subfigure (b)) and the rabbit moves to one of the vertices in {b, d, f }. The game continues until the end of round 6 (subfigure (g)), at which point the hunter is sure to shoot the rabbit in vertex b. Formally, we have S = ({c}, {d}, {c}, {f }, {c}, {b}) and Z(S) = ({a, c, e, g}, {b, d, f }, {a, c}, {b}, {a, c}, {b}, ∅).

  be partitioned into a set C inducing an inclusion-maximal clique and a set I inducing an independent set. Note that given a split graph G, a partition (C, I) of V (G) can be computed in linear time[START_REF] Hammer | The splittance of a graph[END_REF]. In what follows, we denote a split graph by G = (C ∪ I, E) where C induces an inclusion-maximal clique and I induces an independent set. Let us recall the following result on the pathwidth of split graphs: Lemma 11. [17] Let G = (C ∪ I, E) be a split graph. Then, |C| -1 ≤ pw(G) ≤ |C|. First, we have the following easy observation. Proposition 3. Let G = (C ∪ I, E) be a split graph. Then, |C| -1 ≤ h(G) ≤ mh(G) ≤ |C|. Proof. By Lemma 1, h(G) ≥ h(G[C]), and by Lemma 4, h(G[C]) ≥ δ(G[C]) = |C| -1. Therefore, h(G) ≥ |C|-1. Moreover, the hunter strategy that consists in shooting to all the vertices of C twice is clearly a monotone winning hunter strategy in G. Hence, h(G) ≤ mh(G) ≤ |C|.

Theorem 2 .

 2 Let G = (C ∪ I, E) be a split graph. Then, h(G) = |C| if and only if for every two distinct vertices x, y ∈ C, there exists a vertex z ∈ N I (x) ∩ N I (y). Otherwise, h(G) = |C| -1.

  2.a r 2 ∈ N I (y) : This case is similar to Case 1. Since N I (x) ∩ N I (y) = ∅, r 3 ∈ C \ {x}. As S 4 = C \ {x}, r 3 ∈ S 4 , and therefore, S is a winning hunter strategy. 2.b r 2 = x : In this case, if r 3 / ∈ S 4 , then r 3 ∈ N I (x). Therefore, similarly to previous arguments, r 4 ∈ C \ {y}. Since S 5 = C \ {y}, S is a winning hunter strategy. This completes the proof. The above characterisation allows us to show that the hunter number and the pathwidth of split graphs coincide. Corollary 3. For any split graph G = (C ∪ I, E), h(G) = pw(G). Proof. If |C| = 1 and I = ∅, then pw(G) = h(G) = 0. If |C| = 1 and I ̸ = ∅, then pw(G) = h(G) = 1. Let us now assume that |C| > 1.

  there is no bag containing both x and z, contradicting the definition of a path-decomposition. Second, let us assume that h(G) = |C| -1. By Theorem 2, there exist distinct vertices x, y ∈ C such that N I (x) ∩ N I (y) = ∅. Let us prove that, in that case, pw(G) = |C| -1. Let N I (x) = {x 1 , . . . , x m } and I \ N I (x) = {y 1 , . . . , y t }. Then, (x 1 ∪ (C \ {y}), . . . , x m ∪ (C \ {y}), C, y 1 ∪ (C \ {x}), . . . , y t ∪ (C \ {x})) is a path decomposition of G with width |C| -1 and, since pw(G) ≥ |C| -1 by Lemma 11, we get that pw(G) = |C| -1.

Theorem 3 .

 3 Let G = (C ∪ I, E) be a split graph. Then, mh(G) = |C| -1 if and only if there exists a simplicial vertex in C. Otherwise, mh(G) = |C|. Proof. Note first that if there is no simplicial vertex in C, then by Lemma 12, mh(G) ≥ |C| and so, by Proposition 3, mh(G) = |C|. Otherwise, if there exists a simplicial vertex v ∈ C, then S = (C \ v, C \ v) is a monotone winning hunter strategy in G.

  ) and S B ∪ V (A) are both monotone winning hunter strategies in G. Therefore, mh(G) ≤ min(mh(A) + |V (B)|, |V (A)| + mh(B)).

  is a monotone winning hunter strategy in G[A] using k-|V (B)| hunters. Hence, k-|V (B)| ≥ mh(A) which concludes the proof.

Corollary 4 .

 4 Let T be a rooted tree, u ∈ V (T ) and let u 1 , . . . , u d be the d children of u in T . Let us order the children of u such that k = mh(T [u 1 ]) ≥ mh(T [u 2 ]) ≥ . . . mh(T [u d ]). so, by Lemma 8, mh(T [z]) ≤ mh(T [u j ]) < k. Therefore, there is no vertex w ∈ V (T [u]) such that w has 3 branches that have monotone hunter number at least k. Hence, by Lemma 15, mh(T [u]) ≤ k. By Lemma 8 and because mh(T [u 1 ]) = k, mh(T [u]) = k. 9. If k > 1, mh(T [u 1 ]) = k and (mh(T [u 2 ]) < k or d = 1) and T [u 1 ] contains a k-critical vertex x and mh(T [u, x]) = k, then, x has 3 branches with monotone hunter number at least k in T [u]. Therefore, by Lemma 15, mh(T [u]) ≥ k + 1. Finally, by Lemma 16, mh(T [u]) ≤ k + 1 and so mh(T [u]) = k + 1. 10. If k > 1, mh(T [u 1 ]) = k and (mh(T [u 2 ]) < k or d = 1) and T [u 1 ] contains a k-critical vertex x and mh(T [u, x]) < k, then, there do not exist three branches at u with monotone hunter number at least k. Let w be any vertex of T [u] \ {u}. Let us assume first that w is not k-critical. Thus, there is at most one branch at w in T [w] with monotone hunter number k. Since there is only one other branch left for w in T [u] (the one containing its parent), there do not exist three branches at w in T [u] with monotone hunter number at least k. Let us assume now that w is k-critical. Thus, w ∈ V (T [u 1 ]) since mh(T [u j ]) < k for any 2 ≤ j ≤ d. Note that w = x. Indeed, towards contradiction, let us assume that w ̸ = x. Then, the branch at w containing its parent in T [u 1 ] contains T [x] as a subgraph and/or the branch at x containing its parent in T [u 1 ] contains T [w]. Thus, in every case, due to Lemma 8, there exists a vertex in T [u 1 ] that has 3 branches having monotone hunter number k, each. Therefore, by Lemma 15, mh(T [u 1 ]) = k + 1, which is a contradiction to the definition of k. To sum up, for any vertex w ∈ V (T [u]) \ {x}, there exist at most two branches at w that require monotone hunter number at least k. Let us recall that, by hypothesis, mh(T [u, x]) < k. Hence, there are only two branches at x that have monotone hunter number at least k (otherwise, by Lemma 15 and Lemma 8, k < mh(T [x]) ≤ mh(T [u 1 ]), a contradiction). Therefore, there is no vertex w in T [u] such that there exist at least 3 branches at w, each having monotone hunter number at least k. Thus, by Lemma 15, mh(T [u]) ≤ k and by Lemma 8, mh(T [u]) ≥ mh(T [u 1 ]) ≥ k. 11. If k > 1, mh(T [u 1 ]) = k and (mh(T [v 2 ]) < k or d = 1), and T [u 1 ] does not contain any k-critical vertex, then there is no vertex in T [u] that has 3 branches that require monotone hunter number at least k (as in previous case). Therefore, by Lemma 15, mh(T [u]) ≤ k and by Lemma 8, mh(T [u]) ≥ mh(T [u 1 ]) ≥ k, and so, mh(T [u]) = k.

  else if m > 1 then 23: // Invariant/intuition: at this step, λ = λ(v, T m-1 ) where T m-1 is the subtree obtained from T by removing the substrees T [w] such that w ̸ = v and mh(T [w]) ≥ m. 24: //Case 6: at least three children of v have m or m * in their label 25: if n(m) ≥ 3 then 26: λ ← (m + 1); 27: //Case 7: two children of v have m or m * in their label and at least one of their subtrees contains a m-critical vertex 28:

  and λ contains m or m * then 35:

  and λ contains neither m nor m * then 38: λ ← (m) ⊙ λ; 39: //Case 11: one child of v has m or m * in its label. Moreover, its subtree does not contain an m-critical vertex 40: else if n(m) = 1 and, ∀1 ≤ i ≤ d, m / ∈ pref (λ i ) and t(λ i ) ̸ = m * then 41:λ ← (m);

Proposition 7 .

 7 For any connected graph G, h(G) ≤ mh(G) ≤ vc(G).

  x 1 , . . . , x p ] denote the subtree obtained from T [u] after the vertices of i≤p V (T [x i ]) have been removed. Finally, for k ≥ 2, a vertex x ∈ V (T ) is k-critical if and only if mh(T [x]) = k and there exist two children v 1 and v 2 of x in T such that mh(T[v 1 ]) = mh(T [v 2 ]) = k.In the case k = 1, we will say that a vertex x is 1-critical if and only if mh(T [x]) = 1 and there exists a unique child v of x such that mh(T [v]) = 1.Remark: Let us recall that mh(T [w]) ≥ 1 if T [w] contains at least one edge, i.e., w has at least one child. Therefore, if a vertex w is 1-critical in T [w], then T [w] is a star centred in the child w ′ of w such that mh(T [w ′ ]) = 1, i.e., w ′ is the only vertex of T [w] that has degree at least 2. Moreover, if a vertex w is not 1-critical and mh(T [w]) = 1, then T [w] is star rooted in w, i.e., w is the only vertex that may have degree greater than 1 in T [w] (w may also have degree 1 when |V (T [w])| = 2).The next lemma is used through out the proof of Corollary 4 and Lemma 17.

Lemma 16. Let T be any tree rooted in a vertex v ∈ V (T ). Let k = max 1≤i≤d {mh(T [v i ]}, where v 1 , . . . , v d are the children of v in T . For any vertex w ∈ V (T ), there is at most 1 branch at w in T that has monotone hunter number k + 1. Moreover, mh(T ) ≤ k + 1.

Proof. Note first that, by definition of k, there is no branch at v that has monotone hunter number k + 1. Hence, let w be any vertex V (T ) \ {v} and let us denote by x the child of v such that w ∈ V (T [x]). By definition of k, mh(T [x]) ≤ k. For any child z of w, T [z] is a subtree of T [x]. Thus, by

Lemma 8, mh(T [z]

  For every S ⊆ U , if |C Moreover, |V (H)| = |U |+ S⊆U |C S ∩V (H)| ≤ 2t+2 2t (k +1) ≤ 4 t (t+1)+2t (the last inequality holds by

S | > k + 1, then remove |C S | -(k + 1) vertices from C S . By Lemma 28 (applied iteratively for each S ⊆ U ), h(G) ≤ k (resp., mh(G) ≤ k) if and only if h(H) ≤ k (resp., mh(H) ≤ k).

We design a dynamic programming algorithm to compute the monotone hunter number of a tree T . Let us first root T at any vertex r ∈ V (T ). Let T [u] denote the subtree of T induced

This work is partially funded by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004) and the ANR Digraphs and ERC grant titled PARAPATH.

 (3,2,1). Observe that mh(T 1 [ℓ 1 1 ]) = 3 and that ℓ 1 1 is 3-critical since there are two branches attached to ℓ 1 1 , both of monotone hunter number equal to 3. Similarly, mh(T 1 [ℓ 1 2 ]) = 2 and ℓ 1 3 is 2-critical. Finally, the graph T 1 [u 1 , ℓ 1 1 , ℓ 2 1 ] is the star on 3 vertices, centred in u 1 . Adding any number of leaves to attached to u 1 would result in a tree T ′ 1 such that λ(v, T ′ 1 [v]) = (3, 2, 1). Adding one leaf u 2 attached to v would result in a tree T 2 such that λ(u 2 , T 2 [u 2 ]) = (3, 2, 1 * ). Adding a leaf u ′ attached to u 2 would result in a tree T ′ 2 with λ(u ′ , T ′ 2 [u ′ ]) = (4).

Examples. Let us exemplify the above definition. In the following examples, we start from two trees T 1 and T 2 whose roots have "almost" the same labels and show that adding one vertex adjacent to their root may lead to two new trees whose roots have "very different" labels. In particular, this illustrates the importance of the presence of a star on the last integer of a label. First, let T 1 be a tree rooted in a vertex u 1 with the label λ(u 1 , T 1 ) = (a 1 , a 2 , a 3 ) = (3, 2, 1). In Figure 2 we provide an illustration of one such tree. Since a 1 = 3, then mh(T 1 [u 1 ]) = 3 and there exists a vertex ℓ 1 1 ∈ T 1 [u 1 ] that is 3-critical. Moreover, mh(T 1 [u 1 , ℓ 1 1 ]) = a 2 = 2 and there exists a vertex ℓ 1 2 ∈ T 1 [u 1 , ℓ 1 1 ] that is 2-critical. Finally, mh(T 1 [u 1 , ℓ 1 1 , ℓ 1 2 ]) = a 3 = 1 and since a 3 is not marked with a star, there is no 1-critical vertex in T 1 [u 1 , ℓ 1 1 , ℓ 1 2 ]. By previous remarks, T 1 [u 1 , ℓ 1 1 , ℓ 1 2 ] is a star centred in u 1 and ℓ 1 3 = u 1 (moreover, the star contains at least 2 vertices since mh(T 1 [u 1 , ℓ 1 1 , ℓ 1 2 ]) > 0). Let T ′ 1 be the tree obtained from T 1 by adding a vertex u (the root of T ′ 1 ) adjacent to u 1 . Note that, ℓ 1 1 (resp., ℓ 1 2 ) is still 3-critical (resp., 2-critical) in

] is a star (containing at least 3 vertices) centred in u 1 , and so

Second, let T 2 be a tree rooted at u 2 with the label λ(u 2 , T 2 ) = (a 1 , a 2 , a 3 ) = (3, 2, 1 * ). Similarly to the previous example, there exist ℓ 2 1 and ℓ 2 2 that are the 3-critical vertex of T 2 [u 1 ] and the 2-critical vertex of T 2 [u 1 , ℓ 2 1 ], respectively. Moreover, since a 3 is marked with a star, there exists a 1-critical vertex

Let us recall that by definition of a label, ℓ 2 3 = u 2 , and so

] is a star with at least 3 vertices centred in the only child of u 2 . Let T ′ 2 be the tree obtained from T 2 by adding a vertex u ′ (the root of

Proof. Towards contradiction, let us assume that there exists a tree T rooted in v ∈ V (T ) such that v has label λ = (a 1 , a 2 ) = (1, 0) in T [v]. Then, by the definition of the labelling, there occupying a vertex of T j i at the beginning of the second sub-phase, then the rabbit cannot leave this subtree and it is eventually shot. Otherwise, because S i-1 has length at most ℓ i-1 , the rabbit cannot reach c i before the last shots of the hunters in T j i . Let i j 0 be the last round of the phase. Note that i j 0 is even since p h i and ℓ h are even for all 1 ≤ h ≤ q, and i j-1 0 is even by induction. Then, the j th phase ends after the (even) round i j 0 and with the desired property: the rabbit can only occupy a vertex in

To conclude, note that S i is winning in at most qℓ i-1 + 1≤j≤q jp j i rounds since each phase j proceeds in ℓ i-1 + j≤k≤q p k i rounds.

Theorem 8. For any tree T , there exists a subdivision T ′ of T such that h(T ′ ) ≤ 2.

Proof. Let q be the maximum degree of T . Let r be any vertex of T , and let i be the eccentricity of r (i.e., the largest distance between r and some vertex of T ). Then, there exists a subdivision T ′ of T , that is a subgraph of T i,max{6,q} (each vertex of T being "mapped" to a vertex of degree at least 3 of T i,max{6,q} and r being "mapped" to the root of T i,max{6,q} ). By Lemmas 1, 5 and 24, h(T ′ ) ≤ 2.

Corollary 6. For every ℓ ≥ 0, there exists a tree T and a subdivision T ′ of T such that h(T ) -h(T ′ ) ≥ ℓ.

Non monotonicity of the red variant in trees

Before proving Lemma 27, we need some additional results. Note that the next lemma is the adaptation of Proposition 5 for the red variant of the game.

Lemma 25. Let G = (V r ∪ V w , E) be any bipartite graph and H be a connected subgraph of G.

Let S = (S 1 , . . . , S ℓ ) be any parsimonious monotone winning hunter strategy in G with respect to V r . Let 1 ≤ i ≤ ℓ and x, y ∈ V (H) such that x ∈ j<i S j and y ∈ Z i-1 and minimising the distance between such x and y in H. If x, y / ∈ S i , then xy ∈ E(H).

Proof. Note first that if x = y, then S is non-monotone since y = x ∈ ( j<i S j ∩ Z i-1 ) \ S i . Hence, we may assume that x ̸ = y. Let P be a shortest path from x to y in H (it exists since H is connected). Let us assume that S i ⊆ V r and so i is odd (the case when S i ⊆ V w and i is even is similar). Since y ∈ Z i-1 and S i ⊆ Z i-1 (since S is parsimonious), y ∈ V r . Let a be the neighbour of x in P . Towards a contradiction, let us assume that a ̸ = y. By the minimality of the distance between x and y, a / ∈ Z i-1 and a / ∈ j<i S j . Let b ̸ = x be the other neighbour of a in P . If b ̸ = y, then by the minimality of the distance between x and y, b / ∈ Z i-1 and b / ∈ j<i S j . Therefore, by Proposition 6, if a ∈ V r , then a ∈ Z i and if b ∈ V r then b ∈ Z i . In both cases, there is a contradiction with the fact that P minimises the distance between x and y.

Therefore, we may assume that b = y. This implies that x ∈ V r . Note also that y / ∈ S j for all j ≤ i. Indeed, assuming otherwise would contradict the fact that S is monotone, since y / ∈ S i and y ∈ Z i-1 . Thus, by Proposition 6, and since a, y / ∈ j≤i-1 S j , we have that x ∈ Z i-1 . This contradicts the monotonicity of S since x / ∈ S i and x ∈ j<i S j .

Before we prove the next lemma, we introduce an extra definition. Let G = (V, E) be any graph and S = (S 1 , . . . , S ℓ ) be any winning hunter strategy in G with respect to X ⊆ V . We say that W ⊆ V is definitively cleaned at the round i if W ∩ Z j (S) = ∅ and W ∩ S j+1 = ∅ for every i ≤ j ≤ ℓ.

Informally, the following lemma says that if the degree of the root r of a tree T is large enough, compared to the number of hunters, then, when a first branch of r is definitively 1 is the first branch of T 2i,d at γ 2i that is definitively cleaned, and this happens during the round j 2i . No vertex of the branches B 2i 2 and B 2i 3 has been shot until the round j 2i . Among the branches B 2i 2 and B 2i 3 , the first branch that is definitively cleaned is B 2i 2 , and this happens at the round j ′ 2i > j 2i . The colour grey is used on the small triangles to denote that we do not know the state of the corresponding branches at the same level as B 2i

1 that are different from B 2i 2 and B 2i 3 . Observe that B 2i 2 contains a copy of T 2i-1,d , rooted at γ 2i-1 . Since B 2i 2 is definitively cleaned at round j ′ 2i , we can iterate the same arguments, and define B 2i-1 1 to be the first branch of T 2i-1 , d at γ 2i-1 that is definitively cleaned, and this happens during the round j 2i < j 2i-1 < j ′ 2i , and so on, until we have reached the leaves of B 2i 2 .

Finally, we will need an extra definition: For any tree T = (V r ∪ V w , E), and any vertex v ∈ V (T ), let B be any branch at v such that |V (B)| > 1. For any strategy S = (S 1 , . . . , S ℓ ) in T with respect to V r , let m be the minimum integer such that

Let the restriction S B of S be the hunter strategy, such that for every 1 ≤ i ≤ ℓ,

Lemma 27. For any i ∈ N * , i ≥ 3 and d ≥ 2i, we have that mh Vr (T 2i,d ) ≥ i.

Proof. Let γ 2i denote the root of T 2i,d . For purpose of contradiction, let us assume that mh Vr (T 2i,d ) < i. By Lemma 21, there exists a parsimonious monotone winning hunter strategy with respect to V r using at most i -1 hunters; let that strategy be S 2i = (S 2i 1 , . . . , S 2i ℓ ).

Let 1 ≤ j 2i ≤ ℓ be the smallest index such that some branch at γ 2i , w.l.o.g., B 2i 1 , is definitively cleaned at round j 2i . By Lemma 26, there exist two branches at γ 2i , w.l.o.g., B 2i 2 and B 2i 3 , such that (

3 ) is connected and has at least two vertices with at least one in V r . Therefore, by Lemma 3, at least one vertex of B 2i 2 (resp., B 2i 3 ) must be shot before the branch is definitively cleaned . Hence, j 2i < j ′ 2i . W.l.o.g., assume that B 2i 2 is definitively cleaned at round j ′ 2i (possibly, B 2i 3 may also be definitively cleaned at round j ′ 2i ). We now prove by induction on 0 ≤ h < 2i , that there exist 1 is definitively cleaned at round j 2i-s (not before, i.e., for every x < j 2i-s , B 2i-s 1 is not definitively cleaned at round x), B 2i-s 2 is definitively cleaned at round j ′ 2i-s (not before), B 2i-s 3 is definitively cleaned at some round x ≥ j ′ 2i-s (not before).

See Figure 4 for an illustration of the above notation.

We have already proven that the induction hypothesis holds for h = 0. Let us assume that it holds for some 0 ≤ h < 2i -1 and let us show it holds for h + 1. Let F be the copy of

be the smallest integer such that some branch B of F at γ 2i-(h+1) is definitively cleaned. Note that each branch of F at γ 2i-(h+1) is connected and has at least two vertices with at least one in V r . Therefore, by Lemma 3, at least one vertex of B must be shot before it is definitively cleaned. Hence, j 2i-h < j 2i-(h+1) . Let B = B , such that

and B

2i-(h+1) 3 are all contained in B 2i-h and, thus, max(j 2i-(h+1) , j ′ 2i-(h+1) ) = j ′ 2i-(h+1) ≤ j ′ 2i-h . This finishes the proof of the induction step.

For every 1 ≤ s ≤ 2i, let H s be the subgraph induced by B s 1 and B s 3 and γ s (so H s is connected and the subgraphs H s and H s ′ are vertex disjoint for any s ̸ = s ′ ). Since B s 1 has been definitively cleaned at round j s , has at least two vertices and by Lemma 3, there exists a vertex x ′ s ∈ V (B s 1 ) ∩ 1≤q≤j 2i S q . Note that B s 3 is connected and has at least two vertices with at least one in V r . Therefore, by Lemma 3, at least one vertex of B s 3 must be shot before the branch is definitively cleaned. Thus, since B s 3 is definitely cleaned at round z s ≥ j ′ s , but not definitely cleaned at a previous round,

3 )] = V (B s 3 ) ∪ {γ s }. Since S 2i is monotone, we get that w s / ∈ S j for every j < z s and that N (w s ) ̸ ⊆ S j for every j < z s , i.e. w s has not been shot before round A Appendix Proposition 6. Let S = (S 1 , . . . , S ℓ ) be a hunter strategy in a bipartite graph G = (V r ∪ V w , E) with respect to V r . Let v ∈ V r (resp. v ∈ V w ) and 1 ≤ i ≤ ℓ. If there exists a vertex u ∈ N (v) and a vertex x ∈ N (u) (possibly x = v) such that u / ∈ j≤i S j and x / ∈ j<i S j , then v ∈ Z 2p for every 2p ≤ i (resp. v ∈ Z 2p+1 for every 2p + 1 ≤ i).

Proof. This clearly holds if p = 0 (i.e., when v ∈ V r ) since Z 0 = V r . If p = 1 (i.e., when v ∈ V w ), there exists a rabbit trajectory (r 0 = u ∈ N (v) ∩ V r \ S 1 , r 1 = v) and so v ∈ Z 1 . Hence, we assume that p > 1.

The rabbit can follow the following strategy depending on whether p is odd or even:

1. p is odd (and so v ∈ V w ): The rabbit can follow the following trajectory: (r 0 = u, r 1 = x, . . . , r p-1 = u, r p = v) where, for q < p, r q = u if q is even and r q = x if q is odd.

2. p is even (and so, v ∈ V r ): The rabbit can follow the following trajectory: (r 0 = x, r 1 = u, . . . , r p-1 = u, r p = v) where, for q < p, r q = x if q is even and r q = u if q is odd.

In both cases, for every 0 ≤ j < p, r j / ∈ S j+1 since p ≤ i and x, u / ∈ j<i S j . Therefore, v ∈ Z p .

Lemma 18. Let G = (V r ∪ V w , E) be a bipartite graph with at least two vertices. Let S = (S 1 , . . . , S ℓ ) be a monotone hunter strategy in G with respect to V r . For any

Proof. Let us recall that for any hunter strategy in G with respect to V r , if q is even, then Z q ⊆ V r and Z q ⊆ V w otherwise. Thus , if p = 0 or if i = 2, Z i ⊆ Z p . Also, if i = 1, then Z i = Z p . Hence, let us assume that p ≥ 1 and i > 2. Let v ∈ Z i . Since v ∈ Z i , there exists a rabbit trajectory R = (r 0 , . . . , r i-2 = x, r i-1 = u, r i = v) such that, for any 0 ≤ j < i, r j / ∈ S j+1 . By definition of a rabbit trajectory, u ∈ N (v) and x ∈ N (u). Moreover, by monotonicity of S, since u ∈ Z i-1 \ S i (resp. x ∈ Z i-2 \ S i-1 ), u / ∈ q≤i S q (resp. x / ∈ q≤i-1 S q ). By Proposition 6, v ∈ Z p for each p ≤ i such that p and i has the same parity.

Lemma 19. Let S = (S 1 , . . . , S ℓ ) be a non-monotone winning hunter strategy in a bipartite graph G = (V r ∪ V w , E) with respect to V r . Then, there exist a vertex v ∈ V and

Proof. Towards a contradiction, assume that the statement of the lemma is false, i.e., for every vertex v ∈ V and every 1

∈ p<i S p . Since S is non-monotone and winning, there exists a vertex u such that u is cleared at a round 1 ≤ q ≤ ℓ -2, and then recontaminated at a round j > q (i.e., u ∈ Z j \ S j+1 ). Moreover, by our assumption, u is cleared by shooting each contaminated vertex in N (u) at round q, i.e., Z q-1 ∩ N (u) ⊆ S q . W.l.o.g., let us assume that u ∈ V r . Therefore, N (u) ⊆ V w and q -1 is odd.

Let us show that N (u) ⊆ p≤q S p . Let us assume that there exists a vertex x ∈ N (u) such that x / ∈ p<q S p . Since both u, x / ∈ p<q S q , u ∈ N (x), q -1 is odd and x ∈ V w , by Proposition 6, we get that x ∈ Z q-1 . Therefore, x ∈ Z q-1 ∩N (u) ⊆ S q . Hence, N (u) ⊆ p≤q S p .

Since v ∈ Z j then there exists w ∈ (N (u) ∩ Z j-1 ) \ S j and w ∈ p<j S p , i.e., w satisfies the statement of the lemma, a contradiction.

Lemma 20. For any non-empty connected subgraph H of a bipartite graph

we get that, if there exists a monotone winning hunter strategy S = (S 1 , . . . , S ℓ ) in G with respect to V r , then there exists a monotone winning hunter strategy S ′ in H with respect to V r ∩ V (H) using at most max 1≤i≤ℓ |S i ∩ V (H)| hunters.

Proof. Let S = (S 1 , . . . , S ℓ ) be a monotone winning hunter strategy for G with respect to V r .

If |V (H)| = 1, the result clearly holds since mh(H) = 0. Hence, let us assume that |V (H)| > 1. Let m be the minimum integer such that S m ∩ V (H) ̸ = ∅ and let u ∈ S m ∩ V (H) (by Lemma 3, such an integer m exists because |V (H)| > 1 and H is connected, which implies that V r ∩ V (H) ̸ = ∅). Let S ′ = (S ′ 1 , . . . , S ′ ℓ ) be the hunter strategy, such that for every 1 ≤ i ≤ ℓ,

First, we have the following claim.

Claim 5. For every 0 ≤ i ≤ ℓ and for any vertex

Proof of Claim. Let R = (r 0 , . . . , r i = v) be a rabbit trajectory in H such that for any 0 ≤ j < i, r j r j+1 ∈ E(H), r j / ∈ S ′ j+1 and r i = v (such a trajectory exists since v ∈ Z i (S ′ )). By construction of S ′ , for any 1 ≤ j ≤ ℓ, S j ∩ V (H) ⊆ S ′ j . Therefore, R is also a rabbit trajectory in G with r j / ∈ S j+1 , for all 0 ≤ j < i. Thus, v ∈ Z i (S). ⋄

Let us show that S ′ is a monotone winning hunter strategy in H with respect to V r ∩ V (H). First, we show that S ′ is indeed a winning hunter strategy in H with respect to V r ∩ V (H). Towards a contradiction, assume that S ′ is not a winning strategy in H w.r.t. V r ∩ V (H). This implies that Z ℓ (S ′ ) ̸ = ∅. Hence, Claim 5 implies that Z ℓ (S) ̸ = ∅, contradicting the fact that S is a winning hunter strategy in G with respect to V r .

Thus, S ′ is a winning strategy in H with respect to V r ∩ V (H). Next, we establish that S ′ is indeed monotone. Towards a contradiction, let us assume that S ′ is non-monotone. Hence, by Lemma 19, there exist v ∈ V (H) and 1

p for all 1 ≤ p ≤ m) and so v ∈ S m and in Z i (S) \ S i+1 , contradicting the monotonicity of S.

Otherwise, v ̸ = u. By construction of S ′ , S ′ p \ {u} ⊆ S p for all 1 ≤ p ≤ ℓ. Hence, v ∈ S q and v ∈ Z i (S) \ S i+1 , contradicting the monotonicity of S.

Finally, the fact that h(S ′ ) ≤ max 1≤i≤ℓ |S i ∩ V (H)| ≤ h(S) completes the proof.

Lemma 21. For any bipartite graph G = (V r ∪ V w , E) and any k ≥ mh Vr (G), there exists a parsimonious monotone winning hunter strategy in G with respect to V r and that uses k hunters.

Proof. Let S = (S 1 , . . . , S ℓ ) be a monotone winning hunter strategy with respect to V r using at most k ≥ mh Vr (G) hunters such that ℓ is minimum. If S is parsimonious, we are done.

Otherwise, among such strategies, Let us consider S that maximizes the first round 1 ≤ j < ℓ that makes S not parsimonious. There are several cases to be considered.

• Let Z(S) = (Z 0 (S), . . . , Z ℓ (S)) be the set of contaminated vertices for each round of S. If there exists an integer ℓ ′ < ℓ such that Z ℓ ′ (S) = ∅, then S = (S 1 , . . . , S ℓ ′ ) is also a winning hunter strategy with respect to V r using at most k hunters, contradicting the minimality of ℓ.

Hence, we may assume that Z i (S) ̸ = ∅ for every 0 ≤ i < ℓ.

• Let 1 ≤ j ≤ ℓ be the smallest integer such that S j \ Z j-1 (S) ̸ = ∅ (if no such integer exists, then S is parsimonious and we are done). If S j ∩ Z j-1 (S) ̸ = ∅, replace S j by S j ∩ Z j-1 (S). This leads to a winning monotone hunter strategy S ′ (indeed, Z h (S) = Z h (S ′ ) for all 1 ≤ h ≤ ℓ) contradicting the maximality of j.

Hence, we may assume that S j ∩ Z j-1 (S) = ∅. Note that this implies that j < ℓ (since otherwise, S would not be winning).

• If any, let 0 < i be the minimum integer such that

Then, for every 0 ≤ i ′ < i, replace S j+2i ′ by {v}. Let us prove that this leads to a monotone hunter strategy contradicting the maximality of j.

Let S ′ be the strategy obtained by the above modifications. First, note that, for any 0 ≤ h < j, S h = S ′ h and so

S) and S ′ j = {v}. Hence, Z j (S ′ ) ⊆ Z j (S). By induction on j ≤ i ′ ≤ ℓ and using the same arguments, we get that Z i ′ (S ′ ) ⊆ Z i ′ (S) for every j ≤ i ′ ≤ ℓ. Thus, S ′ is a winning hunter strategyin G with respect to W ⊆ V r using at most k ≥ mh Vr (G) hunters (because Z ℓ (S ′ ) ⊆ Z ℓ (S) = ∅). It remains to show that S ′ is monotone.

For purpose of contradiction, let us assume that S ′ is non-monotone. By Lemma 19, there exists a vertex x and 1 < m ≤ ℓ such that x ∈ Z m-1 (S ′ ) \ S ′ m and x ∈ h<m S ′ h . If x ̸ = v, then by definition of S ′ (for every 1 ≤ r ≤ ℓ, either S ′ r = S r or S ′ r = {v}) and because Z r (S ′ ) ⊆ Z r (S) for all 1 ≤ r ≤ ℓ, we get that x ∈ h<m S h and x ∈ Z m-1 (S) \ S m which contradicts the monotonicity of S. Hence, let us assume that x = v.

Recall that we proved that v ∈ Z j-1 (S) \ S j . Therefore, by monotonicity of S and by the definition of i above, v / ∈ r<j+2i S r which implies that v / ∈ r<j S ′ r . Since v ∈ S ′ j+2i ′ for all 0 ≤ i ′ ≤ i and, because v ∈ Z j+2i-1 and by parity, v / ∈ Z j+2i ′ (S ′ ) for all 0 ≤ i ′ ≤ i, we get that m > j + 2i. This means that v ∈ Z m-1 (S) \ S m (because Z r (S ′ ) ⊆ Z r (S) for all 1 ≤ r ≤ ℓ and S ′ r = S r for all r ≥ m > j + 2i) and v ∈ S j+2i , which contradicts the monotonicity of S.

Hence, we may assume that S j+2i ′ ∩ Z j+2i ′ -1 (S) = ∅ for all 0 ≤ i ′ such that j + 2i ′ ≤ ℓ.

• If Z j+1 (S) = Z j-1 (S), then remove S j and S j+1 from S. Let S ′ be the obtained strategy.

We have that Z r (S) = Z r (S ′ ) and S r = S ′ r for all r < j and Z r+2 (S) = Z r (S ′ ) and S r+2 = S ′ r for all j ≤ r ≤ ℓ -2. Hence, S ′ is winning since Z ℓ-2 (S ′ ) = ∅. Moreover, if S ′ is nonmonotone, then, by Lemma 7, there exists x and 1 < m ≤ ℓ such that x ∈ Z m-1 (S ′ ) \ S ′ m and x ∈ h<m S ′ h . If m < j, this implies that x ∈ Z m-1 (S) \ S m and x ∈ h<m S h contradicting the monotonicity of S. Otherwise (m ≥ j), x ∈ Z m+1 (S) \ S m+2 and x ∈ h<m+2 S h , also contradicting the monotonicity of S.

Hence, we may assume that Z j+1 (S) ̸ = Z j-1 (S).

• Note first that by Lemma 18, Z j+1 (S) ⊆ Z j-1 (S). Thus, Z j+1 (S) \ Z j-1 (S) = ∅. Hence, since Z j+1 (S) ̸ = Z j-1 (S), we get that Z j-1 (S) \ Z j+1 (S) ̸ = ∅.

Hence, there exists v ∈ Z j-1 (S) \ Z j+1 (S). Let S ′ be obtained by replacing S j by {v}. By arguments similar to the ones of the third item of this proof, we can prove that S ′ is a monotone hunter strategy contradicting the maximality of j.

This completes the proof.

Lemma 22. Let G = (V r ∪ V w , E) be a bipartite graph and S = (S 1 , . . . , S ℓ ) be a parsimonious monotone winning hunter strategy with respect to V r .