# Further results on the Hunters and Rabbit game through monotonicity111A
Preliminary version of this paper appeared in the proceedings of MFCS 2023.

Thomas Dissaux  Université Côte d’Azur, Inria, CNRS, I3S, France  Foivos
Fioravantes  Université Côte d’Azur, Inria, CNRS, I3S, France  Department of
Theoretical Computer Science, Faculty of Information Technology, Czech
Technical University in Prague, Prague, Czech Republic  Harmender Galhawat
Ben-Gurion University of the Negev, Beersheba, Israel  Nicolas Nisse
Université Côte d’Azur, Inria, CNRS, I3S, France

###### Abstract

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)\leq mh(G)\leq 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\geq 3$,
there exists a tree $T$ with $h(T)=2$ and $mh(T)=k$. We conclude by proving
that computing $h$ (resp., $mh$) is $\mathsf{FPT}$ parameterised by the
minimum size of a vertex cover.

##  1 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
[8], 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 [19], 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\geq 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\geq 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\times
m})=\lfloor\frac{\min\\{n,m\\}}{2}\rfloor+1$ [1] and
$h(Q^{n})=1+\Sigma_{i=0}^{n-2}{i\choose\lfloor i/2\rfloor}$ [6], where
$G_{n\times m}$ is the $n\times 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)\leq\lceil\frac{1}{2}\log_{2}(|V(T)|)\rceil$ [16]. 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)\leq 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 [7, 26]. 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
[21], robot motion planning [10], constraint satisfaction problems and
database theory [15], and distributed computing [25]. 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
[27], pathwidth [26], tree-depth [14], hypertree-width [2], cycle-rank [14],
and directed tree-width [22]. The connection between Graph Searching games and
structural parameters, such as the treewidth or the pathwidth, is based on the
notion of monotonicity [4, 27, 24, 20]. 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” [23], 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 [27]).

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)\in\\{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)|^{\varepsilon}$, for
$0<\varepsilon<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 $\omega(G)\leq h(G)\leq
mh(G)\leq\omega(G)+1$ in any split graph $G$ with maximum clique of size
$\omega(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 [26] 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, 16]). In particular, this
allows us to show that, for any $k\in\mathbb{N}$, there exist trees $T$ such
that $h(T)=2$ and $mh(T)\geq 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)\leq k$, for some given integer
$k$, is in $\mathsf{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.

##  2 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\in V$, let $xy\in E$ denote the edge between
$x$ and $y$. Given a set $S\subseteq V$, let $G[S]$ denote the subgraph of $G$
induced by (the vertices in) $S$ and let $G\setminus S$ denote the subgraph
$G[V\setminus S]$. For any $v\in V$ and $X\subseteq V$, let $N_{X}(v)=\\{u\in
X\mid uv\in 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)\cup\\{v\\})\cap X$. If
$X=V$, we simply write $N(v)$ and $N[v]$ respectively. For any $S\subseteq V$,
let $N(S)=\bigcup_{v\in S}N(v)\setminus S$ and $N[S]=N(S)\cup S$. The degree
$d(v)=|N(v)|$ is the number of neighbours of $v$ and let $\delta(G)=\min_{v\in
V}d(v)$. An independent set of a graph $G=(V,E)$ is a subset $I$ of $V$ such
that, for every $u,v\in I$, $uv\notin 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\in\mathbb{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}\in 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\geq 1$, first, the Hunter player selects a non empty subset
$S_{i}\subseteq 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}\in 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}\in 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 ${\cal
S}=(S_{1},\dots,S_{\ell})$ of non empty subsets of vertices of $G$. Let
$h({\cal S}):=\max_{1\leq i\leq\ell}|S_{i}|$ and let us say that $\cal S$ uses
$h({\cal S})$ hunters. A rabbit trajectory in $G$ starting from $W\subseteq V$
($W$ will always be assumed non empty) is any walk $(r_{0},\dots,r_{\ell})$
starting from $W$, i.e., $r_{0}\in W$ and $r_{i}\in N(r_{i-1})$ for every
$1\leq i\leq\ell$. A hunter strategy is winning with respect to $W$ if, for
every rabbit trajectory $(r_{0},\dots,r_{\ell})$ starting from $W$, there
exists $0\leq j<\ell$ such that $r_{j}\in S_{j+1}$, that is, the rabbit is
eventually shot whatever be its trajectory starting from $W$. Given a hunter
strategy ${\cal S}=(S_{1},\dots,S_{\ell})$, a rabbit trajectory
$(r_{0},\dots,r_{\ell})$ starting from $W$ is winning against $\cal S$ if
$r_{i}\notin S_{i+1}$ for every $0\leq i<\ell$. 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\subseteq 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 $\cal R$ starting from $W\subseteq V$ against $k\geq 1$ hunters if,
for every hunter strategy $\cal S$ using $k$ hunters, there exists a rabbit
trajectory ${\cal R}({\cal S})$ that is winning against $\cal S$. Note that,
if such a strategy $\cal 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\subseteq V$ with $W\cap V(H)\neq\emptyset$. Then, $h_{W\cap V(H)}(H)\leq
h_{W}(G)\leq h(G)$.

###### Proof.

By definition, $h_{W}(G)\leq h(G)$. Let us show the other inequality.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a winning hunter strategy in $G$
with respect to $W$. Let
$\mathcal{S}^{\prime}=(S^{\prime}_{1},S_{2}^{\prime},\dots,S_{\ell}^{\prime})$
be such that, for every $1\leq i\leq\ell$, $S^{\prime}_{i}=S_{i}\cap V(H)$ if
$S_{i}\cap V(H)\neq\emptyset$ and $S^{\prime}_{i}$ consists of any vertex of
$V(H)$ otherwise. Then, ${\cal S}^{\prime}$ is a winning hunter strategy in
$H$ with respect to $W\cap V(H)$. Indeed, any rabbit trajectory $(r_{0}\in
W\cap V(H),r_{1},\dots,r_{\ell})$ in $H$ is also a trajectory starting from
$W$ in $G$. Since $\cal S$ is winning w.r.t. $W$, there exists $i<\ell$ such
that $r_{i}\in S_{i+1}\cap V(H)\subseteq S^{\prime}_{i+1}$, and so ${\cal
S}^{\prime}$ is winning w.r.t. $W\cap V(H)$. Moreover, $h({\cal
S}^{\prime})\leq h({\cal S})$. ∎

For any hunter strategy ${\cal S}=(S_{1},\dots,S_{\ell})$, it will be
convenient to identify the potential positions of a rabbit (starting in
$W\subseteq V$) after each round. Precisely, let ${\cal Z}^{W}({\cal
S})=(Z^{W}_{0}({\cal S}),\dots,Z^{W}_{\ell}({\cal S}))$ be defined as follows.
Let $Z^{W}_{0}({\cal S})=W$ and, for every $0<i\leq\ell$, let $Z^{W}_{i}({\cal
S})$ be the set of vertices $v$ such that there exists a rabbit trajectory
$(r_{0},r_{1},\dots,r_{i}=v)$ such that $r_{0}\in W$ and, for every $0\leq
j<i$, $r_{j}\notin S_{j+1}$. Formally, for any $1\leq i\leq\ell$, let
$Z^{W}_{i}({\cal S})=\\{x\in V(G)\mid\exists y\in(Z^{W}_{i-1}({\cal
S})\setminus S_{i})\wedge(xy\in E(G))\\}$. Intuitively, $Z^{W}_{i}({\cal 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}({\cal S})$ as the contaminated
vertices after round $i$. Note that, if $\cal S$ is winning, then
$Z^{W}_{\ell}({\cal S})=\emptyset$. In what follows, we write $Z_{i}$ (resp.,
$Z_{i}({\cal S})$) instead of $Z^{W}_{i}({\cal S})$ when $\cal 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 ${\cal S}=(S_{1},\dots,S_{\ell})$ is said to
be parsimonious if, for every $1\leq i\leq\ell$, $S_{i}\subseteq Z_{i-1}({\cal
S})$. Note that, if ${\cal S}$ is parsimonious, then $Z_{i}\neq\emptyset$ for
every $i<\ell$. Note that if ${\cal S}$ is parsimonious, then it can be
retrieved only from the sequence ${\cal Z}({\cal S})=(Z_{0},\dots,Z_{\ell})$
of the contaminated sets. Indeed, for any $1\leq i\leq\ell$, $S_{i}=\\{w\in
Z_{i-1}\mid\exists x\in N(w)\backslash 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\subseteq V$, there is a
parsimonious winning hunter strategy in $G$ with respect to $W$ and that uses
$h_{W}(G)$ hunters.

###### Proof.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a winning hunter strategy with
respect to $W\subseteq V$ using at most $k\geq 1$ hunters. Let
$\mathcal{Z}({\cal S})=(Z_{0}({\cal S}),\dots,Z_{\ell}({\cal S}))$ be the set
of contaminated vertices for each round of $\mathcal{S}$. If there exists an
integer $\ell^{\prime}<\ell$ such that $Z_{\ell^{\prime}}({\cal
S})=\emptyset$, then $\mathcal{S}=(S_{1},\dots,S_{\ell^{\prime}})$ is also a
winning hunter strategy with respect to $W\subseteq V$ using at most $k$
hunters. Hence, we may assume that $Z_{i}({\cal S})\neq\emptyset$ for every
$0\leq i<\ell$.

Moreover, if there exists an integer $1\leq i\leq\ell$ such that $S_{i}\cap
Z_{i-1}({\cal S})=\emptyset$, let $h$ be the smallest such integer and let
$v\in Z_{h-1}({\cal S})$. Then,
$\mathcal{S}^{\prime}=(S_{1},\dots,S_{h-1},\\{v\\},S_{h+1},\dots,S_{\ell})$ is
also a winning strategy with respect to $W\subseteq V$ using at most $k\geq 1$
hunters (since $S_{h}\cap Z_{h-1}({\cal S})=\emptyset$). By repeating this
process, we may assume that, for every $1\leq i\leq\ell$, $S_{i}\cap
Z_{i-1}({\cal S})\neq\emptyset$.

Let
$\mathcal{S}^{\prime}=(S^{\prime}_{1},S_{2}^{\prime},\dots,S_{\ell^{\prime}}^{\prime})$
be such that, for every $1\leq i\leq\ell^{\prime}$, $S^{\prime}_{i}=S_{i}\cap
Z_{i-1}({\cal S})$. It is easy to see that, for every $i\leq\ell^{\prime}$,
$Z_{i}({\cal S})=Z_{i}({\cal S}^{\prime})$, and then ${\cal S}^{\prime}$ is
parsimonious. Furthermore, ${\cal S}^{\prime}$ is a winning hunter strategy
with respect to $W$. Indeed, since $\cal S$ is winning w.r.t. $W$, for any
rabbit trajectory $(r_{0},r_{1},\dots,r_{\ell})$, there exists an integer
$j<\ell$ such that $r_{j}\in S_{j+1}$. Let $i$ be the smallest such integer.
By definition, $r_{i}\in Z_{i}\cap S_{i+1}=S^{\prime}_{i+1}$ and so ${\cal
S}^{\prime}$ is winning w.r.t. $W$. Moreover, $h({\cal S}^{\prime})\leq
h({\cal S})$. ∎

It must be noticed that there exist graphs $G=(V,E)$ and hunter strategies
$(S_{1},\dots,S_{\ell})$ that are winning in $G$ without shooting to all
vertices, i.e., such that $V\setminus\bigcup_{1\leq
i\leq\ell}S_{i}\neq\emptyset$. 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\subseteq V$ such that $W\cap V(H)\neq\emptyset$. Let ${\cal
S}=(S_{1},\dots,S_{\ell})$ be any winning hunter strategy in $G$ with respect
to $W$. If $S_{i}\cap V(H)=\emptyset$ for all $1\leq i\leq\ell$, then
$|V(H)|=1$.

###### Proof.

Let $x\in V(H)\cap W$. Towards a contradiction, assume that $|V(H)|\geq 2$.
Let $y\in N_{H}(x)$ (it exists since $H$ is connected). Note that since
$S_{i}\cap V(H)=\emptyset$ for all $1\leq i\leq\ell$,
$\\{x,y\\}\cap\bigcup_{1\leq i\leq\ell}S_{i}=\emptyset$. Thus, the rabbit can
oscillate between $x$ and $y$ during the whole game without being shot. That
is, ${\cal R}=(r_{0}=x,r_{1}=y,r_{2}=x,\dots,r_{\ell})$ is a winning rabbit
trajectory against ${\cal S}$ starting from $W\cap V(H)$. This contradicts
that ${\cal 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)\geq\delta(G)$.

The Hunters and Rabbit game has been particularly studied in bipartite graphs
[1, 6, 16] and we continue this study in Section 5. In what follows, bipartite
graphs are referred to as $G=(V_{r}\cup 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}\cup V_{w},E)$,
$h(G)=h_{V_{r}}(G)=h_{V_{w}}(G)$.

###### Proof.

By definition, $\max\\{h_{V_{r}}(G),h_{V_{w}}(G)\\}\leq h(G)$. To show that
$h(G)\leq h_{V_{r}}(G)$ (resp., $h(G)\leq h_{V_{w}}(G)$), let
$\mathcal{S}_{r}=(S_{1},\dots,S_{\ell})$ be a winning hunter strategy in $G$
with respect to $V_{r}$ (resp., w.r.t. $V_{w}$). If $\ell$ is odd, then
$(S_{1},\dots,S_{\ell},S_{1},\dots,S_{\ell})$ is a winning hunter strategy,
and otherwise, $(S_{1},\dots,S_{\ell},\\{u\\},S_{1},\dots,S_{\ell})$ 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}\cup V_{w},E)$ be a bipartite graph and
$\mathcal{S}_{r}=(S_{1},\dots,S_{\ell})$ be a parsimonious hunter strategy in
$G$ with respect to $V_{r}$. Then, for every $1\leq i\leq\lceil\ell/2\rceil$,
$S_{2i-1}\subseteq Z_{2i-2}\subseteq V_{r}$ and (if $2i\leq\ell$)
$S_{2i}\subseteq Z_{2i-1}\subseteq 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.

##  3 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,
29, 24] 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, 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.

$a$$b$$c$$d$$e$$f$$g$

(a) $Z_{0}=\\{a,c,e,g\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(b) $S_{1}=\\{c\\}$,
$Z_{1}=\\{b,d,f\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(c) $S_{2}=\\{d\\}$, $Z_{2}=\\{a,c,g\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(d) $S_{3}=\\{c\\}$, $Z_{3}=\\{b,f\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(e) $S_{4}=\\{f\\}$, $Z_{4}=\\{a,c\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(f) $S_{5}=\\{c\\}$, $Z_{5}=\\{b\\}$

$a$$b$$c$$d$$e$$f$$g$✗

(g) $S_{6}=\\{b\\}$, $Z_{6}=\emptyset$

Figure 1: 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 ${\cal
S}=(\\{c\\},\\{d\\},\\{c\\},\\{f\\},\\{c\\},\\{b\\})$ and ${\cal Z}({\cal
S})=(\\{a,c,e,g\\},\\{b,d,f\\},\\{a,c,g\\},\\{b,f\\},\\{a,c\\},\\{b\\},\emptyset)$.

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\notin Z_{i}$. This discussion
motivates the following definition for the monotonicity of hunter strategies.

###  3.1 Definition of monotone strategies and first properties

Given a graph $G$, a winning hunter strategy $\mathcal{S}$ in $G$ with respect
to $W\subseteq V$, is monotone if for every vertex $v\in 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\in S_{i}$ or $N(v)\cap Z_{i-1}\neq\emptyset$ and $N(v)\cap Z_{i-1}\subseteq
S_{i}$. Note that, in the second condition, the fact that we require that
$N(v)\cap Z_{i-1}\neq\emptyset$ comes from technicalities when $W\neq V$. A
strategy $\mathcal{S}=(S_{1},\dots,S_{\ell})$ is monotone if, for every vertex
$v\in V$, if there exists an $i$ such that $v$ is cleared at round $i$, then
for every $j>i$ such that $v\in Z_{j}$, the strategy ensures that $v\in
S_{j+1}$. A vertex $v$ is recontaminated at round $j$ if there exists $i\leq
j$ such that $v$ is cleared at round $i$ and $v\in Z_{j}\setminus S_{j+1}$.

The monotone hunter number of a graph $G$ with respect to $W\subseteq 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\subseteq V$, $h_{W}(G)\leq mh_{W}(G)\leq
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 $\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a hunter strategy in a graph
$G=(V,E)$. Let $v\in V$ and $1\leq i\leq\ell$. If there exists a vertex $u\in
N(v)$ and a vertex $x\in N(u)$ (possibly $x=v$) such that
$u\notin\bigcup_{j\leq i}S_{j}$ and $x\notin\bigcup_{j<i}S_{j}$, then $v\in
Z_{p}$ for each $p\leq i$.

###### Proof.

This clearly holds if $p=0$ since $Z_{0}=V$. If $p=1$, there exists a rabbit
trajectory $(r_{0}=u\in N(v)\setminus S_{1},r_{1}=v)$ and so $v\in Z_{1}$.
Hence, we assume that $p>1$.

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

  1. 1.

$p$ is odd: The rabbit can follow the following trajectory:
$(r_{0}=u,r_{1}=x,r_{2}=u,\ldots,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. 2.

$p$ is even: The rabbit can follow the following trajectory:
$(r_{0}=x,r_{1}=u,r_{2}=x,\ldots,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\leq j<p$, $r_{j}\notin S_{j+1}$ since $p\leq i$,
$u\notin\bigcup_{j\leq i}S_{j}$ and $x\notin\bigcup_{j<i}S_{j}$. Therefore,
$v\in 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
$\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a monotone hunter strategy in $G$.
For any $0\leq p\leq i\leq\ell$, $Z_{i}\subseteq Z_{p}$.

###### Proof.

This clearly holds if $p=0$ or $i=1$ since $Z_{0}=V$. Hence, let us assume
that $p\geq 1$ and $i>1$. Let $v\in Z_{i}$. Since $v\in Z_{i}$, there exists a
rabbit trajectory $R=(r_{0},\dots,r_{i-2}=x,r_{i-1}=u,r_{i}=v)$ such that, for
any $0\leq j<i$, $r_{j}\notin S_{j+1}$. By definition of a rabbit trajectory,
$u\in N(v)$ and $x\in N(u)$. Moreover, by monotonicity of ${\cal S}$, since
$u\in Z_{i-1}\setminus S_{i}$ (resp. $x\in Z_{i-2}\setminus S_{i-1}$),
$u\notin\bigcup_{q\leq i}S_{q}$ (resp. $x\notin\bigcup_{q\leq i-1}S_{q}$). By
Proposition 2, $v\in Z_{p}$ for each $p\leq 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 $\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a non-monotone winning hunter
strategy in a graph $G=(V,E)$. Then, there exist a vertex $v\in V$ and $1\leq
i\leq\ell$ such that $v\in Z_{i-1}\setminus S_{i}$ and
$v\in\bigcup_{p<i}S_{p}$.

###### Proof.

Towards a contradiction, assume that the statement of the lemma is false,
i.e., for every vertex $v\in V$ and every $1\leq i\leq\ell$, if $v\in
Z_{i-1}\setminus S_{i}$ then $v\notin\bigcup_{p<i}S_{p}$.

Since $\mathcal{S}$ is non-monotone and winning, there exists a vertex $u$
such that $u$ is cleared at a round $1\leq q\leq\ell-2$, and then
recontaminated at a round $j>q$ (i.e., $u\in Z_{j}\setminus 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}\cap N(u)\subseteq S_{q}$.

Let us show that $N(u)\subseteq\bigcup_{p\leq q}S_{p}$. Let us assume that
there exists a vertex $x\in N(u)$ such that $x\notin\bigcup_{p<q}S_{p}$. Since
both $u,x\notin\bigcup_{p<q}S_{q}$ and $u\in N(x)$, by Proposition 2, we get
that $x\in Z_{q-1}$. Therefore, $x\in Z_{q-1}\cap N(u)\subseteq S_{q}$. Hence,
$N(u)\subseteq\bigcup_{p\leq q}S_{p}$.

Since $u\in Z_{j}$ then there exists $w\in(N(u)\cap Z_{j-1})\setminus S_{j}$
and $w\in\bigcup_{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)\leq
mh(G)$. More precisely, if there exists a monotone winning hunter strategy
${\cal S}=(S_{1},\ldots,S_{\ell})$ in $G$, then there exists a monotone
winning hunter strategy ${\cal S}^{\prime}$ in $H$ using at most $\max_{1\leq
i\leq\ell}|S_{i}\cap V(H)|$ hunters.

###### Proof.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ 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}\cap
V(H)\neq\emptyset$ and let $u\in S_{m}\cap V(H)$ (by Lemma 3, such an integer
$m$ exists because $|V(H)|>1$). Let
$\mathcal{S}^{\prime}=(S^{\prime}_{1},\dots,S^{\prime}_{\ell})$ be the hunter
strategy, such that for every $1\leq i\leq\ell$,

$S^{\prime}_{i}=\begin{cases}S_{i}\cap V(H),&\quad\text{if }S_{i}\cap
V(H)\neq\emptyset\\\ \\{u\\},&\quad\text{otherwise}\\\ \end{cases}$

First, we have the following claim.

######  Claim 1.

For every $0\leq i\leq\ell$ and for any vertex $v\in V(H)$, if $v\in
Z_{i}({\cal S}^{\prime})$, then $v\in Z_{i}({\cal S})$.

Proof of Claim. Let $\mathcal{R}=(r_{0},\dots,r_{i}=v)$ be a rabbit trajectory
in $H$ such that for any $0\leq j<i$, $r_{j}r_{j+1}\in E(H)$, $r_{j}\notin
S^{\prime}_{j+1}$ and $r_{i}=v$ (such a trajectory exists since $v\in
Z_{i}({\cal S}^{\prime})$). By construction of $\mathcal{S}^{\prime}$, for any
$1\leq j\leq\ell$, $S_{j}\cap V(H)\subseteq S^{\prime}_{j}$. Therefore,
$\mathcal{R}$ is also a rabbit trajectory in $G$ with $r_{j}\notin S_{j+1}$,
for all $0\leq j<i$. Thus, $v\in Z_{i}({\cal S})$. $\diamond$

Let us show that $\mathcal{S}^{\prime}$ is a monotone winning hunter strategy
in $H$. First, we show that $\mathcal{S}^{\prime}$ is indeed a winning hunter
strategy in $H$. Towards a contradiction, assume that $\mathcal{S}^{\prime}$
is not a winning strategy in $H$. This implies that $Z_{\ell}({\cal
S}^{\prime})\neq\emptyset$. Hence, Claim 1 implies that $Z_{\ell}({\cal
S})\neq\emptyset$, contradicting the fact that $\mathcal{S}$ is a winning
hunter strategy in $G$.

Thus, $\mathcal{S}^{\prime}$ is a winning strategy in $H$. Next, we establish
that $\mathcal{S}^{\prime}$ is indeed monotone. Towards a contradiction, let
us assume that $\mathcal{S}^{\prime}$ is non-monotone. Hence, by Lemma 7,
there exist $v\in V(H)$ and $1\leq q<i\leq\ell$ such that $v\in
S^{\prime}_{q}$ and $v\in Z_{i}({\cal S^{\prime}})\setminus S^{\prime}_{i+1}$.
By Claim 1 and because $v\in Z_{i}({\cal S}^{\prime})$, $v\in Z_{i}({\cal
S})$. Since $S_{p}\cap V(H)\subseteq S^{\prime}_{p}$ for any $1\leq p\leq\ell$
and because $v\notin S^{\prime}_{i+1}$, $v\notin S_{i+1}$.

If $v=u$, $i+1>m$ (since $u\in S^{\prime}_{p}$ for all $1\leq p\leq m$) and so
$v\in S_{m}$ and in $Z_{i}({\cal S})\setminus S_{i+1}$, contradicting the
monotonicity of $\cal S$.

Otherwise, $v\neq u$. By construction of $\mathcal{S}^{\prime}$,
$S^{\prime}_{p}\setminus\\{u\\}\subseteq S_{p}$ for all $1\leq p\leq\ell$.
Hence, $v\in S_{q}$ and $v\in Z_{i}({\cal S})\setminus S_{i+1}$, contradicting
the monotonicity of $\cal S$.

Finally, the fact that $h(\mathcal{S}^{\prime})\leq\max_{1\leq
i\leq\ell}|S_{i}\cap V(H)|\leq h({\cal S})$ completes the proof. ∎

######  Lemma 9.

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

###### Proof.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a monotone winning hunter strategy
in $G$ using at most $k\geq mh(G)$ hunters such that $\ell$ is minimum. If
${\cal S}$ is parsimonious, we are done. Otherwise, among such strategies, let
us consider $\cal S$ that maximizes the first round $1\leq j\leq\ell$ that
makes $\mathcal{S}$ not parsimonious. There are several cases to be
considered.

  * •

Let $\mathcal{Z}({\cal S})=(Z_{0}({\cal S}),\dots,Z_{\ell}({\cal S}))$ be the
set of contaminated vertices for each round of $\mathcal{S}$. If there exists
an integer $\ell^{\prime}<\ell$ such that $Z_{\ell^{\prime}}({\cal
S})=\emptyset$, then $\mathcal{S}=(S_{1},\dots,S_{\ell^{\prime}})$ is also a
monotone winning hunter strategy in $G$ using at most $k$ hunters,
contradicting the minimality of $\ell$.

Hence, we may assume that $Z_{i}({\cal S})\neq\emptyset$ for every $0\leq
i<\ell$.

  * •

Let $1\leq j\leq\ell$ be the smallest integer such that $S_{j}\setminus
Z_{j-1}({\cal S})\neq\emptyset$ (if no such integer exists, then ${\cal S}$ is
parsimonious and we are done). If $S_{j}\cap Z_{j-1}({\cal S})\neq\emptyset$,
replace $S_{j}$ by $S_{j}\cap Z_{j-1}({\cal S})$. This leads to a winning
monotone hunter strategy ${\cal S}^{\prime}$ (indeed, $Z_{h}({\cal
S})=Z_{h}({\cal S}^{\prime})$ for all $1\leq h\leq\ell$) contradicting the
maximality of $j$.

Hence, we may assume that $S_{j}\cap Z_{j-1}({\cal S})=\emptyset$. Note that
this implies that $j<\ell$ (since otherwise, $\cal S$ would not be winning).

  * •

If any, let $0<i$ be the minimum integer such that $S_{j+i}\cap
Z_{j+i-1}({\cal S})\neq\emptyset$. Let $v\in S_{j+i}\cap Z_{j+i-1}({\cal S})$.
Since $v\in Z_{j+i-1}({\cal S})$, by Lemma 6, $v\in Z_{j-1+i^{\prime}}({\cal
S})$ for every $0\leq i^{\prime}<i$. Then, for every $0\leq i^{\prime}<i$,
replace $S_{j+i^{\prime}}$ by $\\{v\\}$. Let us prove that this leads to a
monotone hunter strategy contradicting the maximality of $j$.

Let ${\cal S^{\prime}}$ be the strategy obtained by the above modifications.
First, note that, for any $0\leq h<j$, $S_{h}=S^{\prime}_{h}$ and so
$Z_{h}({\cal S})=Z_{h}({\cal S}^{\prime})$. By definition, $Z_{j}({\cal
S})=\\{x\in V\mid\exists y\in Z_{j-1}({\cal S})\setminus S_{j}\wedge(xy\in
E)\\}$ and, since $S_{j}\cap Z_{j-1}=\emptyset$, we get $Z_{j}({\cal
S})=\\{x\in V\mid\exists y\in Z_{j-1}({\cal S})\wedge(xy\in E)\\}$. On the
other hand, $Z_{j}({\cal S}^{\prime})=\\{x\in V\mid\exists y\in Z_{j-1}({\cal
S^{\prime}})\setminus S^{\prime}_{j}\wedge(xy\in E)\\}=\\{x\in V\mid\exists
y\in Z_{j-1}({\cal S})\setminus\\{v\\}\wedge(xy\in E)\\}$ since $Z_{j-1}({\cal
S}^{\prime})=Z_{j-1}({\cal S})$ and $S^{\prime}_{j}=\\{v\\}$. Hence,
$Z_{j}({\cal S}^{\prime})\subseteq Z_{j}({\cal S})$. By induction on $j\leq
i^{\prime}\leq\ell$ and using the same arguments, we get that
$Z_{i^{\prime}}({\cal S}^{\prime})\subseteq Z_{i^{\prime}}({\cal S})$ for
every $j\leq i^{\prime}\leq\ell$. Thus, ${\cal S}^{\prime}$ is a winning
hunter strategy in $G$ using at most $k\geq mh(G)$ hunters (because
$Z_{\ell}({\cal S}^{\prime})\subseteq Z_{\ell}({\cal S})=\emptyset$). It
remains to show that ${\cal S}^{\prime}$ is monotone.

For purpose of contradiction, let us assume that ${\cal S}^{\prime}$ is non-
monotone. By Lemma 7, there exists a vertex $x$ and $1<m\leq\ell$ such that
$x\in Z_{m-1}({\cal S}^{\prime})\setminus S^{\prime}_{m}$ and
$x\in\bigcup_{h<m}S^{\prime}_{h}$.

If $x\neq v$, then by definition of ${\cal S}^{\prime}$ (for every $1\leq
r\leq\ell$, either $S^{\prime}_{r}=S_{r}$ or $S^{\prime}_{r}=\\{v\\}$) and
because $Z_{r}({\cal S}^{\prime})\subseteq Z_{r}({\cal S})$ for all $1\leq
r\leq\ell$, we get that $x\in\bigcup_{h<m}S_{h}$ and $x\in Z_{m-1}({\cal
S})\setminus S_{m}$ which contradicts the monotonicity of ${\cal S}$. Hence,
let us assume that $x=v$. Recall that we proved that $v\in Z_{j-1}({\cal
S})\setminus S_{j}$. Therefore, by monotonicity of $\cal S$,
$v\notin\bigcup_{r<j}S_{r}$ which implies that
$v\notin\bigcup_{r<j}S^{\prime}_{r}$. Since $v\in S^{\prime}_{j+i^{\prime}}$
for all $0\leq i^{\prime}\leq i$, we get that $m>j+i$. This means that $v\in
Z_{m-1}({\cal S})\setminus S_{m}$ (because $Z_{r}({\cal S}^{\prime})\subseteq
Z_{r}({\cal S})$ for all $1\leq r\leq\ell$ and $S^{\prime}_{r}=S_{r}$ for all
$r\geq m>j+i$) and $v\in S_{j+i}$, which contradicts the monotonicity of $\cal
S$.

Hence, we may assume that $S_{j+i^{\prime}}\cap Z_{j+i^{\prime}-1}({\cal
S})=\emptyset$ for all $0\leq i^{\prime}$ such that $j+i^{\prime}\leq\ell$.

  * •

Let us recall that $j<\ell$ and that $Z_{j-1}({\cal S})\neq\emptyset$. Thus,
let $v\in Z_{j-1}({\cal S})$. So, there exists $w\in N(v)\cap Z_{j-2}({\cal
S})\setminus S_{j-1}$. Moreover, since $w\in Z_{j-2}({\cal S})\setminus
S_{j-1}$ (resp. $v\in Z_{j-1}({\cal S})\setminus S_{j}$), $w\notin S_{r}$
(resp. $v\notin S_{r}$) for any $r\leq j$ (otherwise, it contradicts the
monotonicity of ${\cal S}$). Let us recall that for any $0\leq i^{\prime}$
such that $j+i^{\prime}\leq\ell$, $S_{j+i^{\prime}}\cap
Z_{j+i^{\prime}-1}({\cal S})=\emptyset$. Therefore, $w\notin S_{r}$ and
$v\notin S_{r}$ for any $r\leq\ell$. By Proposition 2, $v\in Z_{\ell}({\cal
S})$, which contradicts that ${\cal 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 $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a
parsimonious monotone winning hunter strategy in $G$.

  * •

If there exist $1\leq i<j\leq\ell$ such that $v\in S_{i}\cap S_{j}$, then
$v\in S_{i+1}$.

  * •

If there exists an integer $1\leq i<\ell$ such that $v\notin Z_{i-1}$, then
$v\notin S_{j}$ for every $j\geq i$.

###### Proof.

First assume that $v\in S_{i}\cap S_{j}$. Since $\cal S$ is parsimonious, it
implies that $v\in Z_{i-1}\cap Z_{j-1}$. By Lemma 6 and since $v\in Z_{j}$,
$v\in Z_{i^{\prime}}$ for all $i^{\prime}<j$. Since $v\in S_{i}$ and $v\in
Z_{p-1}$ for all $i\leq p\leq j$, by monotonicity of $\cal S$, $v\in S_{p}$
for all $i\leq p\leq j$.

For the second statement, the fact that $v\notin Z_{i-1}$ and Lemma 6 imply
that $v\notin Z_{j}$ for all $j\geq i$. Since $\cal S$ is parsimonious,
$v\notin S_{j}$ for every $j\geq 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\in S_{1}$ and
$a\in Z_{1}\setminus S_{2}$).

###  3.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},\dots,X_{p})$ of subsets of vertices, called bags, such that (1)
$\bigcup_{i\leq p}X_{i}=V$; (2) for every $uv\in E$, there exists $i\leq p$
with $\\{u,v\\}\subseteq X_{i}$; and (3): for every $1\leq i\leq j\leq q\leq
p$, $X_{i}\cap X_{q}\subseteq X_{j}$. The width $w(P)$ of $P$ is the size of a
largest bag of $P$ minus one, i.e., $w(P)=\max_{i\leq 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)\leq mh(G)\leq pw(G)+1$.

###### Proof.

First, let $P=(X_{1},\dots,X_{\ell})$ 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\leq
i<\ell$, $X_{i}\cap X_{i+1}$ separates $\bigcup_{1\leq j\leq i}X_{j}\setminus
X_{i+1}$ from $\bigcup_{i<j\leq\ell}X_{j}\setminus X_{i}$, and so
$Z_{i}\subseteq\bigcup_{i<j\leq\ell}X_{j}$ for every $1\leq i\leq\ell$. In
particular, $mh(G)\leq pw(G)+1$.

To show the other inequality, let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a
parsimonious winning monotone hunter strategy in $G$ using at most $k\geq
mh(G)$ hunters (it exists by Lemma 9).

######  Claim 2.

For every $v\in V\setminus\bigcup_{1\leq i\leq\ell}S_{i}$, there exists $1\leq
j\leq\ell$ such that $N(v)\subseteq S_{j}$.

Proof of Claim. For the purpose of contradiction, let $v\notin\bigcup_{1\leq
i\leq\ell}S_{i}$ such that, for every $1\leq i\leq\ell$, there exists
$u_{i}\in N(v)\setminus S_{i}$. Then,
$\mathcal{R}=(r_{0}=v,u_{1},v,u_{3},\dots,u_{2i-1},v,u_{2i+1},v\dots)$ is a
winning rabbit trajectory against $\cal S$, contradicting the fact that $\cal
S$ is a winning hunter strategy. $\diamond$

Let us build a path-decomposition $\mathcal{P}$ of $G$ as follows. Start with
$\mathcal{P}_{0}=\emptyset$ and let $Y_{0}=V\setminus\bigcup_{1\leq
i\leq\ell}S_{i}$ ($Y_{0}$ is the set of vertices that are never shot by $\cal
S$). Assume, by induction, that the sequence $\mathcal{P}_{i}$ and the set
$Y_{i}$ have been built for some $0\leq i<\ell$. Let us define
$\mathcal{P}_{i+1}$ and $Y_{i+1}$ as follows. Let
$H_{i+1}=\\{u^{i+1}_{1},\dots,u^{i+1}_{r_{i+1}}\\}=\\{v\in Y_{i}\mid
N(v)\subseteq S_{i+1}\\}$. Let $\odot$ denote the concatenation of two
sequences. Let
$\mathcal{P}_{i+1}=\mathcal{P}_{i}\odot(S_{i+1}\cup\\{u^{i+1}_{1}\\},\dots,S_{i+1}\cup\\{u^{i+1}_{r_{i+1}}\\})$
and let $Y_{i+1}=Y_{i}\setminus H_{i+1}$. Finally, let ${\cal
P}=(X_{1},\dots,X_{r})={\cal P}_{\ell}$.

Note that, by construction, for every $1\leq i\leq r$, $|X_{i}|\leq k+1$, and
so $w({\cal P})\leq k$. Let us show that $\cal P$ satisfies the three
properties of a path-decomposition.

By construction, $\bigcup_{1\leq i\leq\ell}S_{i}\subseteq\bigcup_{1\leq i\leq
r}X_{i}$. Moreover, by Claim 2, $Y_{0}\subseteq\bigcup_{1\leq i\leq r}X_{i}$.
Hence, $\bigcup_{1\leq i\leq r}X_{i}=V$ and the Property (1) of path-
decomposition is satisfied.

By construction, for every $v\in Y_{0}$, there exists a unique $1\leq i\leq r$
such that $v\in X_{i}$. Now, for any $v\in V\setminus Y_{0}$, let $1\leq i\leq
j\leq r$ such that $v\in X_{i}\cap X_{j}$. Let $1\leq i^{\prime}\leq\ell$
(resp., $i^{\prime}\leq j^{\prime}\leq\ell$) such that $X_{i}$ has been built
from $S_{i^{\prime}}$ (resp., $X_{j}$ has been built from $S_{j^{\prime}}$).
By Lemma 10, $v\in S_{p^{\prime}}$ for all $i^{\prime}\leq p^{\prime}\leq
j^{\prime}$. Hence, by construction, $v\in X_{p}$ for all $i\leq p\leq j$.
Therefore, Property (3) of the path-decomposition is satisfied for every $v\in
V$.

Let $uv\in E$. First, let us assume that $u\in Y_{0}$. By Claim 2, $v\notin
Y_{0}$. Let $1\leq j\leq r$ such that $u\in X_{j}$, then by construction,
$N(u)\subset X_{j}$ and so $u,v\in X_{j}$. Second, assume that $u,v\in
V\setminus Y_{0}$. For purpose of contradiction, let us assume that, for every
$1\leq i\leq r$, $|\\{u,v\\}\cap X_{i}|\leq 1$. W.l.o.g., $M=\max\\{1\leq
j\leq r\mid u\in X_{j}\\}<m=\min\\{1\leq j\leq r\mid v\in X_{j}\\}$ (both
integers $m$ and $M$ are well defined since Properties (1) and (3) are
satisfied). Let $1\leq M^{\prime}\leq\ell$ (resp., $M^{\prime}\leq
m^{\prime}\leq\ell$) such that $X_{M}$ has been built from $S_{M^{\prime}}$
(resp., $X_{m}$ has been built from $S_{m^{\prime}}$). By definition of $\cal
P$, $u\notin\bigcup_{M^{\prime}<i\leq\ell}S_{i}$ and $v\in
S_{m^{\prime}}\setminus\bigcup_{1<i<m^{\prime}}S_{i}$. Because $\cal S$ is
parsimonious, $v\in Z_{m^{\prime}-1}({\cal S})$ and so, there exists a $w\in
N(v)\cap Z_{m^{\prime}-2}({\cal S})\setminus S_{m^{\prime}-1}$. By
monotonicity of $\cal S$, $w\notin\bigcup_{1\leq i<m^{\prime}}S_{i}$. By
Proposition 2, $u\in Z_{m^{\prime}-1}({\cal S})$. Since
$u\in(Z_{m^{\prime}-1}({\cal S})\cap S_{M^{\prime}})\setminus S_{m^{\prime}}$,
the vertex $u$ is recontaminated, contradicting the monotonicity of $\cal S$.
Therefore, in all cases, for every $uv\in E$, there exists $1\leq j\leq r$
such that $u,v\in X_{j}$. Hence, Property (2) of path-decompositions is
satisfied.

Hence, $\cal P$ is a path-decomposition of width at most $k$. In particular,
$pw(G)\leq mh(G)$. ∎

Theorem 1 has important consequences.

######  Corollary 1.

Given an $n$-node graph $G$ and $k\in\mathbb{N}$, it is NP-hard to decide
whether $mh(G)\leq k$. Moreover, it is NP-hard to approximate $mh(G)$ up to an
additive error of $n^{\varepsilon}$, for $0<\varepsilon<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^{\varepsilon}$, for
$0<\varepsilon<1$ [5]. ∎

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

######  Corollary 2.

There exists $\varepsilon>0$ such that, for any $k\in\mathbb{N}$, there exists
a tree $T$ with $h(T)\geq k$ and $mh(T)\geq(1+\varepsilon)h(T)$.

###### Proof.

For any $n\in\mathbb{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})|=\frac{3^{n+1}-1}{2}$ and, by the Parsons’ Lemma [26],
$pw(T_{n})=n=\Theta(\log_{3}(V(T)))$. On the other hand, it is shown in [16]
that, for any tree $T$, $h(T)\leq\lceil\frac{\log_{2}|V(T)|}{2}\rceil$. The
result follows for $(1+\varepsilon)=2\frac{\ln(2)}{\ln(3)}$. ∎

##  4 (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.

###  4.1 Split and interval graphs

A graph $G=(V,E)$ is a split graph if $V=C\cup I$ can 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 [18]. In what follows, we denote a split
graph by $G=(C\cup 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\cup I,E)$ be a split graph. Then, $|C|-1\leq pw(G)\leq|C|$.

First, we have the following easy observation.

######  Proposition 3.

Let $G=(C\cup I,E)$ be a split graph. Then, $|C|-1\leq h(G)\leq mh(G)\leq|C|$.

###### Proof.

By Lemma 1, $h(G)\geq h(G[C])$, and by Lemma 4,
$h(G[C])\geq\delta(G[C])=|C|-1$. Therefore, $h(G)\geq|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)\leq
mh(G)\leq|C|$. ∎

The following theorem fully characterises the hunter number of split graphs.

######  Theorem 2.

Let $G=(C\cup I,E)$ be a split graph. Then, $h(G)=|C|$ if and only if for
every two distinct vertices $x,y\in C$, there exists a vertex $z\in
N_{I}(x)\cap N_{I}(y)$. Otherwise, $h(G)=|C|-1$.

###### Proof.

First we show that if, for every two distinct vertices $x,y\in C$, there
exists a vertex $z\in I$ such that $xz\in E$ and $yz\in 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
$\mathcal{S}=(S_{1},\dots,S_{\ell})$ such that $|S_{i}|\leq|C|-1$ for every
$i\geq 1$, we design a rabbit trajectory
$\mathcal{R}=(r_{0},r_{1},\dots,r_{\ell-1})$ such that for every $i\geq 0$,
$r_{i}\notin S_{i+1}$. Since $|S_{1}|\leq|C|-1$, there is at least one vertex,
say, $v\in C$, such that $v\notin S_{1}$. Let $r_{0}=v$. Hence the rabbit is
safe for the first round (since $r_{0}\notin S_{1}$). Now, for $i\geq 0$, let
us assume that we have built $(r_{0},\dots,r_{i})$ such that $r_{j}\notin
S_{j+1}$ for every $0\leq j\leq i$ and $r_{i}\in C$. If there is at least one
vertex $u\neq r_{i}$ in $C$ such that $u$ is not shot in round $i+2$ (i.e.,
$u\notin S_{i+2}$), then let $r_{i+1}=u$. Otherwise,
$S_{i+2}=C\setminus\\{r_{i}\\}$. Moreover, observe that there is at least one
vertex $w\in C$ such that $w\notin 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\in I$ such that $wz,r_{i}z\in E$. Let us set $r_{i+1}=z$
and $r_{i+2}=w$. Observe that $r_{i+1}\notin S_{i+2}$ (since
$S_{i+2}=C\setminus\\{r_{i}\\}$ and $z\in I$), $r_{i+2}\notin S_{i+3}$, and
$r_{i+2}\in C$. Therefore, using the above strategy, we can design
$\mathcal{R}$ such that it is a winning trajectory against $\mathcal{S}$.
Therefore, $h(G)\geq|C|$. Since $h(G)\leq|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\in C$ such that $N_{I}(x)\cap N_{I}(y)=\emptyset$ (i.e., there
is no $z\in I$ such that $xz\in E$ and $yz\in E$), then $h(G)\leq|C|-1$ (and
so $h(G)=|C|-1$ by Proposition 3). We prove this by giving a (simple) winning
hunter strategy $\mathcal{S}$ using $|C|-1$ hunters. Let
$\mathcal{S}=(S_{1},S_{2},S_{3},S_{4},S_{5})$ where
$S_{1}=S_{2}=S_{5}=C\setminus\\{y\\}$ and $S_{3}=S_{4}=C\setminus\\{x\\}$. Let
$\mathcal{R}=(r_{0},\dots,r_{4})$ be any rabbit trajectory. If the rabbit is
not shot at the first round, i.e., $r_{0}\notin S_{1}$, then either $r_{0}=y$
or $r_{0}\in I$. Accordingly, we consider both these cases below to show that
$\mathcal{S}$ is a winning hunter strategy.

Case 1. $\mathbf{r_{0}=y:}$ In this case, assume $r_{1}\notin S_{2}$
(otherwise, the rabbit will be shot). Note that $r_{1}\in N_{I}(y)$. Since
$N_{I}(x)\cap N_{I}(y)=\emptyset$, $r_{2}\in C\setminus\\{x\\}$. As
$S_{3}=C\setminus\\{x\\}$, $r_{2}\in S_{3}$, and therefore, $\mathcal{S}$ is a
winning hunter strategy.

Case 2. $\mathbf{r_{0}\in I:}$ In this case, if $r_{1}\notin S_{2}$, then
$r_{1}=y$. Now, assuming that $r_{2}\notin 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}\in
N_{I}(y)$). We have the following two cases accordingly:

  1. 2.a

$\mathbf{r_{2}\in N_{I}(y)}:$ This case is similar to Case 1. Since
$N_{I}(x)\cap N_{I}(y)=\emptyset$, $r_{3}\in C\setminus\\{x\\}$. As
$S_{4}=C\setminus\\{x\\}$, $r_{3}\in S_{4}$, and therefore, $\mathcal{S}$ is a
winning hunter strategy.

  2. 2.b

$\mathbf{r_{2}=x:}$ In this case, if $r_{3}\notin S_{4}$, then $r_{3}\in
N_{I}(x)$. Therefore, similarly to previous arguments, $r_{4}\in
C\setminus\\{y\\}$. Since $S_{5}=C\setminus\\{y\\}$, $\mathcal{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\cup I,E)$, $h(G)=pw(G)$.

###### Proof.

If $|C|=1$ and $I=\emptyset$, then $pw(G)=h(G)=0$. If $|C|=1$ and
$I\neq\emptyset$, then $pw(G)=h(G)=1$. Let us now assume that $|C|>1$.

Since $pw(G),h(G)\in\\{|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\in C$, there exist $z\in N_{I}(x)\cap N_{I}(y)$. For purpose of
contradiction, let us assume that there exists a reduced optimal path-
decomposition $P=(X_{1},\dots,X_{\ell})$ of width $|C|-1$. It is well known
that there exists $1\leq i\leq\ell$ with $C\subseteq X_{i}$. Moreover, since
$P$ has width $|C|-1$, $X_{i}=C$. Let us prove now that $1<i<\ell$. Let us
suppose by contradiction that $i=1$, i.e., $X_{1}=C$ (the case $i=\ell$ is
symmetric). Since $P$ has width $|C|-1$ and is reduced, let $v\in
X_{1}\setminus X_{2}$ and let $z\in N_{I}(v)$ ($z$ exists since $|C|>1$ and
any two distinct vertices of $C$ have a common neighbour in $I$). Since $v\in
X_{1}=C$ and $v\notin\bigcup_{1<j\leq\ell}X_{j}$, no bag contains both $v$ an
$z$, contradicting the definition of a path-decomposition. Hence, $1<i<\ell$.
Now, let $x\in C\setminus X_{i-1}$ and $y\in C\setminus X_{i+1}$ ($x$ and $y$
exists since $P$ is reduced and $X_{i}=C$). Let $z\in N_{I}(x)\cap N_{I}(y)$.
If $x=y$, no bag contains both $x$ and $z$ (since $x$ appears only in
$X_{i}=C$). If $x\neq y$, there must exist $1\leq j\leq\ell$ such that
$\\{y,z\\}\subseteq X_{j}$. Since $y\notin\bigcup_{i<h\leq\ell}X_{h}$, $j<i$
and since $z\in X_{j}\setminus X_{i}$, $z\notin\bigcup_{i<h\leq\ell}X_{h}$.
Finally, since $x\notin\bigcup_{1\leq h<i}X_{h}$, 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\in C$ such that $N_{I}(x)\cap N_{I}(y)=\emptyset$. Let us prove
that, in that case, $pw(G)=|C|-1$. Let $N_{I}(x)=\\{x_{1},\dots,x_{m}\\}$ and
$I\setminus N_{I}(x)=\\{y_{1},\dots,y_{t}\\}$. Then,
$(x_{1}\cup(C\setminus\\{y\\}),\dots,x_{m}\cup(C\setminus\\{y\\}),C,y_{1}\cup(C\setminus\\{x\\}),\dots,y_{t}\cup(C\setminus\\{x\\}))$
is a path decomposition of $G$ with width $|C|-1$ and, since $pw(G)\geq|C|-1$
by Lemma 11, we get that $pw(G)=|C|-1$. ∎

Next, let us characterise the monotone hunter number of split graphs. We start
with the following general lemma.

######  Lemma 12.

Let $G$ be a graph that contains a complete subgraph $C$ such that
$N(v)\setminus C\neq\emptyset$ for every $v\in C$. Then, $mh(G)\geq|C|$.

###### Proof.

By Lemmas 1, 4 and Proposition 1, $mh(G)\geq h(G)\geq h(C)\geq|C|-1$. Let
$H=G[N[C]]$. We will show that $mh(H)\geq|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 ${\cal
S}=(S_{1},\dots,S_{\ell})$ in $H$ using $|C|-1$ hunters.

There must be an index $1\leq i\leq\ell$ such that $|S_{i}\cap C|=|C|-1$.
Otherwise, $(r_{0},\dots,r_{\ell})$ where $r_{0}\in C\setminus S_{1}$ and
$r_{j}\in C\setminus(S_{j+1}\cup\\{r_{j-1}\\})$ for every $1\leq j\leq\ell$ is
a winning rabbit trajectory, contradicting the fact that $\cal S$ is winning.
Hence, let $i$ be the smallest integer such that $|S_{i}\cap C|=|C|-1$, let
$\\{v\\}=C\setminus S_{i}$ and let $w\in N(v)\setminus C$ (which exists by
hypothesis). Let us define a rabbit trajectory ${\cal
R}=(r_{0},\dots,r_{i-1}=v)$ such that $r_{j}\in
C\setminus(S_{j+1}\cup\\{r_{j-1}\\})$ for every $1\leq j<i-1$, which is
possible since $|S_{j}\cap C|<|C|-1$ for all $j<i$. Thus $v\in
Z_{i-1}\setminus S_{i}$. Therefore, $v\notin\bigcup_{1\leq j\leq i}S_{j}$
since otherwise, $v$ would have been recontaminated.

Let us show now that $w\notin\bigcup_{1\leq j<i}S_{j}$. Towards contradiction,
let us assume that $w\notin\bigcup_{1\leq j<i}S_{j}$. If $w\notin S_{i+1}$,
then let $r_{i}=w$: this contradicts the monotonicity of $\cal S$ (since $w\in
Z_{i}\cap\bigcup_{1\leq j<i}S_{j})\setminus S_{i+1}$). Hence, $w\in S_{i+1}$
and so there exists $z\in C\setminus(S_{i+1}\cup\\{v\\})$. In this latter
case, let $r_{i}=z$, contradicting the monotonicity of $\cal S$ (since $z\in
Z_{i}\cap S_{i})\setminus S_{i+1}$).

Since $w\notin\bigcup_{1\leq j<i}S_{j}$, let $j>i$ be the smallest integer
such that $w\in S_{j}$, or, if $w$ is never shot, let $j>i$ be the smallest
integer such that $v\in S_{j}$ (it must exists otherwise the rabbit may
oscillate between $v$ and $w$ without being never shot). In both cases, let
$z\in C\setminus(S_{j}\cup\\{v\\})$. Thus, by Proposition 2, $z\in
Z_{j-1}\setminus S_{j}$, contradicting the monotonicity of $\cal 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\cup I,E)$, a vertex $v\in C$
is simplicial if and only if $N(v)\setminus C=\emptyset$ (recall that $C$ is
supposed to be an inclusion-maximal clique).

######  Theorem 3.

Let $G=(C\cup 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)\geq|C|$ and so, by Proposition 3, $mh(G)=|C|$. Otherwise, if there
exists a simplicial vertex $v\in C$, then $S=(C\setminus v,C\setminus v)$ is a
monotone winning hunter strategy in $G$.∎

Note that above results imply that there exist split graphs $G$ for which
$mh(G)\neq 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)=\omega(G)-1$ where $\omega(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)=\omega(G)-1$ if every maximum
clique has a simplicial vertex. Otherwise, $mh(G)=\omega(G)$.

###### Proof.

By Theorem 1, $pw(G)\leq mh(G)\leq pw(G)+1=\omega(G)$. Moreover, by Lemma 4,
$h(G)\geq\omega(G)-1$. If there exists a clique of maximum size that does not
contain any simplicial vertex, then by Lemma 12, $mh(G)=\omega(G)$. Otherwise,
let $(X_{1},\dots,X_{\ell})$ be an optimal path-decomposition of $G$ such that
all bags induce a complete graph. For every $1\leq i\leq\ell$, if $X_{i}$
contains a simplicial vertex $v_{i}$, let $Y_{i}=\\{v_{i}\\}$ and let
$Y_{i}=\emptyset$ otherwise. Then, $(X_{1}\setminus Y_{1},X_{1}\setminus
Y_{1},X_{2}\setminus Y_{2},X_{2}\setminus Y_{2},X_{3}\setminus
Y_{3},\dots,X_{\ell}\setminus Y_{\ell},X_{\ell}\setminus Y_{\ell})$ is a
monotone winning hunter strategy using $\omega(G)-1$ hunters. ∎

It follows that $\omega(G)-1\leq h(G)\leq\omega(G)$. But, the question of
deciding $h(G)$ in interval graph when some maximum clique has no simplicial
vertex seems more challenging.

###  4.2 Cographs

The class of cographs can be defined recursively as follows [11]. One vertex
is a cograph. Given two cographs $A$ and $B$, their disjoint union $A\cup B$
is a cograph, and their join $A\Join 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 [11].

######  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\cup B)=max(mh(A),mh(B))$, and

  * •

$mh(A\Join 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 [11].

The first statement is obvious, so let us prove the second one. Let $G=A\Join
B$ and let ${\cal S}^{A}=(S^{A}_{1},\dots,S^{A}_{\ell})$ and ${\cal S}^{B}$ be
two monotone winning hunter strategies for $A$ and $B$ and using respectively
$mh(A)$ and $mh(B)$ hunters. Note that ${\cal S}^{A}\cup V(B)=(S^{A}_{1}\cup
V(B),\dots,S^{A}_{\ell}\cup V(B))$ and ${\cal S}^{B}\cup V(A)$ are both
monotone winning hunter strategies in $G$. Therefore, $mh(G)\leq
min(mh(A)+|V(B)|,|V(A)|+mh(B))$.

Let ${\cal S}=(S_{1},\dots,S_{\ell})$ be a parsimonious monotone winning
hunter strategy in $G$ using at most $k\geq mh(G)$ hunters (it exists by Lemma
9) and such that $\ell$ is minimized among all such strategies. If $\ell=1$,
then $k=|S_{1}|=|V(G)|\geq min(mh(A)+|V(B)|,|V(A)|+mh(B))$. Hence, let us
assume that $\ell>1$. Let ${\cal Z}=(Z_{0},\dots Z_{\ell})$ be the set of
contaminated vertices with respect to ${\cal S}$. Note first that since $\ell$
is minimum, $(S_{2},\dots,S_{\ell})$ is not a winning hunter strategy, and so
$Z_{1}\neq V$. Let $v\in V\setminus Z_{1}$.

Let us assume that $v\in V(A)$ (the case $v\in V(B)$ is symmetric). Since
$v\notin Z_{1}$ and $Z_{0}=V$, $N(v)\subseteq S_{1}$ . Since $B\subseteq
N(v)$, we have that $V(B)\subseteq S_{1}$. Moreover, $V(B)\subseteq Z_{1}$.
Otherwise, there exists $w\in B$ such that $N(w)\subseteq S_{1}$ and since
$V(A)\subseteq N(w)$, we would have $S_{1}=V(A)\cup V(B)=V(G)$, a
contradiction to the fact that $\ell>1$.

Let us prove by induction on $i$ that, for every $1\leq i<\ell$,
$V(B)\subseteq Z_{i}$ and $V(B)\subseteq S_{i}$. This statement holds for
$i=1$ by the previous paragraph. By induction, let us assume that
$V(B)\subseteq Z_{i}$ and $V(B)\subseteq S_{i}$ for some $1\leq i<\ell-1$.
Since ${\cal S}$ is monotone, $V(B)\subseteq S_{i+1}$. Let us assume that
there exists $b\in V(B)$ such that $b\notin Z_{i+1}$. It implies that
$V(A)\cap Z_{i}\subseteq S_{i+1}$. Therefore, $Z_{i}=(V(A)\cap
Z_{i})\cup(V(B)\cap Z_{i})\subseteq S_{i+1}$, which implies that
$Z_{i+1}=\emptyset$, contradicting the minimality of $\ell$. Thus
$V(B)\subseteq Z_{i+1}$ and the induction hypothesis holds for $i+1$. In
particular, $V(B)\subseteq Z_{\ell-1}$ and so, by monotonicity, $V(B)\subseteq
S_{\ell}$. Therefore, $V(B)\subseteq S_{i}$ for all $1\leq i\leq\ell$. Since
$V(B)\subseteq S_{i}$ for all $1\leq i\leq\ell$, the strategy ${\cal S}\cap
V(A)=(S_{1}\cap V(A),\dots,S_{\ell}\cap V(A))$ is a monotone winning hunter
strategy in $G[A]$ using $k-|V(B)|$ hunters. Hence, $k-|V(B)|\geq mh(A)$ which
concludes the proof. ∎

Once again, the case of the hunter number seems more challenging. In
particular, the following lemma shows that recontamination may help in
cographs.

######  Lemma 13.

For every $k\geq 2$, there exists a cograph $G$ such that $h(G)\geq k$ and
$mh(G)\geq\frac{3}{2}h(G)-1$.

###### Proof.

Let $a\geq 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\Join 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)\geq 2a$ by
Lemma 4. Now, $(A,K_{A}\cup K_{B},K_{B},A)$ is a (non-monotone) winning hunter
strategy in $G$ using $2a$ hunters and so $h(G)=2a$. ∎

###  4.3 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 [26] holds for the monotone hunter number in trees and then the
algorithm follows the one for computing the pathwidth of trees in [13].

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)\leq 2$
is easy.

Towards a contradiction, let us assume that there exists a winning monotone
hunter strategy in $P$ using one hunter and let ${\cal S}=(S_{1},\dots
S_{\ell})$ be a shortest such strategy (i.e., minimizing $\ell$). Let
$Z=(Z_{1},\dots,Z_{\ell})$ be the set of contaminated vertices with respect to
${\cal S}$. Let $w\in V(P)$ such that $S_{1}=\\{w\\}$. Note that $w\in Z_{1}$
and so, $\ell>1$. Since $P$ has length at least $4$, there exist $x,y\in V(P)$
such that $x\in N(w)$ and $y\in N(x)\setminus\\{w\\}$. We will prove by
induction on $i$ that $S_{i}=\\{w\\}$ for all $1\leq i\leq\ell$. The base case
($i=1$) is already proven. Assume now that for some $1\leq q<\ell$, it holds
that $S_{j}=\\{w\\}$ for all $1\leq j\leq q$. Thus, $x,y\notin\bigcup_{1\leq
j\leq q}S_{j}$ and so, by Proposition 2, $w\in Z_{q}$. Hence, by the
monotonicity of $\mathcal{S}$, we have that $w\in S_{q+1}$, showing the step
of the induction. Therefore, $x,y\notin\bigcup_{1\leq j\leq\ell}S_{j}$ and so,
by Proposition 2, $w,x,y\in Z_{\ell}$, contradicting the fact that
$\mathcal{S}$ is a winning strategy in $P$. Therefore, $mh(P)\geq 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 $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be any parsimonious monotone winning
hunter strategy in $G$. Moreover, let $1\leq i\leq\ell$ and $x,y\in V(H)$ such
that $x\in\bigcup_{j<i}S_{j}$, $y\in Z_{i-1}$ and minimising the distance
between such $x$ and $y$ in $H$. If $x,y\notin S_{i}$, then $xy\in E(H)$.

###### Proof.

Note first that $x\neq y$. Indeed, assuming otherwise would imply that
$\mathcal{S}$ is not monotone since $y=x\in(\bigcup_{j<i}S_{j}\cap
Z_{i-1})\setminus S_{i}$. Hence, we may assume that $x\neq 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\\}\in E(G)$, and the claim holds. Hence, we may assume
that $a\neq y$. By minimality of the distance between $x$ and $y$, $a\notin
Z_{i-1}$ and $a\notin\bigcup_{j<i}S_{j}$. Let $b\neq x$ be the other neighbour
of $a$ in $P$. We show that $b\notin\bigcup_{j<i}S_{j}$. If $b\neq y$, then,
by minimality of the distance between $x$ and $y$,
$b\notin\bigcup_{j<i}S_{j}$. If $b=y$, since $y\in Z_{i-1}\setminus S_{i}$,
then $y\notin\bigcup_{j<i}S_{j}$, because otherwise this would contradict the
monotonicity of $\mathcal{S}$. Therefore, by Proposition 2, $a\in Z_{q}$ for
every $q<i$. In particular, $a\in Z_{i-1}$, a contradiction.∎

######  Lemma 14.

Let $G=(V,E)$ be any graph and ${\cal S}=(S_{1},\dots,S_{\ell})$ 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}\cap
V(H)\neq\emptyset$ and $S_{j}\cap V(H)\neq\emptyset$ for some $1\leq
i<j\leq\ell$, then $S_{z}\cap V(H)\neq\emptyset$ for every $i\leq z\leq j$.

###### Proof.

Let $2\leq i+1<j\leq\ell$ be such that $V(H)\cap S_{i}\neq\emptyset$ and
$V(H)\cap S_{j}\neq\emptyset$. Towards a contradiction, let us assume that
there exists $i<z<j$ such that $S_{z}\cap V(H)=\emptyset$. Let
$X=V(H)\cap\bigcup_{q<z}S_{q}$. Since $V(H)\cap S_{i}\neq\emptyset$ and $i<z$,
we get that $X\neq\emptyset$. Let $Y=V(H)\cap Z_{z-1}$. Since $S_{j}\cap
V(H)\neq\emptyset$ and ${\cal S}$ is parsimonious, we have that $Z_{j-1}\cap
V(H)\neq\emptyset$. Let $u\in Z_{j-1}\cap S_{j}\cap V(H)$. By Lemma 6, $u\in
Z_{q}$ for every $q<j$. In particular, $u\in Z_{z-1}$ and so $Y\neq\emptyset$.
Let $x\in X$ and $y\in Y$ such that the distance bewteen $x$ and $y$ in $H$ is
minimum. By Proposition 5, $xy\in E$. Thus, since $y\in Z_{z-1}\setminus
S_{z}$, we get that $x\in Z_{z}$. Therefore, since $\cal S$ is monotone and
$x\in\bigcup_{q<z}S_{q}$, we must have $x\in S_{z+1}$. By Lemma 10, since
$x\in\bigcup_{q<z}S_{q}$ and $x\in S_{z+1}$, then $x\in S_{z}$. Hence,
$V(H)\cap S_{z}\neq\emptyset$, a contradiction. ∎

Let $T$ be a tree and $v\in 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 [26] states that,
for any tree $T$ and $k\in\mathbb{N}$, $pw(T)\geq 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\setminus P$ is a forest of stars and isolated vertices;

  * •

For every $k\geq 3$, $mh(T)\geq k$ if and only if there exists a vertex $v\in
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)|\geq 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)\geq 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\setminus P$ is a forest of stars and isolated vertices,
it is easy to show that $mh(T)\leq 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\geq 3$.

Proof of $\Leftarrow$: 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})\geq k-1$. We will show that $mh(T)\geq k$.
Towards a contradiction, let us assume that $mh(T)<k$. By Lemma 9, there
exists a parsimonious monotone strategy ${\cal S}=(S_{1},\dots,S_{\ell})$ in
$T$ that uses at most $k-1$ hunters. Let $Z=(Z_{1},\dots,Z_{\ell})$ be the set
of contaminated vertices with respect to ${\cal S}$.

For $j\in\\{1,2,3\\}$, let $1\leq i_{j}\leq\ell$ be the minimum integer such
that $V(B_{j})\cap Z_{i_{j}}=\emptyset$. Note that, by Lemma 6, $V(B_{j})\cap
Z_{q}=\emptyset$ for all $i_{j}\leq q\leq\ell$, and since $\cal S$ is
parsimonious, $V(B_{j})\cap S_{q}=\emptyset$ for all $i_{j}<q\leq\ell$. Note
also that, since $mh(B_{j})\geq k-1\geq 2$, $B_{j}$ has at least two vertices.
Since $Z_{i_{j}-1}\cap V(B_{j})\neq\emptyset$ and $Z_{i_{j}}\cap
V(B_{j})=\emptyset$, it implies that $S_{i_{j}}\cap V(B_{j})\neq\emptyset$
(otherwise, let $w\in(Z_{i_{j}-1}\cap V(B_{j}))$ and $u\in N(w)\cap V(B_{j})$,
then $u\in Z_{i_{j}}\cap V(B_{j})$, a contradiction with the definition of
$i_{j}$). W.l.o.g., let us assume that $i_{1}\leq i_{2}\leq 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\in
Z_{j_{2}-1}$, which will lead to a contradiction.

For any $1\leq i\leq 3$, let $j_{i}$ be an index such that $|S_{j_{i}}\cap
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\in Z_{j_{2}-1}$. Observe that $j_{2}\leq i_{2}\leq i_{3}$.
Moreover, $j_{2}\neq i_{3}$ since $S_{i_{3}}\cap V(B_{3})\neq\emptyset$,
$|S_{j_{2}}\cap V(B_{2})|=k-1$ and ${\cal S}$ uses at most $k-1$ hunters.
Hence, $j_{2}<i_{3}$. Therefore, by Proposition 2 and Lemma 14,
$V(B_{3})\cup\\{v\\}\subseteq Z_{q}$ for all $q\leq j_{2}$. In particular,
$v\in Z_{j_{2}-1}$. Moreover, since $S_{j_{2}}\subseteq V(B_{2})$, $v\notin
S_{j_{2}}$. Hence, $x\in Z_{j_{2}}$ where $x$ is the neighbour of $v$ in
$B_{1}$, i.e., $Z_{j_{2}}\cap V(B_{1})\neq\emptyset$.

Since $Z_{i_{1}}\cap V(B_{1})=\emptyset$, if $i_{1}<j_{2}$, then there is a
contradiction to Lemma 6. Otherwise, $j_{2}<i_{1}\leq i_{2}$ (because
$j_{2}\neq i_{1}$) and so either $j_{1}<j_{2}<i_{1}$ or $j_{2}<j_{1}<i_{2}$
(because $j_{1}\neq j_{2}$, $j_{1}\leq i_{1}\leq i_{2}$ and $j_{1}\neq
i_{2}$), both contradicting Lemma 14.

Proof of $\Rightarrow$: Now let us assume that, for every $v\in 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 ${\cal S}$
in $T$ using at most $k-1$ hunters.

First, let us assume that there exists a path $P=(v_{1},\dots,v_{p})$ such
that for any connected component $C$ of $T\setminus 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\setminus 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\geq 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\neq\emptyset$ and let us show that it induces a path. Let $x,y\in X$ and
let $z$ be any internal vertex of the path between $x$ and $y$. Let $B$
(resp., $B^{\prime}$) be the branch at $z$ that contains $x$ (resp., that
contains $y$). One branch $B_{x}$ at $x$ with $mh(B_{x})\geq k-1$ is a
subgraph of $B$ and so, by Lemma 8, $mh(B)\geq k-1$. Similarly,
$mh(B^{\prime})\geq k-1$ and so, $z\in 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},\dots,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})\geq 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})\geq k-1$) and let $v_{p}$ be the neighbour of $v_{p-1}$ in $B_{p}$.
Then, $P=(v_{1},v_{2},\dots,v_{p-1},v_{p})$ satisfies the desired conditions.

Finally, if $X=\emptyset$, 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},\dots,v_{i})$ has already been built for some $i\geq 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=\emptyset$), 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. ∎

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\in V(T)$. Let
$T[u]$ denote the subtree of $T$ induced by $u\in V(T)$ and all the descendent
of $u$. For any $x_{1},\cdots,x_{p}\in V(T[u])$, let $T[u,x_{1},\ldots,x_{p}]$
denote the subtree obtained from $T[u]$ after the vertices of $\bigcup_{i\leq
p}V(T[x_{i}])$ have been removed. Finally, for $k\geq 2$, a vertex $x\in 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])\geq 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^{\prime}$ of $w$ such
that $mh(T[w^{\prime}])=1$, i.e., $w^{\prime}$ 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\in V(T)$. Let $k=\max_{1\leq i\leq
d}\\{mh(T[v_{i}]\\}$, where $v_{1},\ldots,v_{d}$ are the children of $v$ in
$T$. For any vertex $w\in V(T)$, there is at most $1$ branch at $w$ in $T$
that has monotone hunter number $k+1$. Moreover, $mh(T)\leq 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)\setminus\\{v\\}$ and let us denote by $x$ the child of $v$ such that
$w\in V(T[x])$. By definition of $k$, $mh(T[x])\leq k$. For any child $z$ of
$w$, $T[z]$ is a subtree of $T[x]$. Thus, by Lemma 8, $mh(T[z])\leq 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)\leq k+1$. ∎

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\in 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.

######  Corollary 4.

Let $T$ be a rooted tree, $u\in V(T)$ and let $u_{1},\dots,u_{d}$ be the $d$
children of $u$ in $T$. Let us order the children of $u$ such that
$k=mh(T[u_{1}])\geq mh(T[u_{2}])\geq\dots mh(T[u_{d}])$.

  1. 1.

If $d=0$, then $mh(T[u])=0$;

  2. 2.

If $k=0$ and $d>0$, then $mh(T[u])=1$;

  3. 3.

If $k=1$, $d=1$ and the only child of $u$ is not $1$-critical, then
$mh(T[u])=1$;

  4. 4.

If $k=1$ and $d=1$ and the only child of $u$ is $1$-critical, then
$mh(T[u])=2$;

  5. 5.

If $k=1$ and $d\geq 2$, then $mh(T[u])=2$;

  6. 6.

If $k>1$ and $mh(T[u_{3}])=k$, then $mh(T[u])=k+1$;

  7. 7.

If $k>1$, $mh(T[u_{2}])=k$ and ($mh(T[u_{3}])<k$ or $d=2$), and $T[u_{1}]$ or
$T[u_{2}]$ contains a $k$-critical vertex, then $mh(T[u])=k+1$.

  8. 8.

If $k>1$, $mh(T[u_{2}])=k$ and ($mh(T[u_{3}])<k$ or $d=2$), and neither
$T[u_{1}]$ nor $T[u_{2}]$ contains a $k$-critical vertex, then $mh(T[u])=k$.

  9. 9.

If $k>1$, $mh(T[u_{1}])=k$ and ($mh(T[u_{2}])<k$ or $d=1$), $T[u_{1}]$
contains a $k$-critical vertex $x$ and $mh(T[u,x])=k$, then $mh(T[u])=k+1$;

  10. 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 $mh(T[u])=k$;

  11. 11.

If $k>1$, $mh(T[u_{1}])=k$ and ($mh(T[u_{2}])<k$ or $d=1$) and $T[u_{1}]$ does
not contain any $k$-critical vertex, then $mh(T[u])=k$.

###### Proof.

Each statement can be proved using Lemma 15.

  1. 1.

If $d=0$, then $T[u]$ is a single vertex and by Lemma 15, $mh(T[u])=0$.

  2. 2.

If $k=0$ and $d>0$, then there exists at least one child $w$ of $u$ such that
$mh(T[w])=0$ and there is no child $w^{\prime}$ of $u$ such that
$mh(T[w^{\prime}])>0$. Thus, $T[u]$ contains at least one edge and is a star
graph centred in $u$. By Lemma 15, we get that $mh(T[u])=1$.

  3. 3.

If $k=1$, $d=1$ and the only child of $u$ is not $1$-critical, i.e., $u_{1}$
is the only child of $u$ and $mh(T[u_{1}])=1$. Thus, $T[u_{1}]$ is a star
centred at $u_{1}$. Therefore, $T[u]$ is also a star centred at $u_{1}$, and
so, by Lemma 15, $mh(T[u])=1$.

  4. 4.

If $k=1$, $d=1$ and the only child of $u$ is $1$-critical, i.e., $u_{1}$ is
the only child of $u$, $mh(T[u_{1}])=1$ and there exists a child $w$ of
$u_{1}$ such that $mh(T[w])=1$. By Lemma 15, $T[w]$ contains at least $1$
edge. Let $v$ be the child of $w$ in $T[w]$. Thus, $T[u]$ contains the path
$(v,w,u_{1},u)$, and so, is not a star. Moreover, $T[u]\setminus u$ is a
forest of stars, and so, by Lemma 15, $mh(T[u])=2$.

  5. 5.

If $k=1$ and $d\geq 2$, then $u$ has at least two children. Thus, by Lemma 15,
$T[u_{1}]$ contains at least one edge. Let $w$ be a child of $u_{1}$ in
$T[u_{1}]$. Note that $T[u]$ contains the path $P=(u_{2},u,u_{1},w)$ as
subgraph and that $T[u]\setminus u$ is a forest of stars. Therefore, by Lemma
15, $mh(T[u])=2$.

  6. 6.

If $k>1$ and $mh(T[v_{3}])=k$, then $mh(T[u])\geq k+1$ by Lemma 15. Moreover,
by Lemma 16, we get that $mh(T[u])\leq k+1$, and so $mh(T[u])=k+1$.

  7. 7.

If $k>1$, $mh(T[u_{1}])=mh(T[u_{2}])=k$ and ($mh(T[v_{3}])<k$ or $d=2$) and
$T[u_{1}]$ or $T[u_{2}]$ contains a $k$-critical vertex, let $x$ be a
$k$-critical vertex in $T[u]\setminus\\{u\\}$. W.l.o.g., let us assume that
$x\in V(T[u_{1}])$. Let us denote by $y$ the parent of $x$ in $T[u]$. Note
that $y$ may be equal to $u$. Let $B_{1}$ and $B_{2}$ denote the two branches
at $x$ in $T[x]$ such that $mh(B_{1})=mh(B_{2})=k$. Let $B_{y}$ denote the
branch at $x$ in $T[u]$ that contains $y$. Note that $B_{y}$ contains
$T[u_{2}]$ as subgraph. Thus, by Lemma 8, $mh(B_{y})\geq mh(T[u_{2}])=k$.
Therefore, since there are $3$ branches at $x$ with monotone hunter number at
least $k$, by Lemma 15, we get that $mh(T[u])\geq k+1$. Finally, by Lemma 16,
$mh(T[u])\leq k+1$, and so $mh(T[u])=k+1$.

  8. 8.

If $k>1$, $mh(T[u_{1}])=mh(T[u_{2}])=k$ and ($mh(T[v_{3}])<k$ or $d=2$) and
neither $T[u_{1}]$ nor $T[u_{2}]$ contains a $k$-critical vertex, then there
do not exist three branches at $u$ having monotone hunter number at least $k$.
Note that for any $w\in V(T[u_{1}])$ (resp., $w\in V(T[u_{2}])$), $w$ is not
$k$-critical, and so, there is at most $1$ branch at $w$ in $T[w]$ that has
monotone hunter number at least $k$. Therefore, since every branch at $w$ in
$T[u]$ is also a branch at $w$ in $T[u_{1}]$, except the one containing the
parent of $w$, we get that there are at most $2$ branches at $w$ that has
monotone hunter number at least $k$. Finally, if $d>2$, for any $2<j\leq d$
and any vertex $w\in V(T[u_{j}])$, let us denote by $y$ the parent of $w$ in
$T[u_{j}]\cup\\{u\\}$. Note that for any vertex $z\in N(w)\setminus\\{y\\}$,
$T[z]$ is a subgraph of $T[u_{j}]$ and so, by Lemma 8, $mh(T[z])\leq
mh(T[u_{j}])<k$. Therefore, there is no vertex $w\in V(T[u])$ such that $w$
has $3$ branches that have monotone hunter number at least $k$. Hence, by
Lemma 15, $mh(T[u])\leq k$. By Lemma 8 and because $mh(T[u_{1}])=k$,
$mh(T[u])=k$.

  9. 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])\geq k+1$. Finally, by Lemma 16, $mh(T[u])\leq k+1$ and so
$mh(T[u])=k+1$.

  10. 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]\setminus\\{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\in V(T[u_{1}])$ since
$mh(T[u_{j}])<k$ for any $2\leq j\leq d$. Note that $w=x$. Indeed, towards
contradiction, let us assume that $w\neq 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\in V(T[u])\setminus\\{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])\leq 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])\leq k$ and by Lemma 8, $mh(T[u])\geq mh(T[u_{1}])\geq k$.

  11. 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])\leq k$ and by Lemma 8,
$mh(T[u])\geq mh(T[u_{1}])\geq k$, and so, $mh(T[u])=k$.

∎

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},\cdots,x_{p}\in V(T[u])$, the tree
$T[u,x_{1},\ldots,x_{p}]$ denotes the subtree obtained from $T[u]$ after the
vertices of $\bigcup_{i\leq p}V(T[x_{i}])$ have been removed.

######  Definition 1.

For any tree $T[u]$, the label $\lambda(u,T[u])$ of $u$ is a list of integers
$(a_{1},\ldots,a_{p})$, where $a_{1}>a_{2}>\dots>a_{p}\geq 0$, possibly
$a_{p}$ may be marked with a star, and there exists a set of vertices
$\\{\ell_{1},\dots,\ell_{p}\\}$, such that:

  * •

$mh(T[u])=a_{1}$.

  * •

For $1\leq i<p$, $mh(T[u,\ell_{1},\ldots,\ell_{i}])=a_{i+1}$ and $\ell_{i}$ is
an $a_{i}$-critical vertex in $T[u,\ell_{1},\ldots,\ell_{i-1}]$. We will say
that $\ell_{i}$ is associated to $a_{i}$.

  * •

$\ell_{p}=u$. If $a_{p}$ is not marked with a star ($*$), then there is no
$a_{p}$-critical vertex in $T[u,\ell_{1},\ldots,\ell_{p-1}]$. If $a_{p}$ is
marked (with a star), then $\ell_{p}$ is an $a_{p}$-critical vertex. In both
cases, $T[u,\ell_{p}]=T[u,u]$ is the empty tree.

#### 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
$\lambda(u_{1},T_{1}[u_{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 $\ell^{1}_{1}\in T_{1}[u_{1}]$
that is $3$-critical. Moreover, $mh(T_{1}[u_{1},\ell^{1}_{1}])=a_{2}=2$ and
there exists a vertex $\ell^{1}_{2}\in T_{1}[u_{1},\ell^{1}_{1}]$ that is
$2$-critical. Finally, $mh(T_{1}[u_{1},\ell^{1}_{1},\ell^{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},\ell^{1}_{1},\ell^{1}_{2}]$. By previous remarks,
$T_{1}[u_{1},\ell^{1}_{1},\ell^{1}_{2}]$ is a star centred in $u_{1}$ and
$\ell^{1}_{3}=u_{1}$ (moreover, the star contains at least $2$ vertices since
$mh(T_{1}[u_{1},\ell^{1}_{1},\ell^{1}_{2}])>0$).

Let $T^{\prime}_{1}$ be the tree obtained from $T_{1}$ by adding a vertex $u$
(the root of $T^{\prime}_{1}$) adjacent to $u_{1}$. Note that, $\ell^{1}_{1}$
(resp., $\ell^{1}_{2}$) is still $3$-critical (resp., $2$-critical) in
$T^{\prime}_{1}[u]$ (resp., in $T^{\prime}_{1}[u,\ell^{1}_{1}]$). Note also
that $T^{\prime}_{1}[u,\ell^{1}_{1},\ell^{1}_{2}]$ is actually equal to the
tree obtained from $T_{1}[u_{1},\ell^{1}_{1},\ell^{1}_{2}]$ by making $u$
adjacent to $u_{1}$. Hence, $T^{\prime}_{1}[u,\ell^{1}_{1},\ell^{1}_{2}]$ is a
star (containing at least $3$ vertices) centred in $u_{1}$, and so $u$ is
$1$-critical in $T^{\prime}_{1}[u,\ell^{1}_{1},\ell^{1}_{2}]$. Therefore, the
label of $u$ in $T^{\prime}_{1}$ is $(3,2,1^{*})$.

Second, let $T_{2}$ be a tree rooted at $u_{2}$ with the label
$\lambda(u_{2},T_{2}[u_{2}])=(a_{1},a_{2},a_{3})=(3,2,1^{*})$. Similarly to
the previous example, there exist $\ell^{2}_{1}$ and $\ell^{2}_{2}$ that are
the $3$-critical vertex of $T_{2}[u_{1}]$ and the $2$-critical vertex of
$T_{2}[u_{1},\ell^{2}_{1}]$, respectively. Moreover, since $a_{3}$ is marked
with a star, there exists a $1$-critical vertex $\ell^{2}_{3}$ in
$T_{2}[u_{2},\ell^{2}_{1},\ell^{2}_{2}]$. Let us recall that by definition of
a label, $\ell^{2}_{3}=u_{2}$, and so $T_{2}[u_{2},\ell^{2}_{1},\ell^{2}_{2}]$
is a star with at least $3$ vertices centred in the only child of $u_{2}$.

Let $T^{\prime}_{2}$ be the tree obtained from $T_{2}$ by adding a vertex
$u^{\prime}$ (the root of $T^{\prime}_{2}$) adjacent to $u_{2}$. Note that
$T^{\prime}_{2}[u^{\prime},\ell^{2}_{1},\ell^{2}_{2}]$ is actually equal to
the tree obtained from $T_{2}[u_{2},\ell^{2}_{1},\ell^{2}_{2}]$ by making
$u^{\prime}$ adjacent to $u_{2}$. Therefore,
$T^{\prime}_{2}[u^{\prime},\ell^{2}_{1},\ell^{2}_{2}]$ contains a path with
$4$ vertices and so
$mh(T^{\prime}_{2}[u^{\prime},\ell^{2}_{1},\ell^{2}_{2}])>1$. It follows that
there exist three branches at $\ell^{2}_{2}$ in
$T^{\prime}_{2}[u^{\prime},\ell^{2}_{1}]$ that have monotone hunter number at
least $2$, and so, $mh(T^{\prime}_{2}[u^{\prime},\ell^{2}_{1}])\geq 3$. This
implies that there exist three branches at $\ell^{2}_{1}$ in
$T^{\prime}_{2}[u^{\prime}]$ that have monotone hunter number at least $3$.
Hence, we get that $mh(T^{\prime}_{2}[u^{\prime}])\geq 4$ and
$\lambda(u^{\prime},T^{\prime}_{2}[u^{\prime}])=(4)$.

$\ell_{2}^{1}$$\ell_{1}^{1}$$v$$u_{1}\equiv\ell_{3}^{1}$ Figure 2: An example
of the tree $T_{1}$, described in the examples of Definition 1, such that
$\lambda(u_{1},T_{1}[u_{1}])=(3,2,1)$. Observe that
$mh(T_{1}[\ell_{1}^{1}])=3$ and that $\ell_{1}^{1}$ is $3$-critical since
there are two branches attached to $\ell_{1}^{1}$, both of monotone hunter
number equal to $3$. Similarly, $mh(T_{1}[\ell_{2}^{1}])=2$ and $\ell_{3}^{1}$
is $2$-critical. Finally, the graph $T_{1}[u_{1},\ell_{1}^{1},\ell_{1}^{2}]$
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^{\prime}_{1}$ such that
$\lambda(v,T^{\prime}_{1}[v])=(3,2,1)$. Adding one leaf $u_{2}$ attached to
$v$ would result in a tree $T_{2}$ such that
$\lambda(u_{2},T_{2}[u_{2}])=(3,2,1^{*})$. Adding a leaf $u^{\prime}$ attached
to $u_{2}$ would result in a tree $T^{\prime}_{2}$ with
$\lambda(u^{\prime},T^{\prime}_{2}[u^{\prime}])=(4)$.

######  Claim 3.

There exists no tree $T$ rooted in $v\in V(T)$ such that $v$ has label $(1,0)$
in $T[v]$.

###### Proof.

Towards contradiction, let us assume that there exists a tree $T$ rooted in
$v\in V(T)$ such that $v$ has label $\lambda=(a_{1},a_{2})=(1,0)$ in $T[v]$.
Then, by the definition of the labelling, there exists a vertex $\ell_{1}$ in
$T[v]$ such that $\ell_{1}$ is $1$-critical (because $a_{1}=1$) and moreover
$\ell_{1}\neq v$ because $\lambda\neq(a_{1})$. By the definition of a vertex
being $1$-critical, we get that $\ell_{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\in N(y)$. Since $T[v]$ is connected, there exists
a $(\ell_{1},v)$-path $P=(p_{1}=\ell_{1},\ldots p_{q}=v)$. Thus,
$P^{\prime}=(x,y,p_{1}=\ell_{1},\dots,p_{q}=v)$ is a path with at least $4$
vertices. Hence, $mh(T[v])>1$ which contradicts that $\lambda(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 $\lambda=(a_{1},\ldots,a_{p})$ and any integer $a>a_{1}$, let
$a\odot\lambda=(a^{\prime}_{1}=a,a^{\prime}_{2}=a_{1},\ldots,a^{\prime}_{p^{\prime}-1}=a_{p-1},a^{\prime}_{p^{\prime}}=a_{p})$,
i.e., $\odot$ denotes the concatenation. Moreover, let
$pref(\lambda)=(a_{1},\cdots,a_{p-1})$ (the prefix of $\lambda$) and
$t(\lambda)=a_{p}$ (the tail of $\lambda$).

Algorithm 1 Let $T$ be a tree rooted in a vertex $v$. Let $v_{1},\ldots,v_{d}$
be the $d$ children of $v$ in $T[v]$ and let $\lambda_{1},\ldots,\lambda_{d}$
be their corresponding labels.

1: if $d=0$ then

2: return $(0)$;

3: end if

4: Let $\lambda=()$ and let
$k=\max_{i\in\\{1,\dots,d\\}}\max_{q\in\\{1,\dots,|\lambda_{i}|\\}}\lambda_{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;

7: if $m=0$ then

8: if $n(m)\geq 1$ then

9: $\lambda\leftarrow(1)$;

10: else

11: $\lambda\leftarrow(0)$;

12: end if

13: 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$, $\forall 1\leq i\leq d$, $m\notin pref(\lambda_{i})$ and
$t(\lambda_{i})\neq m^{*}$ and $\lambda=(0)$ then

16: $\lambda\leftarrow(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

19: else if $n(m)\geq 1$ then

20: $\lambda\leftarrow(2)$;

21: end if

22: else if $m>1$ then

23: // Invariant/intuition: at this step, $\lambda=\lambda(v,T_{m-1})$ where
$T_{m-1}$ is the subtree obtained from $T$ by removing the substrees $T[w]$
such that $w\neq v$ and $mh(T[w])\geq m$.

24: //Case 6: at least three children of $v$ have $m$ or $m^{*}$ in their
label

25: if $n(m)\geq 3$ then

26: $\lambda\leftarrow(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: else if $n(m)=2$ and $\exists 1\leq i\leq d$, $m\in pref(\lambda_{i})$ or
$t(\lambda_{i})=m^{*}$ then

29: $\lambda\leftarrow(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, $\forall 1\leq i\leq d$, $m\notin pref(\lambda_{i})$
and $t(\lambda_{i})\neq m^{*}$ then

32: $\lambda\leftarrow(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: else if $n(m)=1$, $\exists 1\leq i\leq d$, $m\in pref(\lambda_{i})$ or
$t(\lambda_{i})=m^{*}$, and $\lambda$ contains $m$ or $m^{*}$ then

35: $\lambda\leftarrow(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: else if $n(m)=1$, $\exists 1\leq i\leq d$, $m\in pref(\lambda_{i})$ or
$t(\lambda_{i})=m^{*}$, and $\lambda$ contains neither $m$ nor $m^{*}$ then

38: $\lambda\leftarrow(m)\odot\lambda$;

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, $\forall 1\leq i\leq d$, $m\notin pref(\lambda_{i})$
and $t(\lambda_{i})\neq m^{*}$ then

41: $\lambda\leftarrow(m)$;

42: end if

43: end if

44: end for

45: return $\lambda$;

######  Lemma 17.

Algorithm 1 takes a tree $T$ rooted at some vertex $v\in 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 $\lambda(v,T[v])=(a^{v}_{1},\ldots,a^{v}_{p^{v}})$. Let
$d_{T[v]}(v)=d$. Let $\lambda^{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, $\lambda(v,T[v])=(0)$. Note that Algorithm 1 returns
$(0)$ in line 2. Hence, $\lambda^{alg}=\lambda(v,T[v])=(0)$.

Thus let us assume that $d>0$. Let $v_{1},\ldots v_{d}$ be the $d$ children of
$v$ in $T[v]$. For any $1\leq i\leq d$, let
$\lambda_{i}=\lambda(v_{i},T[v_{i}])=(a^{i}_{1},\ldots,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}\geq
a^{2}_{1}\geq\dots\geq a^{d}_{1}$ and let
$k=a^{1}_{1}=\max_{i\in\\{1,\dots,d\\}}\max_{q\in\\{1,\dots,|\lambda_{i}|\\}}a^{i}_{q}$.

For each $1\leq i\leq d$, let $T^{i}_{k}=T[v_{i}]$. Also, for $0\leq m\leq k$,
if $m=a^{i}_{j}$ for any $1\leq j\leq p_{i}$, let $T^{i}_{m-1}$ be obtained
from $T^{i}_{m}$ by removing $T[\ell^{i}_{j}]$ where $\ell^{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}]\setminus\bigcup_{a^{i}_{j}\in\lambda_{i},a^{i}_{j}>m}T[a^{i}_{j}]$.
Finally, for any $0\leq m\leq k$, let $T_{m}$ be the subtree of $T[v]$ induced
by $\bigcup_{1\leq i\leq 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\neq
v$ such that $mh(T[w])\geq m+1$. Note that $T_{k}=T[v]=T$ and that
$mh(T_{m})\leq m+1$ for every $m\leq k$. Note also that $T_{0}$ consists of
$v$ and, possibly, some of its children.

Let us prove by induction on $0\leq m\leq k$ that after the $(m+1)$-th
iteration of the loop of the algorithm, the current value of $\lambda$, the
variable of Algorithm 1, denoted by $\lambda^{m}$, is equal to the label
$\lambda(v,T_{m})$, i.e., the label of $v$ in $T_{m}$. If this induction
holds, then, when $m=k$, the algorithm returns
$\lambda^{alg}=\lambda^{k}=\lambda(v,T_{k})=\lambda(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)\geq 1$. Recall that, by the definition of
$T_{0}$, for any child $w$ of $v$ in $T_{0}$, $mh(T_{0}[w])\leq 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 $\lambda(v,T_{0})=(1)$, which corresponds to $\lambda^{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, $\lambda(v,T_{0})=(0)$. Moreover, since,
$n(m)=0$, $\lambda^{0}=(0)$ (line 11 of Algorithm 1).

Let us assume now that $m=1$. It follows from the case $m=0$ that
$\lambda^{0}=\lambda(v,T_{0})$. Before analysing the several subcases for
$m=1$, let us recall that $\lambda(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 $\lambda^{1}=\lambda^{0}=\lambda(v,T_{0})=\lambda(v,T_{1})$ (in this
case, Algorithm 1 does nothing during the $2$-nd iteration of the loop).

  * •

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
$\lambda^{0}=(0)$. Recall that since $\lambda^{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, $\lambda(v,T_{1})=(1^{*})$, which
correspond to $\lambda^{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
$\lambda^{0}=(1)$. Observe that if $\lambda^{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}\in V(T_{1})\setminus 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\in 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, $\lambda(v,T_{1})=(2)$, which corresponds
to $\lambda^{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\in 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,
$\lambda(v,T_{1})=(2)$, which corresponds to $\lambda^{1}$ (line 20 of
Algorithm 1).

  * •

Finally, assume that $n(m)=n(1)\geq 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})\leq 2$). Moreover, by Lemma 16, for any vertex $w\in
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,
$\lambda(v,T_{1})=(2)$, which corresponds to $\lambda^{1}$ (line 20 of
Algorithm 1).

We are now ready to prove the induction step. Let $m\geq 2$ and let us assume
that $\lambda(v,T_{m-1})=\lambda^{m-1}$. We will prove that
$\lambda(v,T_{m})=\lambda^{m}$.

  * •

Case $\boldsymbol{6}$. We are in the case where $n(m)\geq 3$ (line 26 of
Algorithm 1). Since $n(m)\geq 3$, in $T_{m}$, $v$ has at least $3$ children
$v_{j}$, $v_{j^{\prime}}$ and $v_{j^{\prime\prime}}$ such that
$mh(T^{j}_{m})=mh(T^{j^{\prime}}_{m})=mh(T^{j^{\prime\prime}}_{m})=m$ (and
$mh(T^{i}_{m})\leq m$ for every $1\leq i\leq 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\in T_{m}$, there exists at most $1$ branch $B$ at $w$ with
$mh(B)\geq m+1$. Therefore, $T_{m}$ has no $m+1$-critical vertex, and so
$\lambda(v,T_{m})=(m+1)$. To conclude, line 26 of Algorithm 1 precisely
returns $\lambda^{m}=(m+1)$. Hence, $\lambda^{m}=\lambda(v,T_{m})$.

  * •

Case $\boldsymbol{7}$. We are in the case where $n(m)=2$ and there exists
$1\leq i\leq d$ such that $m\in pref(\lambda_{i})$ or $t(\lambda_{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^{\prime}}$ (and $i\in\\{j,j^{\prime}\\}$) such that
$mh(T^{j}_{m})=mh(T^{j^{\prime}}_{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\in T_{m}$, there exists at most $1$ branch $B$ at $w$ with
$mh(B)\geq m+1$. Therefore, $T_{m}$ has no $m+1$-critical vertex, and so
$\lambda(v,T_{m})=(m+1)$. To conclude, line 29 of Algorithm 1 precisely
returns $\lambda^{m}=(m+1)$. Hence, $\lambda^{m}=\lambda(v,T_{m})$.

  * •

Case $\boldsymbol{8}$. We are in the case where $n(m)=2$ and $m\notin
pref(\lambda_{i})$ and $t(\lambda_{i})\neq m^{*}$ for all $1\leq i\leq 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^{\prime}}$ such that $mh(T^{j}_{m})=mh(T^{j^{\prime}}_{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^{\prime}}$ 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 $\lambda(v,T_{m})=(m^{*})$. To conclude, line 32
of Algorithm 1 precisely returns $\lambda^{m}=(m^{*})$. Hence,
$\lambda^{m}=\lambda(v,T_{m})$.

  * •

Case $\boldsymbol{9}$. We are in the case where $n(m)=1$, there exists $1\leq
i\leq d$ such that $m\in pref(\lambda_{i})$, or $m^{*}=t(\lambda_{i})$ (i.e.,
there is an $m$-critical vertex in $T^{i}_{m}$) and $\lambda_{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\in\lambda^{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\in T_{m}$, there exists at most $1$ branch $B$ at
$w$ with $mh(B)\geq m+1$. Therefore, $T_{m}$ has no $(m+1)$-critical vertex,
and so $\lambda(v,T_{m})=(m+1)$. To conclude, line 35 of Algorithm 1 precisely
returns $\lambda^{m}=(m+1)$. Hence, $\lambda^{m}=\lambda(v,T_{m})$.

  * •

Case $\boldsymbol{10}$. We are in the case where $n(m)=1$, there exists $1\leq
i\leq d$ such that $m\in pref(\lambda_{i})$, or $m^{*}=t(\lambda_{i})$ (i.e.,
there is an $m$-critical vertex in $T^{i}_{m}$), and $m\notin\lambda^{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\notin\lambda^{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
$\lambda^{m-1}=\lambda(v,T_{m-1})=(a_{1},\ldots,a_{p})$. Recall that, there
exist vertices $\ell_{1},\ell_{2},\ldots,\ell_{p-1}$ such that $\ell_{h}$ is
$a_{h}$-critical in $T_{m-1}[v,\ell_{1},\cdots,\ell_{h-1}]$ for every $1\leq
h<p$. Since $T_{m-1}[v]=T_{m}[v,y_{i}]$, $\ell_{h}$ is $a_{h}$-critical in
$T_{m}[v,y_{i},\ell_{1},\cdots,\ell_{h-1}]$ for every $1\leq h<p$. Moreover,
for every $1\leq h\leq p$,
$T_{m-1}[v,\ell_{1},\dots,\ell_{h-1}]=T_{m}[v,y_{i},\ell_{1},\dots,\ell_{h-1}]$,
and so
$mh(T_{m}[v,y_{i},\ell_{1},\dots,\ell_{h-1}])=mh(T_{m-1}[v,\ell_{1},\dots,\ell_{h-1}])=a_{h}$.
Therefore, $\lambda(v,T_{m})=(m,a_{1},\dots,a_{p})$. To conclude, line 38 of
Algorithm 1 precisely returns $\lambda^{m}=(m)\odot\lambda^{m-1}$. Hence,
$\lambda^{m}=\lambda(v,T_{m})$.

  * •

Case $\boldsymbol{11}$. Finally, we are in the case where $n(m)=1$ and
$m\notin pref(\lambda_{i})$ and $t(\lambda_{i})\neq m^{*}$ for all $1\leq
i\leq 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 $\lambda(v,T_{m})=(m)$. To conclude, line 41 of Algorithm 1
precisely returns $\lambda^{m}=(m)$. Hence, $\lambda^{m}=\lambda(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.

##  5 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}\cup 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_{V_{r}}(G)$ for every bipartite graph $G=(V_{r}\cup
V_{w},E)$ and which helped to get many results on the Hunters and Rabbit game
[1, 6, 16]. 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_{V_{r}}(G)$ denotes the minimum number of hunters required to win against
a rabbit starting at $V_{r}$ in a bipartite graph $G=(V_{r}\cup V_{w},E)$ and
in a monotone way. It can be checked that, in [16], it is actually shown that,
for any tree $T$, $mh_{V_{r}}(T)\leq\lceil\frac{\log_{2}|V(T)|}{2}\rceil$ (a
monotone strategy with respect to $V_{r}$ is described in [16]). Therefore,
the proof of Corollary 2 actually shows that:

######  Corollary 5.

There exists $\varepsilon>0$ such that, for any $k\in\mathbb{N}$, there exists
a tree $T$ with $mh_{V_{r}}(T)\geq k$ and
$mh(T)\geq(1+\varepsilon)mh_{V_{r}}(T)$.

Therefore, Proposition 4 and Corollary 5 already show that there exist graphs
$G$ for which $mh_{V_{r}}(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_{V_{r}}(T)$ and $h_{V_{r}}(T)$ is arbitrarily large. In particular, this
improves the result of Corollary 2 since $mh_{V_{r}}(G)\leq mh(G)$ and
$h_{V_{r}}(G)=h(G)$ for any graph $G$.

More precisely, this section is devoted to proving:

######  Theorem 7.

For every $i\geq 3$, there exists a tree $T$ such that $mh_{V_{r}}(T)\geq i$
and $h_{V_{r}}(T)=h(T)=2$.

###### Proof.

In Section 5.1, we define a family $(T_{i,2i})_{i\geq 3}$ of trees such that
$h_{V_{r}}(T_{i,2i})=2$ for every $i\geq 3$ (Lemma 24). Then, in Section 5.2,
Lemma 27 proves that $mh_{V_{r}}(T_{i,2i})\geq i$ for every $i\geq 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 $\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a hunter strategy in a bipartite
graph $G=(V_{r}\cup V_{w},E)$ with respect to $V_{r}$. Let $v\in V_{r}$ (resp.
$v\in V_{w})$ and $1\leq i\leq\ell$. If there exists a vertex $u\in N(v)$ and
a vertex $x\in N(u)$ (possibly $x=v$) such that $u\notin\bigcup_{j\leq
i}S_{j}$ and $x\notin\bigcup_{j<i}S_{j}$, then $v\in Z_{2p}$ for every $2p\leq
i$ (resp. $v\in Z_{2p+1}$ for every $2p+1\leq i$).

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

######  Lemma 18.

Let $G=(V_{r}\cup V_{w},E)$ be a bipartite graph with at least two vertices.
Let $\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a monotone hunter strategy in $G$
with respect to $V_{r}$. For any $0\leq p<i\leq\lceil\ell/2\rceil$,
$Z_{2i}\subseteq Z_{2p}$ and $Z_{2i+1}\subseteq 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 $\mathcal{S}=(S_{1},\ldots,S_{\ell})$ be a non-monotone winning hunter
strategy in a bipartite graph $G=(V_{r}\cup V_{w},E)$ with respect to $V_{r}$.
Then, there exist a vertex $v\in V$ and $1\leq i\leq\ell$ such that $v\in
Z_{i-1}\setminus S_{i}$ and $v\in\bigcup_{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}\cup
V_{w},E)$, $mh_{V_{r}\cap V(H)}(H)\leq mh_{V_{r}}(G)$. Moreover, if
$|V(H)|>1$, we get that, if there exists a monotone winning hunter strategy
${\cal S}=(S_{1},\ldots,S_{\ell})$ in $G$ with respect to $V_{r}$, then there
exists a monotone winning hunter strategy ${\cal S}^{\prime}$ in $H$ with
respect to $V_{r}\cap V(H)$ using at most $\max_{1\leq i\leq\ell}|S_{i}\cap
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}\cup V_{w},E)$ and any $k\geq mh_{V_{r}}(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}\cup V_{w},E)$ be a bipartite graph and
$\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a parsimonious monotone winning hunter
strategy with respect to $V_{r}$.

  * •

If there exist $1\leq i<j\leq\ell$ such that $v\in S_{i}\cap S_{j}$, then
$v\in S_{i+2}$.

  * •

If $v\in V_{r}$ (resp., $v\in V_{w}$) and there exists an odd (resp., even)
integer $1\leq i<\ell$ such that $v\notin Z_{i-1}$, then $v\notin S_{j}$ for
every $j\geq i$.

###  5.1 The family of trees $\boldsymbol{(T_{i,q})_{i\geq 3,q\geq 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\geq 3}$ of trees
which exhibits this behaviour.

Let $S_{k,q}$ be the rooted tree obtained from $q\geq 6$ paths of length
$k\geq 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\in V_{r}$.

######  Lemma 23.

For any $k,q\in\mathbb{N}$ such that $k\geq 3$ and $q\geq 6$, it holds that
$h(S_{k,q})=mh_{V_{r}}(S_{k,q})=2$.

###### Proof.

The fact that $h(S_{k,q})>1$ comes from the characterisation of trees with
hunter number one in [8]. W.l.o.g., let us suppose that the centre $c$ of
$S_{k,q}$ is in $V_{r}$. We now prove that $mh_{V_{r}}(S_{k,q})\leq 2$ and the
result then follows from Lemma 5 and Proposition 1.

The strategy $\cal 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},\dots,v_{k})$ of
$S_{k,q}\setminus c$ by iteratively shooting at $v_{1},v_{2},\dots,v_{k}$
(starting by shooting $v_{1}$ at an even round).

Formally, let $P^{1},\dots,P^{q}$ be the $q$ branches of $c$ in $S_{k,q}$, and
let $P^{i}=(v^{i}_{1},\dots,v^{i}_{k})$ for every $1\leq i\leq q$ where
$v^{i}_{1}$ is the neighbour of $c$ in $P^{i}$. Then, the strategy $\cal S$
equals $(\\{c\\},\\{v^{1}_{1}\\},\\{c,v^{1}_{2}\\},\\{v^{1}_{3}\\},$
$\\{c,v^{1}_{4}\\},\dots,\\{v^{1}_{k-1}\\},\\{c,v^{1}_{k}\\},\\{v^{2}_{1}\\},\\{c,v^{2}_{2}\\},\dots,\\{v^{i}_{j-1}\\},\\{c,v^{i}_{j}\\},\dots,\\{c,v^{q}_{k}\\})$
if $k$ is even, and $\cal S$ equals
$(\\{c\\},\\{v^{1}_{1}\\},\\{c,v^{1}_{2}\\},\\{v^{1}_{3}\\},\\{c,v^{1}_{4}\\},\dots,\\{c,v^{1}_{k-1}\\},\\{v^{1}_{k}\\},\\{c\\},\\{v^{2}_{1}\\},\\{c,v^{2}_{2}\\},\dots,\\{v^{i-1}_{k}\\},\\{c\\},\\{v^{i}_{1}\\}$
$,\\{c,v^{i}_{2}\\},\dots,\\{v^{i}_{j-1}\\},\\{c,v^{i}_{j}\\},\dots,\\{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 ${\cal S}_{1}$
and let $\ell_{1}$ be the smallest even integer greater or equal to the length
of ${\cal S}_{1}$ (this length equals to $1+qk$ if $k$ is even and to $q(k+1)$
otherwise).

#### The construction of the tree $\boldsymbol{T_{i,q}}$.

For every $i\geq 2$ and $q\geq 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 $\ell_{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\geq 2$ in the next lemma). Let $T_{i,q}$ be
obtained from $q$ vertex disjoint copies $T_{i}^{1},\dots,T_{i}^{q}$ of
$T_{i-1,q}$ and from a vertex $c_{i}$, the root of $T_{i,q}$. Then, for every
$1\leq j\leq q$, add a path $P_{i}^{j}$ of length $p_{i}^{j}$ (defined below)
between the root $c_{i}^{j}$ of $T_{i}^{j}$ and $c_{i}$ (that is, $c_{i}$ and
$c_{i}^{j}$ are at distance $p^{i}_{j}$ in $T_{i,q}$).

The lengths $p_{i}^{j}$ are defined recursively as follows. Let $p_{i}^{1}=2$
and, for every $1<j\leq q$, let $p_{i}^{j}$ be the minimum even integer
greater or equal to $\ell_{i-1}+\sum_{1\leq k<j}p_{i}^{k}$ (it will be shown
in the next lemma that $\ell_{i}$ equals the smallest even integer greater or
equal to $q\ell_{i-1}+\sum_{1\leq j\leq q}jp_{i}^{j}$).

Finally, let us assume that $c_{i}\in V_{r}$ and note that, since $p_{i}^{j}$
is even, this implies that $c_{i},c_{i}^{1},\dots,c_{i}^{q}$ all belong to
$V_{r}$.

######  Lemma 24.

For any $i\in\mathbb{N}^{*}$ and $q\geq 6$, $h_{V_{r}}(T_{i,q})=2$.

###### Proof.

The fact that $h_{V_{r}}(T_{i,q})\geq 2$ follows from Lemmas 23 and 1 and
since $T_{i,q}$ contains $S_{3,q}$ as a subgraph.

We prove that $h_{V_{r}}(T_{i,q})\leq 2$ by induction on $i$. More precisely,
we prove that there exists a winning hunter strategy
$\mathcal{S}_{i}=(S_{1},\dots,S_{\ell_{i}})$ for $T_{i,q}$, with respect to
$V_{r}$, using $2$ hunters and such that, for any $j\geq 1$, if the root
$c_{i}$ of $T_{i,q}$ is in $Z_{j}$, then $c_{i}\in S_{j+1}$. This holds for
$i=1$ by Lemma 23. Let $i>1$ and let us assume by induction that such a
strategy $\mathcal{S}_{i-1}$ has already been defined for $T_{i-1,q}$.

Recall that, for all $1\leq j\leq 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 $\ell_{i-1}+\sum_{1\leq k<j}p_{i}^{k}$.
Moreover, recall that $c_{i}\in V_{r}$.

Let us define the strategy ${\cal S}_{i}$ as follows. It proceeds in $q$
phases and ensures that, at every round $h$, if $c_{i}\in Z_{h}$, then
$c_{i}\in S_{h+1}$ and that, for every round $h$ arising after the $j^{th}$
phase, $(Z_{h}\setminus c_{i})\cap\bigcup_{k\leq j}(V(T^{k}_{i})\cup
V(P^{k}_{i}))=\emptyset$. This implies that, at the round $\ell_{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, ${\cal S}_{i}$ is a
winning strategy.

Let $1\leq j\leq 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}}\setminus
c_{i})\cap\bigcup_{k\leq j-1}(V(T^{k}_{i})\cup V(P^{k}_{i}))=\emptyset$. The
$j^{th}$ phase proceeds into two sub-phases as follows.

$c_{i-1}^{1}$$c_{i-1}^{2}$$c_{i-1}^{3}$$c_{i-1}^{4}$$c_{i-1}^{5}$$c_{i-1}^{6}$$c_{i}$$p_{i}^{1}=2$$p_{i}^{2}>\ell_{i-1}+p_{i}^{1}$$p_{i}^{3}$$p_{i}^{4}$$p_{i}^{5}$$p_{i}^{6}>\ell_{i-1}+\sum_{k=1}^{5}p_{i}^{k}$$T_{i-1,6}^{1}$$T_{i-1,6}^{2}$$T_{i-1,6}^{3}$$T_{i-1,6}^{4}$$T_{i-1,6}^{5}$$T_{i-1,6}^{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\leq j\leq 6$, we have
that $p_{i}^{j}>\sum_{1\leq k\leq j-1}p_{i}^{k}+\ell_{i-1}$, where
$p_{i}^{1}=2$ and $\ell_{i-1}$ is equal to the number of rounds needed to
clear any copy of the $T_{i-1,6}$ graph.

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}\setminus c_{i}$ that it was occupying at the end of the $(j-1)^{th}$
phase. During the same first sub-phase, the second hunter sequentially shoots
the vertices of $P^{q}_{i},P^{q-1}_{i},\dots,P^{j}_{i}$ in this order and from
the neighbours of $c_{i}$ to the vertices
$c^{q}_{i},c^{q-1}_{i},\dots,c^{j}_{i}$. More precisely, for every $j\leq
k\leq q$, let
$P^{k}_{i}=(v^{k}_{0}=c_{i},v^{k}_{1},\dots,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},\dots,v^{q}_{p^{q}_{i}}=c^{q}_{i},v^{q-1}_{1},v^{q-1}_{2},\dots,v^{q-1}_{p^{q-1}_{i}}=c^{q-1}_{i},v^{q-2}_{1},\dots,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}\cup 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}\cup 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}\cup 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\leq q$,
after the round when the second hunter shoots at $c^{j}_{i}$, the rabbit must
be at distance at least $\ell_{i-1}$ from $c_{i}$ if it was occupying a vertex
of $\bigcup_{j<k\leq q}T^{k}_{i}\cup P^{k}_{i}$ at the end of the $(j-1)^{th}$
phase. Moreover, the rabbit cannot occupy any vertex in $\bigcup_{k\leq