∎

e1e-mail<EMAIL_ADDRESS>e2e-mail<EMAIL_ADDRESS>
11institutetext: Research Center for Neutrino Science, Tohoku University,
Sendai, Miyagi, JAPAN 22institutetext: Research Center for Nuclear Physics,
Osaka University, Osaka, JAPAN 33institutetext: Department of Physics,
Soongsil University, Seoul 06978, KOREA 44institutetext: Department of
Radiology, Dongshin University, Chonnam 58245, KOREA 55institutetext:
Department of Physics, Kyung Hee University, Seoul 02447, KOREA
66institutetext: J-PARC Center, JAEA, Tokai, Ibaraki JAPAN 77institutetext:
Department of Fire Safety, Seoyeong University, Gwangju 61268, KOREA
88institutetext: Gwangju Institute of Science and Technology, Gwangju, 61005,
KOREA 99institutetext: Department of Physics, Sungkyunkwan University, Gyeong
Gi-do, KOREA 1010institutetext: Department of Physics, Chonnam National
University, Gwangju, 61186, KOREA 1111institutetext: University of Michigan,
Ann Arbor, MI, 48109, USA 1212institutetext: School of Liberal Arts, Seoul
National University of Science and Technology, Seoul, 139-743, KOREA
1313institutetext: Department of Physics, Kitasato University, Sagamihara
252-0373, Kanagawa, JAPAN 1414institutetext: Division of Science Education,
Physics major, Chonbuk National University, Jeonju, 54896, KOREA
1515institutetext: Department of Physics, Kyungpook National University, Daegu
41566, KOREA 1616institutetext: High Energy Accelerator Research Organization
(KEK), Tsukuba, Ibaraki, JAPAN 1717institutetext: Department of Physics, Kyoto
University, Kyoto, JAPAN 1818institutetext: Department of Physics and
Astronomy, University of Sussex, Brighton,UK 1919institutetext: University of
Florida, Gainesville, FL, 32611, USA 2020institutetext: Brookhaven National
Laboratory, Upton, NY, 11973-5000, USA

#  Characterization of the correlated background for a sterile neutrino search
using the first dataset of the JSNS2 experiment

Y. Hinoe1, addr4  S. Ajimuraaddr1  M. K. Cheounaddr2  J. H. Choiaddr3  T.
Dodoaddr4  H. Furutaaddr4  J. Gohaddr22  K. Hagaaddr5  M. Haradaaddr5  S.
Hasegawaaddr5  T. Hiraiwaaddr1  W. Hwangaddr22  H. I. Jangaddr9  J. S.
Jangaddr8  H. Jeonaddr19  S. Jeonaddr19  K. K. Jooaddr10  J. R. Jordanaddr6
D. E. Jungaddr19  S. K. Kangaddr11  Y. Kasugaiaddr5  T. Kawasakiaddr7  E. J.
Kimaddr12  J. Y. Kimaddr10  S. B. Kimaddr19  S. Y. Kimaddr22  W. Kimaddr14  H.
Kinoshitaaddr5  T. Konnoaddr7  C. Y. Cheounaddr2  D. H. Leeaddr15  S.
Leeaddr22  I. T. Limaddr10  C. Littleaddr6  E. Marzecaddr6  T. Maruyamae2,
addr15  S. Masudaaddr5  S. Meigoaddr5  S. Monjushiroaddr15  D. H. Moonaddr10
T. Nakanoaddr1  M. Niiyamaaddr16  K. Nishikawaaddr15  M. Nomachiaddr1  M. Y.
Pacaddr3  J. S. Parkaddr15  R. G. Parkaddr10  S. J. M. Peetersaddr17  H.
Rayaddr18  C. Rottaddr19  K. Sakaiaddr5  S. Sakamotoaddr5  T. Shimaaddr1  C.
D. Shinaddr10  J. Spitzaddr6  F. Suekaneaddr4  Y. Sugayaaddr1  K. Suzuyaaddr5
M. Tairaaddr15  R. Ujiieaddr4  Y. Yamaguchiaddr5  M. Yehaddr21  I. S.
Yeoaddr22  I. Yuaddr19

(Received: date / Accepted: date)

###### Abstract

JSNS2 (J-PARC Sterile Neutrino Search at J-PARC Spallation Neutron Source) is
an experiment that is searching for sterile neutrinos via the observation of
$\bar{\nu}_{\mu}\to\bar{\nu}_{e}$ appearance oscillations using muon decay-at-
rest neutrinos. Before dedicate data taking in the first-half of 2021, we
performed a commissioning run for 10 days in June 2020. In this paper, we
present an estimate of correlated background which imitates $\bar{\nu}_{e}$
signal in a sterile neutrino search using the data obtained in this
commissioning run. In addition, in order to demonstrate future prospects of
the JSNS2 experiment, possible pulse shape discrimination improvements towards
reducing cosmic ray induced fast neutron background are described.

††journal: Eur. Phys. J. C

##  1 Introduction

The existence of sterile neutrinos has been an important issue in the field of
neutrino physics for over twenty years. The experimental results from
cite:LSND ; cite:GALLEX ; cite:SAGE ; cite:RA ; cite:MiniBooNE2013 ;
cite:MiniBooNE2018  could be interpreted as indications on the existence of
sterile neutrinos with mass-squared differences of around 1 $\mathrm{eV}^{2}$.

The JSNS2 experiment, proposed in 2013 cite:proposal , is designed to search
for neutrino oscillations caused by such a sterile neutrino at the Material
and Life science experimental Facility (MLF) in J-PARC. The facility provides
an intense and high quality neutrino beam from muon decay-at-rest ($\mu$DAR)
due to a proton beam with 1 MW power in a 25 Hz repetition rate. The 3 GeV
protons come from a rapid cycling synchrotron and the neutrino source is
produced from a mercury target in the MLF. The experiment uses a Gadolinium
(Gd) loaded liquid scintillator (Gd-LS) detector placed at 24 m from the
target.

The JSNS2 experiment aims at a direct test of the LSND observation cite:LSND
with improvements over the experimental technique. Observing
$\bar{\nu}_{\mu}\to\bar{\nu}_{e}$ oscillation using a $\mu$DAR neutrino source
via inverse beta decay (IBD) reaction, $\bar{\nu}_{e}+p\to e^{+}+n$, is the
same experimental principle used by the LSND experiment cite:LSND . On the
other hand, there are several improvements in the JSNS2 experiment. In order
to identify IBD events, a delayed coincidence between the positron signal
(prompt signal: up to 53MeV) and neutron capture signal is used for selection.
Gd is used to identify neutron captures. After absorbing thermal neutrons, Gd
generates gamma-rays with higher energy and shorter capture time (8 MeV, $\sim
30~{}\mu$s) than hydrogen (2.2 MeV, $\sim 200~{}\mu$s). Therefore, backgrounds
accidentally coincidence in the delayed signal region can be reduced by $\sim
6$ times compared to the hydrogen capture used in the LSND experiment, due to
the shorter capture time. In addition, the short pulsed beam enables us to set
a timing window for the IBD prompt signal as 1.5 to 10 $\mu\mathrm{s}$ from
the proton beam collision so that the neutrinos from pion and kaon decay and
fast neutrons generated at the target can be rejected efficiently. However,
the efficiency for the $\mu$DAR neutrinos can be kept at 62% because of muon
lifetime ($2.2~{}\mathrm{\mu s}$). Cosmogenic background is also reduced by a
factor of $10^{-4}$.

There are a number of correlated backgrounds to the IBD signal, characterized
by a time-coincident prompt and delayed signal. The most concerning one is a
cosmic-induced neutron whose prompt signal is made by a recoil proton and a
delayed signal from the neutron capture on Gd after thermalization.
Approxiamtely 99% of this neutron background can be rejected by pulse shape
discrimination (PSD) using the waveform shape difference between the prompt
signal of IBD and neutron events. Detailed discussion about the signal
detection principle and the background rejection technique can be found in
cite:proposal ; cite:TDR

##  2 Commissioning run

The JSNS2 experiment commenced data taking with a single detector in June
2020. The data taking period was from June 5th to 15th, i.e., approximately 10
days. The proton beam power was 600 kW during this period. There was a one-day
beam-off period due to facility maintenance, and thus we obtained beam-off
data at that time. The integrated number of proton-on-target (POT) collected
was $8.9\times 10^{20}$, corresponding to less than 1.0% of the required POT
of the JSNS2 experiment. The expected number of IBD signal events from this
run is estimated to be much less than 1 cite:TDR . Therefore, all of observed
events are likely background.

###  2.1 Experimental setup

The JSNS2 detector is a cylindrical liquid scintillator detector placed at a
distance of 24 m from the mercury target of the MLF. It consists of 17 tonnes
Gd-LS contained in an acrylic vessel, and 33 tonnes unloaded liquid
scintillator (LS) in a layer between the acrylic vessel and an stainless steel
tank. The LS volume is separated into two independent layers by an optical
separator that forms two detector volumes in the one detector. The region
inside of the optical separator, called the “inner detector”, consists of 17
tonnes Gd-LS and 25 cm thick LS layer, 33 tonnes, surrounding the Gd-LS
volume. Scintillation light from the inner detector is observed by 96
photomultiplier tubes (PMTs) with 10-inch diameter. The outer layer, called
the “veto layer”, is used detect cosmic ray induced particles coming into the
detector.A total 24 of 10-inch PMTs are set in the veto layer whose inner
surfaces are fully covered with reflection sheets in order to improve the
collection efficiency of the scintillation light.

###  2.2 Data acquisition system and triggers

PMT signal waveforms from both the inner detector and the veto layer are
digitized and recorded at a 500 MHz sampling rate by 8-bit flash analog-to-
digital converters (FADCs). We utilize a 25 Hz periodic signal from the kicker
magnet which directs proton beam towards the MLF target as a trigger called
the ”kicker trigger” . The width of the acquired waveform in this trigger
scheme is set to 25 $\mu\mathrm{s}$ , which thoroughly covers the prompt
signal timing window of the IBDs events. We mainly used this trigger and data
acquisition to obtain the beam-on data for a background estimation within the
sterile neutrino search.

The other trigger, called the “self trigger”, uses an analog sum of the PMT
signals from the inner detector. The trigger threshold is set to 80 mV and its
efficiency reaches approximately 99% above 7 MeV. The FADCs record 496 ns wide
waveforms in the data taking using the self trigger. We utilized the self
trigger during the beam-off period in order to obtain cosmogenic events and
calibration data using a 252-Californium (252Cf) neutron source. A detailed
description of the detector and the triggers are given in cite:detector ;
cite:daq , respectively.

##  3 Event selection and results

The data set used for the background estimation was obtained using the kicker
trigger. The total number of beam spills was 8092503, equivalent to 3.5 days
of data taking. Since the obtained waveforms, given the 25 $\mu\mathrm{s}$
width, contains multiple events, we therefore used an event definition based
on the number of hit PMTs in order to extract each event. We constructed a hit
time series at each trigger by accumulating hit information along the FADC
window with 60 ns coincidence width over all the PMTs. The coincidence width
was determined by considering a typical PMT pulse shape and a safety factor
from timing calibration. The event discrimination threshold is set to 10 hits
and 50 p.e., which corresponds to an energy well below 1 MeV.

The event vertex position and energy reconstruction is performed
simultaneously based on a maximum likelihood algorithm using the charge
response of each PMT. Both vertex position and energy were calibrated using 8
MeV peak in the energy spectrum, resulting from thermal neutron capture on Gd
(nGd) by deploying a 252Cf source. The reconstruction performance can be found
in cite:PAC31  for the nGd events and for events with up to 60 MeV using
Michel electrons in cite:HJKPS2020 .

The selection criteria and estimated efficiency are given in Table 1 and a
more detailed description is found in cite:TDR . The selection criteria
applied in this analysis are nearly identical to those in cite:TDR

The prompt signal of IBD candidates is selected using a time difference from
the beam collision timing ($\Delta t_{\mathrm{beam-p}}$) and its energy
($E_{\mathrm{p}}$). We applied the following requirements; $1.5\leq\Delta
t_{\mathrm{beam-p}}\leq 10$ $\mu\mathrm{s}$ and $20\leq E_{\mathrm{p}}\leq 60$
MeV, in order to fully cover $\mu$DAR neutrinos from the mercury target. The
timing selection rejects beam induced fast neutrons in the beam on-bunch
timing ($0\leq\Delta t_{\mathrm{beam-p}}\leq 1.5~{}\mathrm{\mu s}$) as well as
neutrino backgrounds from kaon and pion decay whose lifetimes are 12 ns and 26
ns, respectively. Figure 1 demonstrates the energy and timing selection
windows in a two-dimensional distribution of energy and timing. The red box
represents the prompt signal region and the orange box displays the region of
beam-induced fast neutron events.

In order to identify neutron captures on Gd, the 8 MeV peak of the delayed
signal energy ($E_{\mathrm{d}}$) is selected using a requirement of $7\leq
E_{\mathrm{d}}\leq 12$ MeV cite:SRBG . In addition, the conditions on the time
and spatial difference between the prompt and delayed signal, $\Delta
t_{\mathrm{p-d}}\leq 100~{}\mathrm{\mu s}$ and
$\Delta\mathrm{VTX}_{\mathrm{p-d}}\leq 60$ cm, were used for correlated event
selection. The range of digitized waveforms obtained using the kicker trigger
limited the range of $\Delta t_{\mathrm{p-d}}$, and thus the selection was
replaced with $\Delta t_{\mathrm{p-d}}\leq 25~{}\mathrm{\mu s}$.

There are nGd events associated with fast neutrons induced by beam
contributing to the IBD delayed signal as an accidental background cite:BG2014
. This process has a prompt event within the on-bunch timing; therefore, we
applied a requirement on the spatial difference between on-bunch event and
delayed candidates, $\Delta\mathrm{VTX}_{\mathrm{OB-d}}\geq 110$ cm, in order
to reject the nGd events from on-bunch neutrons. The distribution of
$\Delta\mathrm{VTX}_{\mathrm{OB-d}}$ and the efficiency estimation can be
found in cite:SRBG . The on-bunch event tagging condition is set to
$0\leq\Delta t_{\mathrm{beam-OB}}<1.5~{}\mathrm{\mu s}$ and $1\leq
E_{\mathrm{OB}}\leq 200$ MeV.

Note that a nitrogen purging to the Gd-LS/LS was not performed. Thus, the PSD
was unavailable in this commissioning run data. The timing veto, a selection
using a likelihood based on $\Delta t_{\mathrm{beam-p}}$ and $\Delta
t_{\mathrm{p-d}}$ cite:SRBG , was also not applied due to the limited waveform
width.

Table 1: The IBD selection criteria and their efficiencies in the JSNS2 experiment cite:TDR .  Requirement | Efficiency /%
---|---
$1.5\leq\Delta t_{\mathrm{beam-p}}\leq 10$ $\mu\mathrm{s}$ | 62
$20\leq E_{\mathrm{p}}\leq 60$ MeV | 92
$7\leq E_{\mathrm{d}}\leq 12$ MeV | 71
$\Delta t_{\mathrm{p-d}}\leq 100$ $\mu\mathrm{s}$ | 93
$\Delta\mathrm{VTX}_{\mathrm{p-d}}\leq 60$ cm | 96
$\Delta\mathrm{VTX}_{\mathrm{OB-d}}\geq 110$ cm | 98
PSD | 99
Timing veto | 91
Total | 32

The IBD selection results in the distributions of $E_{\mathrm{p}}$ (a),
$E_{\mathrm{d}}$ (b) and $\Delta\mathrm{VTX}_{\mathrm{p-d}}$ (c), $\Delta
t_{\mathrm{p-d}}$ (d) and $\Delta\mathrm{VTX}_{\mathrm{OB-d}}$ (e) as shown in
Fig. 2, respectively. The regions indicated by the red arrows represent the
selected event candidates. As a result, $59\pm 8$ correlated event candidates
remain within the IBD selection region for the sterile neutrino search.

Figure 1: A two-dimensional distribution of energy and timing before event
selection, used to demonstrate the IBD selection region. The selected regions
for the IBD prompt signal (red box), the IBD delayed signal (green box) and
the beam on-bunch event (orange box) are overlaid. Note that the events are
shown around the prompt signal timing region. There are two event clusters
within 0 to 1.5 $\mu\mathrm{s}$ , which reflect the proton beam structure of
the MLF. They are caused by neutrons produced at the mercury target. One can
see that the IBD prompt signal region is well separated from the on-bunch
region. The events in the IBD delayed signal region must also satisfy $\Delta
t_{\mathrm{p-d}}>0$ in the actual delayed coincidence.  Figure 2: The
distributions of the variables used in the IBD selection: (a)
$E_{\mathrm{p}}$, (b) $E_{\mathrm{d}}$, (c)
$\Delta\mathrm{VTX}_{\mathrm{p-d}}$, (d) $\Delta t_{\mathrm{p-d}}$ and (e)
$\Delta\mathrm{VTX}_{\mathrm{OB-d}}$. Each distribution has all of the
selection criteria applied, except for the selection on the variable
displayed. The red arrows show the selection criteria of each variable.

Taking an efficiency difference between the beam-off data obtained by the self
trigger and the beam-on data with 25 $\mu\mathrm{s}$ FADC window into
consideration, the expected number of cosmic-induced fast neutron events in
the IBD selection is $55.9\pm 4.3$. This is consistent with the number of the
correlated events obtained above. The remaining background rates are mainly
produced by cosmic-induced fast neutrons, with a measured rate of $(2.45\pm
0.20)\times 10^{-5}$ /spill. By assuming 99% neutron rejection with the PSD
capability, the cosmic-induced fast neutron event rate will be comparable with
the expected event rate of the signal IBD at the best-fit oscillation
parameter from the LSND experiment. Therefore, it is crucial to construct a
particle identification technique with the PSD capability for fast neutron
rejection.

##  4 Pulse shape discrimination

As described above, we have found a large number of background events caused
by cosmic-induced fast neutrons for the sterile neutrino search. Thus,
diisopropylnaphthalene (DIN, $\mathrm{C}_{16}\mathrm{H}_{20}$) was dissolved
into the Gd-LS in order to enhance the PSD capability. DIN is commercially
available and widely used as a base solvent of organic liquid scintillator.
Several neutrino experiments using a liquid scintillator detector have adopted
it and achieved good PSD capability cite:NEOS ; cite:PROSPECT . Approximately
8% in volume of DIN was dissolved into the Gd-LS at the beginning of the first
physics run from January 2021. A nitrogen purging was performed before data
taking which led to 10% increase in light yield as a result. The test data
obtained using the self trigger in the first run was used to investigate the
PSD capability.

We developed a PSD algorithm based on likelihood discrimination using
probability density functions (PDFs) associated with the waveform. The PDFs
were constructed by accumulating the ratio of a peak count to a count at each
sample of digitized waveforms for each PMT. We defined a log-likelihood for
PSD with a weight of the total charges representing photon statistics as
follows:

$\log\mathcal{L}_{\alpha}=\sum^{96}_{i=0}Q^{\mathrm{total}}_{i}\sum^{248}_{j=40}\log(P^{\alpha}_{i}(Q^{\mathrm{ratio}}_{ij}))\quad(\alpha=\mathrm{sig,bkg}),$
(1)

where $Q^{\mathrm{total}}_{i}$ represents the observed charge on $i$-th PMT,
and $P^{\alpha}_{i}$ is the probability of the charge ratio
$Q^{\mathrm{ratio}}_{ij}$ of the $j$-th sample of the digitized waveform of
the $i$-th PMT. The first 39 samples were used for a baseline calculation and
thus ignored in computing the likelihood value. Two likelihood values
representing signal-like ($\mathcal{L}_{\mathrm{sig}}$) and fast neutron
background-like ($\mathcal{L}_{\mathrm{bkg}}$) are computed, and the log-
likelihood difference of them, defined as a score, is then used for the event
selection.

In parallel, another method for PSD was developed which utilizes a
Convolutional Neural Network (CNN), a deep learning algorithm commonly used in
the computer vision area. The same data in the likelihood method are put in as
a 96-channel image with $1\times 208$ pixels (FADC sampling points). A CNN
structure composed of three blocks of convolution, max-pooling, ReLU, Batch
Normalization and Dropout layers cite:LeNet ; cite:AI-Saffar  are used for the
pattern recognition in the waveform image. Two fully-connected layers composed
by ReLU and Dropout layers are followed after the convolution block for the
signal to background classification. The model is trained to minimize the
binary cross-entropy loss function, with the values closer to 1.0
corresponding to signals and 0.0 to the backgrounds. The kernel size of the
first convolution layer was chosen to be 11 for optimal performance of the
signal to background classification.

In this study, we used the data samples of Michel electron events associated
with cosmic muon and cosmic-induced fast neutron for the signal-like and the
background control sample, respectively, instead of Monte-Carlo simulation.
The selected energy range is identical in terms of the IBD prompt signal
definition (20 - 60 MeV). As a starting point of the PSD study, the event
vertices around the center of the detector ($r<60$ cm and $|z|<60$ cm) were
selected. Technically, we selected data files with odd ID numbers for the PDF
construction and training the CNN model, and even ones for a performance
evaluation.

Figure 3 shows the result of the PSD performance of the likelihood (top) and
the CNN method (bottom), respectively. The likelihood method achieved fast
neutron rejection of ($97.4\pm 0.5$)% in taking the likelihood score $\geq 0$
with a signal efficiency of ($94.2\pm 2.6$)%. The performance of the CNN
method was similar to the result of the likelihood method with a cut on the
CNN score $\geq 0.17$. Therefore, we have obtained close performance to the
experimental requirement (99% rejection), given an impurity of the fast
neutron control sample coming from accidental coincidence caused by cosmic-
induced gamma-ray leading to a signal-like pulse shape. An understanding of
the impurity will improve the fast neutron rejection efficiency in maintaining
the signal efficiency.

The JSNS2 experiment performed data taking with the improvement against the
dominant background for the sterile neutrino search from the physics run
(January to June 2021), and obtained high statistics data equivalent to
$1.45\times 10^{22}$ POT. According to the study on the PSD capability as a
function of DIN concentration cite:DIN , further improvement on the PSD
capability beyond the neutron rejection efficiency of 99% can be anticipated
by an increase in DIN concentration from 8 to 10%, performed in June 2021
cite:detector .

Figure 3:  Top: The likelihood score distributions of the Michel electron
sample (blue) and the fast neutron sample (red). The Michel electron sample
represents the distribution of the neutrino signal. Bottom: The CNN score
distributions of the Michel electron sample (blue) and the fast neutron sample
(red). The label “Central region only” indicates that the event vertices
around the detector center ($r<60$ cm and $|z|<60$ cm) are used.

##  5 Summary

JSNS2 is a sterile neutrino search experiment aiming at a direct test of the
positive result of the LSND experiment using a decay-at-rest neutrino source
at the MLF and a Gd-LS detector.

We performed the commissioning run of ten days in June 2020. As a result of
the IBD selection to the commissioning run data, we observed $59\pm 8$ of
correlated event candidates in the signal region of the sterile neutrino
search. This is consistent with the cosmic-induced fast neutron rate measured
based on the beam-off data.

In order to reduce the cosmic-induced fast neutron background, 8% in volume of
DIN was dissolved into the Gd-LS to improve the PSD capability for the first
physics run since January 2021. We also developed the two independent PSD
methods based on the likelihood using waveform PDFs and the machine learning
with the CNN. Using a control sample of Michel electrons and fast neutron
events in the central region of the detector. we achieved fast neutron
rejection of ($97.4\pm 0.5$)% with a signal efficiency of ($94.2\pm 2.6$)% if
we require $\mathrm{score}\geq 0$. The CNN method shows a similar performance
to the likelihood method with a requirement of the CNN score $\geq 0.17$.
Further improvements on the PSD capability can be expected with an increase in
DIN concentration as well as an understanding of the impurity in the control
samples. The JSNS2 experiment will start data taking with the improvements
from the coming physics run in 2021/2022.

###### Acknowledgements.

We thank the J-PARC staff for their support. We acknowledge the support of the
Ministry of Education, Culture, Sports, Science, and Technology (MEXT) and the
JSPS grants-in-aid: 16H06344, 16H03967 and 20H05624, Japan. This work is also
supported by the National Research Foundation of Korea (NRF):
2016R1A5A1004684, 2017K1A3A7A09015973, 2017K1A3A7A09016426, 2019R1A2C3004955,
2016R1D1A3B02010606, 2017R1A2B4011200, 2018R1D1A1B07050425,
2020K1A3A7A09080133 and 2020K1A3A7A09080114. Our work has also been supported
by a fund from the BK21 of the NRF. The University of Michigan gratefully
acknowledges the support of the Heising-Simons Foundation. This work conducted
at Brookhaven National Laboratory was supported by the U.S. Department of
Energy under Contract DE-AC02- 98CH10886. The work of the University of Sussex
is supported by the Royal Society grant no. IESnR3n170385. We also thank the
Daya Bay Collaboration for providing the Gd-LS, the RENO collaboration for
providing the LS and PMTs, CIEMAT for providing the splitters, Drexel
University for providing the FEE circuits and Tokyo Inst. Tech for providing
FADC boards.

## References

  * (1) C. Athanassopoulos et al. (LSND Collaboration), Phys. Rev. Lett. 77 (1996) 3082.
  * (2) W. Hampel et al. (GALLEX Collaboration), Phys. Lett. B 420 (1998) 114.
  * (3) J. N. Abdurashitov et al. (SAGE Collaboration), Phys. Rev. C 80 (2009) 015807.
  * (4) G. Mention, M. Fechner, T. Lasserre, T. A. Mueller, D. Lhuillier, M. Cribier and A. Letourneau, Phys. Rev. D 83 (2011) 073006.
  * (5) A. A. Aguilar-Arevalo et al. (MiniBooNE Collaboration), Phys. Rev. Lett. 110 (2013) 161801.
  * (6) A. A. Aguilar-Arevalo et al. (MiniBooNE Collaboration), Phys. Rev. Lett. 120 (2018) 141802.
  * (7) M. Harada, et al, arXiv:1310.1437 [physics.ins-det]
  * (8) M. Harada, et al, arXiv:1705.08629 [physics.ins-det]
  * (9) S. Ajimura et al, Nucl. Inst. Meth. A 1014 (2021) 165742
  * (10) J. S. Park, et al, 2020 JINST 15 T09002
  * (11) T. Maruyama, in Presentation of 31st J-PARC PAC (2021).
  * (12) H. Jeon, in Presentation of 2020 KPS Fall Meeting (2020).
  * (13) M. Harada, et al, arXiv:1502.02255 [physics.ins-det]
  * (14) S. Ajimura et al, PTEP 2015 6, 063C01 (2015).
  * (15) NEOS Collaboration, B. R. Kim et al., J. Radioanal. Nucl. Chem. 310 (2016) 1, 311-316
  * (16) J. Ashenfelter, et al., JINST 14 (2019) no.03, P03026
  * (17) Y. Lecun, et al, in Proceedings of the IEEE, pages 2278–2324, 1998.
  * (18) A. A. Saffar, et al, 2017 International Conference on Radar, Antenna, Microwave, Electronics, and Telecommunications (ICRAMET), 2017, pp. 26-31.
  * (19) B. R. Kim et al., Phys. Scr. 90 (2015) 055302 (8pp)


j-1}(V(T^{k}_{i})\cup V(P^{k}_{i}))$ since the first hunter is always shooting
$c_{i}$ during the odd rounds. Finally, the rabbit cannot occupy a vertex in
$P^{j}_{i}$ since the second hunter has just shot sequentially the vertices
$v^{j}_{1},v^{j}_{2},\dots,v^{j}_{p^{j}_{i}}=c^{j}_{i}$.

Then, the second sub-phase of phase $j$ starts, during which both hunters
execute the strategy ${\cal S}_{i-1}$ in the subtree $T^{j}_{i}$ (the shot of
$c^{j}_{i}$ by the second hunter during the first sub-phase, i.e., the last
round of the first sub-phase, may be used as the first round of ${\cal
S}_{i-1}$). By the induction hypothesis, the strategy ${\cal S}_{i-1}$ ensures
that the rabbit cannot reach the root $c^{j}_{i}$ of $T^{j}_{i}$ without being
shot immediately (if $c^{j}_{i}$ is in $Z_{h}$ for some round $h$, then
$c^{j}_{i}\in S_{h+1}$). Thus, if the rabbit was occupying a vertex of
$T^{j}_{i}$ at the beginning of the second sub-phase, then the rabbit cannot
leave this subtree and it is eventually shot. Otherwise, because ${\cal
S}_{i-1}$ has length at most $\ell_{i-1}$, the rabbit cannot reach $c_{i}$
before the last shots of the hunters in $T^{j}_{i}$. Let $i^{j}_{0}$ be the
last round of the phase. Note that $i^{j}_{0}$ is even since $p^{h}_{i}$ and
$\ell_{h}$ are even for all $1\leq h\leq q$, and $i^{j-1}_{0}$ is even by
induction. Then, the $j^{th}$ phase ends after the (even) round $i^{j}_{0}$
and with the desired property: the rabbit can only occupy a vertex in
$c_{i}\cup\bigcup_{j<k\leq q}(V(T^{k}_{i})\cup V(P^{k}_{i}))$, i.e.,
$(Z_{i^{j}_{0}}\setminus c_{i})\cap\bigcup_{k\leq j}(V(T^{k}_{i})\cup
V(P^{k}_{i}))=\emptyset$.

To conclude, note that ${\cal S}_{i}$ is winning in at most
$q\ell_{i-1}+\sum_{1\leq j\leq q}jp_{i}^{j}$ rounds since each phase $j$
proceeds in $\ell_{i-1}+\sum_{j\leq k\leq q}p^{k}_{i}$ rounds. ∎

######  Theorem 8.

For any tree $T$, there exists a subdivision $T^{\prime}$ of $T$ such that
$h(T^{\prime})\leq 2$.

###### Proof.

Let $q$ be the maximum degree of $T$. Let $r$ be any vertex of $T$, and let
$i$ be the eccentricity of $r$ (i.e., the largest distance between $r$ and
some vertex of $T$). Then, there exists a subdivision $T^{\prime}$ of $T$,
that is a subgraph of $T_{i,\max\\{6,q\\}}$ (each vertex of $T$ being “mapped”
to a vertex of degree at least $3$ of $T_{i,\max\\{6,q\\}}$ and $r$ being
“mapped” to the root of $T_{i,\max\\{6,q\\}}$). By Lemmas 1, 5 and 24,
$h(T^{\prime})\leq 2$. ∎

######  Corollary 6.

For every $\ell\geq 0$, there exists a tree $T$ and a subdivision $T^{\prime}$
of $T$ such that $h(T)-h(T^{\prime})\geq\ell$.

###  5.2 Non monotonicity of the red variant in trees

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

######  Lemma 25.

Let $G=(V_{r}\cup V_{w},E)$ be any bipartite 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$ with respect to $V_{r}$. Let $1\leq
i\leq\ell$ and $x,y\in V(H)$ such that $x\in\bigcup_{j<i}S_{j}$ and $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 if $x=y$, then $\mathcal{S}$ is non-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$ (it exists
since $H$ is connected). Let us assume that $S_{i}\subseteq V_{r}$ and so $i$
is odd (the case when $S_{i}\subseteq V_{w}$ and $i$ is even is similar).
Since $y\in Z_{i-1}$ and $S_{i}\subseteq Z_{i-1}$ (since ${\cal S}$ is
parsimonious), $y\in V_{r}$. Let $a$ be the neighbour of $x$ in $P$.

Towards a contradiction, let us assume that $a\neq y$. By the 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$. If $b\neq y$, then by the minimality of the distance between $x$ and $y$,
$b\notin Z_{i-1}$ and $b\notin\bigcup_{j<i}S_{j}$. Therefore, by Proposition
6, if $a\in V_{r}$, then $a\in Z_{i}$ and if $b\in V_{r}$ then $b\in Z_{i}$.
In both cases, there is a contradiction with the fact that $P$ minimises the
distance between $x$ and $y$.

Therefore, we may assume that $b=y$. This implies that $x\in V_{r}$. Note also
that $y\notin S_{j}$ for all $j\leq i$. Indeed, assuming otherwise would
contradict the fact that $\mathcal{S}$ is monotone, since $y\notin S_{i}$ and
$y\in Z_{i-1}$. Thus, by Proposition 6, and since $a,y\notin\bigcup_{j\leq
i-1}S_{j}$, we have that $x\in Z_{i-1}$. This contradicts the monotonicity of
${\cal S}$ since $x\notin S_{i}$ and $x\in\bigcup_{j<i}S_{j}$. ∎

Before we prove the next lemma, we introduce an extra definition. Let
$G=(V,E)$ be any graph and ${\cal S}=(S_{1},\dots,S_{\ell})$ be any winning
hunter strategy in $G$ with respect to $X\subseteq V$. We say that $W\subseteq
V$ is definitively cleaned at the round $i$ if $W\cap Z_{j}({\cal
S})=\emptyset$ and $W\cap S_{j+1}=\emptyset$ for every $i\leq j\leq\ell$.

Informally, the following lemma says that if the degree of the root $r$ of a
tree $T$ is large enough, compared to the number of hunters, then, when a
first branch of $r$ is definitively cleaned according to any monotone hunter
strategy, there must be some other branches of $r$ whose vertices have never
been shot.

######  Lemma 26.

Let $T=(V_{r}\cup V_{w},E)$ be a tree rooted in some vertex $c\in V_{r}$ with
neighbours $N(c)=\\{v_{1},\dots,v_{d}\\}$, $d\geq 2k$. For every $1\leq i\leq
d$, let $B_{i}$ be the branch at $c$ containing $v_{i}$ and assume that
$|V(B_{i})|\geq 2$. Let $\mathcal{S}=(S_{1}\dots,S_{\ell})$ be any
parsimonious monotone winning hunter strategy in $T$ with respect to $V_{r}$
using at most $k-1$ hunters. Let $1\leq j\leq\ell$ be the smallest index such
that there exists an $1\leq\alpha\leq d$ such that $V(B_{\alpha})$ is
definitively cleaned at the round $j$. Then, there exist
$1\leq\beta<\gamma\leq d$, $\alpha\notin\\{\beta,\gamma\\}$, such that
$(\bigcup_{1\leq i\leq j}S_{i})\cap V(B_{\beta})=\emptyset$ and
$(\bigcup_{1\leq i\leq j}S_{i})\cap V(B_{\gamma})=\emptyset$.

###### Proof.

Let $j$ and $\alpha$ be defined as in the statement and, w.l.o.g., let us
assume that $\alpha=1$. That is, the branch $B_{1}$ is definitively cleaned at
round $j$, and no other branch has been definitively cleaned before round $j$.

######  Claim 4.

For any vertex $v\in V(T)$ such that there exist a least $3$ branches at $v$
with at least two vertices, let $q$ be the minimum index such that such a
branch $B$ is definitively cleaned at round $q$. Then, $S_{q}\cap
V(B)\neq\emptyset$.

Proof of Claim.. By the minimality of $q$, either $Z_{q-1}\cap
V(B)\neq\emptyset$ or $S_{q}\cap V(B)\neq\emptyset$. If $S_{q}\cap
V(B)\neq\emptyset$, then the statement holds. Thus, let us assume that
$S_{q}\cap V(B)=\emptyset$. Then $Z_{q-1}\cap V(B)\neq\emptyset$, as otherwise
$B$ would have been definitively cleaned at round prior to $q$. Let $x\in
Z_{q-1}\cap V(B)$. Since $x\notin S_{q}$, $N_{B}(x)\subseteq Z_{q}$. Since $B$
is connected and contains at least two vertices, we have that
$N_{B}(x)\neq\emptyset$. Thus $Z_{q}\cap V(B)\neq\emptyset$, which contradicts
that $B$ is definitively cleaned at round $q$. $\diamond$

It follows by Claim 4 that $V(B_{1})\cap S_{j}\neq\emptyset$. Thus, since
$|S_{j}|\leq k-1$, there are at most $k-2$ branches at $c$, other than
$B_{1}$, which can be shot during the round $j$. W.l.o.g., let us assume that
$B_{2},\dots,B_{k-1}$ are the branches at $c$ that are also shot during round
$j$. That is, $S_{j}\subseteq\\{c\\}\cup\bigcup_{1\leq h<k}V(B_{h})$.

For purpose of contradiction, let us assume that there exists at most one
branch, w.l.o.g., say $B_{k}$, such that $\bigcup_{1\leq i\leq j}S_{i}\cap
V(B_{k})=\emptyset$. Hence, we assume that for every $k<h\leq d$, there exists
$j_{h}<j$ and $x_{h}\in V(B_{h})\cap S_{j_{h}}$.

For any $k<h\leq d$, let us denote by $j_{h}^{*}$ the minimum index such that
$B_{h}$ is definitively cleaned at round $j_{h}^{*}$. By Claim 4, for any
$k<h\leq d$, $S_{j_{h}^{*}}\cap V(B_{h})\neq\emptyset$. Thus, since
$V(B_{h})\cap S_{j}=\emptyset$ for every $k<h\leq d$, we have that
$j_{h}^{*}\neq j$ for every $k<h\leq d$. In particular, it follows by the
minimality of $j$ that $j_{h}^{*}>j$.

Let us prove that, for some $k<h\leq d$, there exists a vertex $y_{h}\in
Z_{j-1}\cap V(B_{h})$. Towards a contradiction, let us assume that for every
$k<h\leq d$, we have $Z_{j-1}\cap V(B_{h})=\emptyset$. Recall that
$S_{j_{h}^{*}}\cap V(B_{h})\neq\emptyset$, and let $z\in S_{j_{h}^{*}}\cap
V(B_{h})$ (for some $k<h\leq d$). Since ${\cal S}$ is parsimonious, $z\in
Z_{j_{h}^{*}-1}$. Thus, there exists a rabbit trajectory
$(r_{0},\dots,r_{j_{h}^{*}-1}=z)$ such that $r_{q}\notin S_{q+1}$ for every
$0\leq q<j_{h}^{*}-1$. Moreover, $r_{j-1}\notin V(B_{h})$, since $Z_{j-1}\cap
V(B_{h})=\emptyset$. Since a rabbit trajectory is a walk, and any walk between
a vertex from $V\setminus V(B_{h})$ to a vertex of $V(B_{h})$ contains $c$,
there exists $j-1\leq m<j_{h}^{*}-1$ such that $r_{m}=c$. Since $r_{m}\notin
S_{m+1}$, it follows that $v_{1}\in Z_{m+1}$, where $v_{1}$ is the neighbour
of $c$ in $B_{1}$. This contradicts that $B_{1}$ is definitively cleaned at
round $j$. Hence, there exists some vertex $y_{h}\in Z_{j-1}\cap V(B_{h})$.

Finally, for every $k<h\leq d$, let us choose the vertices $x_{h}$ and
$y_{h}$, such that $x_{h}\in V(B_{h})\cap\bigcup_{1\leq i<j}S_{i}$ and
$y_{h}\in Z_{j-1}\cap V(B_{h})$ and the distance between $x_{h}$ and $y_{h}$
is minimised. Note that $y_{h}\notin\bigcup_{1\leq i<j}S_{i}$, since,
otherwise, $\mathcal{S}$ would not be monotone as $y_{h}\in Z_{j-1}\setminus
S_{j}$. Since $S_{j}\cap V(B_{h})=\emptyset$ and by Lemma 25, we obtain that
$x_{h}y_{h}\in E(B_{h})$. Thus, $x_{h}\in Z_{j}$ for every $k<h\leq d$. Since
$\mathcal{S}$ is a monotone strategy, $x_{h}\in S_{j_{h}}\cap Z_{j}$ (with
$j_{h}<j$), that $x_{h}\in S_{j+1}$ for every $k<h\leq d$. However, $d\geq 2k$
and so $|S_{j+1}|\geq k$, a contradiction. ∎

$\gamma_{2i-s}$$\gamma_{2i-1}$$\gamma_{2i}$$\dots$$\dots$$\dots$$B_{1}^{2i-s}$$B_{2}^{2i-s}$$B_{3}^{2i-s}$$B_{2}^{2i-1}$$B_{2}^{2i}$$B_{1}^{2i-1}$$B_{3}^{2i-1}$$B_{1}^{2i}$$B_{3}^{2i}$
Figure 4: A representation of the tree $T_{2i,d}$ illustrating the notation
used throughout the proof of Lemma 27. Wiggly edges are used to represent
paths whose internal vertices have degree $2$. The branch $B_{1}^{2i}$ is the
first branch of $T_{2i,d}$ at $\gamma_{2i}$ that is definitively cleaned, and
this happens during the round $j_{2i}$. No vertex of the branches $B_{2}^{2i}$
and $B_{3}^{2i}$ has been shot until the round $j_{2i}$. Among the branches
$B_{2}^{2i}$ and $B_{3}^{2i}$, the first branch that is definitively cleaned
is $B_{2}^{2i}$, and this happens at the round $j^{\prime}_{2i}>j_{2i}$. The
colour grey is used on the small triangles to denote that we do not know the
state of the corresponding branches at the same level as $B_{1}^{2i}$ that are
different from $B_{2}^{2i}$ and $B_{3}^{2i}$. Observe that $B_{2}^{2i}$
contains a copy of $T_{2i-1,d}$, rooted at $\gamma_{2i-1}$. Since $B_{2}^{2i}$
is definitively cleaned at round $j^{\prime}_{2i}$, we can iterate the same
arguments, and define $B_{1}^{2i-1}$ to be the first branch of $T_{2i-1},d$ at
$\gamma_{2i-1}$ that is definitively cleaned, and this happens during the
round $j_{2i}<j_{2i-1}<j_{2i}^{\prime}$, and so on, until we have reached the
leaves of $B_{2}^{2i}$.

Finally, we will need an extra definition: For any tree $T=(V_{r}\cup
V_{w},E)$, and any vertex $v\in V(T)$, let $B$ be any branch at $v$ such that
$|V(B)|>1$. For any strategy ${\cal S}=(S_{1},\dots,S_{\ell})$ in $T$ with
respect to $V_{r}$, let $m$ be the minimum integer such that $S_{m}\cap
V(B)\neq\emptyset$ and let $u\in S_{m}\cap V(B)$ (by Lemma 3, such an integer
$m$ exists because $|V(B)|>1$ and $B$ is connected, which implies that
$V_{r}\cap V(B)\neq\emptyset$). Let the restriction ${\cal S}_{B}$ of ${\cal
S}$ be the hunter strategy, such that for every $1\leq i\leq\ell$,

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

Recall that, $h({\cal S}_{B})\leq\max_{1\leq i\leq\ell}S_{i}\cap V(B)$ by
Lemma 20.

######  Lemma 27.

For any $i\in\mathbb{N}^{*}$, $i\geq 3$ and $d\geq 2i$, we have that
$mh_{V_{r}}(T_{2i,d})\geq i$.

###### Proof.

Let $\gamma_{2i}$ denote the root of $T_{2i,d}$. For purpose of contradiction,
let us assume that $mh_{V_{r}}(T_{2i,d})<i$. By Lemma 21, there exists a
parsimonious monotone winning hunter strategy with respect to $V_{r}$ using at
most $i-1$ hunters; let that strategy be ${\cal
S}_{2i}=(S^{2i}_{1},\dots,S^{2i}_{\ell})$.

Let $1\leq j_{2i}\leq\ell$ be the smallest index such that some branch at
$\gamma_{2i}$, w.l.o.g., $B^{2i}_{1}$, is definitively cleaned at round
$j_{2i}$. By Lemma 26, there exist two branches at $\gamma_{2i}$, w.l.o.g.,
$B^{2i}_{2}$ and $B^{2i}_{3}$, such that $(\bigcup_{1\leq q\leq
j_{2i}}S_{q})\cap V(B^{2i}_{2})=\emptyset$ and $(\bigcup_{1\leq q\leq
j_{2i}}S_{q})\cap V(B^{2i}_{3})=\emptyset$.

Let $1\leq j^{\prime}_{2i}\leq\ell$ be the smallest index such that at least
one branch $B^{2i}_{2}$ or $B^{2i}_{3}$ is definitively cleaned.

Note that $B^{2i}_{2}$ (resp., $B^{2i}_{3}$) is connected and has at least two
vertices with at least one in $V_{r}$. Therefore, by Lemma 3, at least one
vertex of $B^{2i}_{2}$ (resp., $B^{2i}_{3}$) must be shot before the branch is
definitively cleaned . Hence, $j_{2i}<j^{\prime}_{2i}$. W.l.o.g., assume that
$B^{2i}_{2}$ is definitively cleaned at round $j^{\prime}_{2i}$ (possibly,
$B^{2i}_{3}$ may also be definitively cleaned at round $j^{\prime}_{2i}$).

We now prove by induction on $0\leq h<2i$ , that there exist $1\leq
j_{2i}<j_{2i-1}<\dots<j_{2i-h}<j^{\prime}_{2i-h}\leq
j^{\prime}_{2i-h+1}\leq\dots\leq j^{\prime}_{2i-1}\leq
j^{\prime}_{2i}\leq\ell$ and
$\\{B^{2i-s}_{1},B^{2i-s}_{2},B^{2i-s}_{3}\\}_{0\leq s\leq h}$ such that, for
every $0\leq s\leq h$:

  1. 1.

$(\bigcup_{1\leq q\leq j_{2i-s}}S_{q})\cap V(B^{2i-s}_{2})=\emptyset$ and
$(\bigcup_{1\leq q\leq j_{2i-s}}S_{q})\cap V(B^{2i-s}_{3})=\emptyset$;

  2. 2.

$B^{2i-s}_{1},B^{2i-s}_{2}$ and $B^{2i-s}_{3}$ are vertex disjoint branches at
the root $\gamma_{2i-s}$ of the copy of $T_{2i-s,d}$ contained in
$B^{2i-(s-1)}_{2}$ (with $B^{2i+1}_{2}=T_{2i,d}$ for $s=0$), each containing a
copy of $T_{2i-(s+1),d}$ (with $T_{0,d}=\emptyset$ for $s=h=2i-1$);

  3. 3.

$B^{2i-s}_{1}$ is definitively cleaned at round $j_{2i-s}$ (not before, i.e.,
for every $x<j_{2i-s}$, $B^{2i-s}_{1}$ is not definitively cleaned at round
$x$), $B^{2i-s}_{2}$ is definitively cleaned at round $j^{\prime}_{2i-s}$ (not
before), $B^{2i-s}_{3}$ is definitively cleaned at some round $x\geq
j^{\prime}_{2i-s}$ (not before).

See Figure 4 for an illustration of the above notation.

We have already proven that the induction hypothesis holds for $h=0$. Let us
assume that it holds for some $0\leq h<2i-1$ and let us show it holds for
$h+1$. Let $F$ be the copy of $T_{2i-(h+1),d}$ (rooted at $\gamma_{2i-(h+1)}$)
contained in $B^{2i-h}_{2}$ and let $1\leq j_{2i-(h+1)}\leq j^{\prime}_{2i-h}$
be the smallest integer such that some branch $B$ of $F$ at
$\gamma_{2i-(h+1)}$ is definitively cleaned. Note that each branch of $F$ at
$\gamma_{2i-(h+1)}$ is connected and has at least two vertices with at least
one in $V_{r}$. Therefore, by Lemma 3, at least one vertex of $B$ must be shot
before it is definitively cleaned. Hence, $j_{2i-h}<j_{2i-(h+1)}$. Let
$B=B^{2i-(h+1)}_{1}$. Let $\mathcal{S}_{2i-(h+1)}$ denote the restriction of
$\mathcal{S}_{2i-h}$ on $F$. By Lemma 26 considering the strategy
$\mathcal{S}_{2i-(h+1)}$ on $F$, there exist at least two branches at
$\gamma_{2i-(h+1)}$, let us denote them by $B^{2i-(h+1)}_{2}$ and
$B^{2i-(h+1)}_{3}$, such that $(\bigcup_{1\leq q\leq j_{2i-(h+1)}}S_{q})\cap
V(B^{2i-(h+1)}_{2})=\emptyset$ and $(\bigcup_{1\leq q\leq
j_{2i-(h+1)}}S_{q})\cap V(B^{2i-(h+1)}_{3})=\emptyset$. Also, it follows by
Lemma 3 that $j_{2i-(h+1)}<j^{\prime}_{2i-(h+1)}$. Finally,
$B^{2i-(h+1)}_{1}$, $B^{2i-(h+1)}_{2}$ and $B^{2i-(h+1)}_{3}$ are all
contained in $B_{2i-h}$ and, thus,
$max(j_{2i-(h+1)},j^{\prime}_{2i-(h+1)})=j^{\prime}_{2i-(h+1)}\leq
j^{\prime}_{2i-h}$. This finishes the proof of the induction step.

For every $1\leq s\leq 2i$, let $H_{s}$ be the subgraph induced by $B^{s}_{1}$
and $B^{s}_{3}$ and $\gamma_{s}$ (so $H_{s}$ is connected and the subgraphs
$H_{s}$ and $H_{s^{\prime}}$ are vertex disjoint for any $s\neq s^{\prime}$).
Since $B^{s}_{1}$ has been definitively cleaned at round $j_{s}$, has at least
two vertices and by Lemma 3, there exists a vertex $x^{\prime}_{s}\in
V(B^{s}_{1})\cap\bigcup_{1\leq q\leq j_{2i}}S_{q}$.

Note that $B^{s}_{3}$ is connected and has at least two vertices with at least
one in $V_{r}$. Therefore, by Lemma 3, at least one vertex of $B^{s}_{3}$ must
be shot before the branch is definitively cleaned. Thus, since $B^{s}_{3}$ is
definitely cleaned at round $z_{s}\geq j^{\prime}_{s}$, but not definitely
cleaned at a previous round, $S_{z_{s}}\cap V(B^{s}_{3})\neq\emptyset$.
Moreover, since $\mathcal{S}_{2i}$ is parsimonious, any vertex $v\in
S_{z_{s}}\cap V(B^{s}_{3})$ is such that $v\in Z_{z_{s}-1}$. It follows that
$(N(v)\cap Z_{z_{s}-2})\setminus S_{z_{s}-1}\neq\emptyset$. Let
$w_{s}\in(N(v)\cap Z_{z_{s}-2})\setminus S_{z_{s}-1}$ and note that $w_{s}\in
N[V(B^{s}_{3})]=V(B^{s}_{3})\cup\\{\gamma_{s}\\}$. Since $\mathcal{S}_{2i}$ is
monotone, we get that $w_{s}\notin S_{j}$ for every $j<z_{s}$ and that
$N(w_{s})\not\subseteq S_{j}$ for every $j<z_{s}$, i.e. $w_{s}$ has not been
shot before round $z_{s}$. Note also that if $w_{s}=\gamma_{s}$ , then the
neighbour of $\gamma_{s}$ in $B_{1}^{s}$ is in $Z_{z_{s}-1}$, a contradiction
since $z_{s}>j_{1}$ and $B_{1}^{s}$ is definitively cleaned at round
$j_{s}\leq j_{1}$. Hence, $w_{s}\neq\gamma_{s}$ and so $w_{s}\in
V(B^{s}_{3})$.

Similarly, there exists a vertex $w^{\prime}_{s}\in N(w_{s})\cap
Z_{z_{s}-3}\setminus S_{z_{s}-2}$ such that $w^{\prime}_{s}$ has not been
cleaned before round $z_{s}-1$. Hence, we have two adjacent vertices $w_{s}$
and $w^{\prime}_{s}$ in $N[B^{s}_{3}]$ that have never been shot before the
round $z_{s}-1$. Thus, since $\\{w_{s},w^{\prime}_{s}\\}\cap
V_{r}\neq\emptyset$, there exists a rabbit trajectory
$(\dots,w_{s},w^{\prime}_{s},w_{s},w^{\prime}_{s},\dots)$ consisting in
oscillating between $w_{s}$ and $w^{\prime}_{s}$ which implies that
$\\{w_{s},w^{\prime}_{s}\\}\cap Z_{j}\neq\emptyset$ for all $j<z_{s}$. In
particular, since $j_{1}-1<z_{s}$, there exists a vertex $y^{\prime}_{s}\in
N[B^{s}_{3}]\cap Z_{j_{1}-1}$.

For every $1\leq s\leq 2i$, let $x_{s}$ and $y_{s}$ be two vertices in
$V(H_{s})$ such that $x_{s}\in V(H_{s})\cap\bigcup_{1\leq q\leq j_{1}}S_{q}$,
$y_{s}\in V(H_{s})\cap Z_{j_{1}-1}$ and the distance between $x_{s}$ and
$y_{s}$ is minimised. Let $\mathcal{P}=\\{s\mid 1\leq s\leq 2i,y_{s}\in
S_{j_{1}}\cup S_{j_{1}+1}$ or $x_{s}\in S_{j_{1}}\cup S_{j_{1}+1}\\}$, i.e.
$\cal P$ is the set of indices $s$ such that at least one of $y_{s}$ or
$x_{s}$ is shot during the round $j_{1}$ or $j_{1}+1$. Since ${\cal S}_{2i}$
uses at most $i-1$ hunters, we have that $|\mathcal{P}|\leq 2(i-1)$. Thus, let
$1\leq s^{*}\leq 2i$ such that $s^{*}\notin{\cal P}$, i.e.,
$x_{s^{*}},y_{s^{*}}\notin S_{j_{1}}\cup S_{j_{1}+1}$. It follows from Lemma
25 that $x_{s^{*}}y_{s^{*}}\in E(T_{2i,d})$. Since $y_{s^{*}}\in
Z_{j_{2i}-1}\setminus S_{j_{1}}$, we have that that $x_{s^{*}}\in Z_{j_{1}}$.
However, $x_{s^{*}}\in\bigcup_{1\leq q\leq j_{1}}S_{q}\setminus S_{j_{1}+1}$
and so, $x_{s^{*}}$ is recontaminated, contradicting the monotonicity of
${\cal S}_{2i}$. ∎

##  6 Kernelization by vertex cover

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

######  Definition 2 (Equivalent Instances).

Let $\Pi_{1}$ and $\Pi_{2}$ be two parameterised problems. Two instances,
$(I,t)\in\Pi_{1}$ and $(I^{\prime},t^{\prime})\in\Pi_{2}$, are equivalent when
$(I,t)$ is a Yes-instance if and only if $(I^{\prime},t^{\prime})$ is a Yes-
instance.

A parameterised (decision) problem $\Pi_{p}$ admits a kernel of size $f(t)$,
for some function $f$ that depends only on $t$, if the following is true:
there exists an algorithm (called a kernelization algorithm) that, given as
input an instance $(I,t)$ of $\Pi_{p}$, runs in $(|I|+t)^{\mathcal{O}(1)}$
time and outputs an equivalent instance $(I^{\prime},t^{\prime})$ of $\Pi_{p}$
such that $|I^{\prime}|\leq f(t)$ and $t^{\prime}\leq t$. If the function $f$
is polynomial, then the problem is said to admit a polynomial kernel. It is
well-known that a decidable parameterised problem is $\mathsf{FPT}$ if and
only if it admits a kernel [12].

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

First, we have the following observation.

######  Proposition 7.

For any connected graph $G$, $h(G)\leq mh(G)\leq vc(G)$.

###### Proof.

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

Let $U$ be a vertex cover of size $t\geq vc(G)$ of $G$ and $I$ be the
independent set $V(G)\setminus U$. For each subset $S\subseteq U$, we define
the following equivalence class: $\mathcal{C}_{S}=\\{v\mid v\in I\ \text{and}\
N(v)=S\\}$. Next, we have the following crucial lemma.

######  Lemma 28.

Let $G=(V,E)$ be a connected graph, $U\subseteq V$ be a vertex cover of $G$,
$k\geq 1$ and let $S\subseteq U$ be such that $|\mathcal{C}_{S}|>k+1$. Let
$\mathcal{C}_{S}=\\{v_{1},\dots,v_{q}\\}$. Then, $h(G)\leq k$ (resp.,
$mh(G)\leq k$) if and only if $h(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])\leq
k$ (resp., $mh(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])\leq k$).

###### Proof.

By Lemma 1, $h(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])\leq h(G)$. Similarly,
due to Lemma 8, $mh(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])\leq mh(G)$. So, it
only remains to prove that, if $h(G)>k$ (resp., $mh(G)>k$), then
$h(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])>k$ (resp.,
$mh(G[V\setminus\\{v_{k+2},\dots,v_{q}\\}])>k$). Let
$H=G[V\setminus\\{v_{k+2},\dots,v_{q}\\}]$ and let
$X=\\{v_{1},\dots,v_{k+1}\\}$ (i.e., $X=V(H)\cap{\cal C}_{S}$).

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

(1) $\boldsymbol{h(G)>k\implies h(H)>k}$: Let
$\mathcal{S}=(S_{1},S_{2},\dots,S_{\ell})$ be any hunter strategy (not
necessarily winning) in $H$ using at most $k$ hunters. Then, $\cal S$ is a
hunter strategy (not necessarily winning) in $G$ using at most $k$ hunters.
Since $h(G)>k$, there exists a rabbit-trajectory
$\mathcal{R}^{\prime}=(r^{\prime}_{0},r^{\prime}_{1},\dots,r^{\prime}_{\ell-1})$
in $G$ such that $r^{\prime}_{i}\notin S_{i+1}$ for every $0\leq i<\ell$. Let
${\cal R}=(r_{0},\dots,r_{\ell-1})$ be such that, for every $0\leq i<\ell$,
let $r_{i}=r^{\prime}_{i}$ if $r^{\prime}_{i}\in V(H)$ and, otherwise, let
$r_{i}$ be any vertex of $X\setminus S_{i+1}$ (such a vertex exists since
$|S_{i+1}|\leq k$ and $|X|>k$). Note that $r^{\prime}_{i}\neq r_{i}$ only if
$r^{\prime}_{i}\notin V(H)$ and therefore $r^{\prime}_{i}\in{\cal C}_{S}$.
This implies that, if $r^{\prime}_{i}\notin V(H)$, then
$r^{\prime}_{i-1},r^{\prime}_{i+1}\in S\subset V(H)$ (since
$N(r^{\prime}_{i})=S$). Therefore, $r_{i-1}=r^{\prime}_{i-1}$ and
$r_{i+1}=r^{\prime}_{i+1}$ and $r_{i-1},r_{i+1}\in N_{H}(r_{i})$ (since
$r_{i}\in X$ and so $N_{G}(r_{i})=N_{H}(r_{i})=S$). Therefore, $\cal R$ is a
rabbit trajectory in $H$ and, by construction, $r_{i}\notin S_{i+1}$ for every
$0\leq i<\ell$. Hence, $\mathcal{S}$ is not a winning hunter strategy.
Therefore, $h(H)>k$.

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

Finally, we present our kernelization result.

######  Theorem 9.

The problem that takes an $n$-node connected graph $G$ and an integer $k\geq
1$ as inputs and decides whether $h(G)\leq k$ (resp., $mh(G)\leq k$),
parameterised by any upper bound $t$ on $vc(G)$, admits a kernel of size at
most $4^{t}(t+1)+2t$. Moreover, this problem can be solved in $\mathsf{FPT}$
time $(4^{t}(t+1)+2t)^{t+1}\cdot n^{\mathcal{O}(1)}$.

###### Proof.

The kernelization proceeds as follows. First, if $k>t$, then answer that
$h(G)\leq mh(G)\leq k$ (this is correct by Proposition 7). Otherwise, let $U$
be a vertex cover of size at most $2t$ of $G$ (which can be computed in time
$\mathcal{O}(tn)$ by classical $2$-approximation for vertex cover using
maximal matching [28]). Let $H$ be the graph obtained from $G$ as follows. For
every $S\subseteq U$, if $|{\cal C}_{S}|>k+1$, then remove $|{\cal
C}_{S}|-(k+1)$ vertices from ${\cal C}_{S}$. By Lemma 28 (applied iteratively
for each $S\subseteq U$), $h(G)\leq k$ (resp., $mh(G)\leq k$) if and only if
$h(H)\leq k$ (resp., $mh(H)\leq k$). Moreover, $|V(H)|=|U|+\sum_{S\subseteq
U}|{\cal C}_{S}\cap V(H)|\leq 2t+2^{2t}(k+1)\leq 4^{t}(t+1)+2t$ (the last
inequality holds by Proposition 7). Hence, the above algorithm is the desired
kernelization algorithm.

Finally, applying the XP-algorithm [1], it can be decided in time
$|V(H)|^{k+1}$ whether $h(H)\leq k$. Since, by Proposition 7, $k\leq t$, this
gives the $\mathsf{FPT}$ algorithm that decides whether $h(G)\leq k$ (resp.,
$mh(G)\leq k$) in time $(4^{t}(t+1)+2t)^{t+1}\cdot n^{\mathcal{O}(1)}$. ∎

##  7 Some Future Directions

In this paper, we studied the Hunters and Rabbit game by defining the notion
of monotonicity for this game. Using this notion of monotonicity, we
characterised the monotone hunter number for various classes of graphs.
Moreover, we established that, unlike several graph searching games, the
monotonicity helps in this game, i.e., the $h(G)$ can be arbitrary smaller
than $mh(G)$.

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

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

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

##  8 Acknowledgements

This work is partially funded by the project UCA JEDI (ANR-15-IDEX-01) and the
EUR DS4H Investments in the Future (ANR-17-EURE-004) and the ANR Digraphs and
the ERC grant titled PARAPATH and the IFCAM project “Applications of graph
homomorphisms” (MA/IFCAM/18/39).

## References

  * [1] T. V. Abramovskaya, F. V. Fomin, P. A. Golovach, and M. Pilipczuk.  How to hunt an invisible rabbit on a graph.  European Journal of Combinatorics, 52:12–26, 2016.  doi:10.1016/j.ejc.2015.08.002.
  * [2] I. Adler.  Marshals, monotone marshals, and hypertree-width.  Journal of Graph Theory, 47(4):275–296, 2004.  doi:10.1002/jgt.20025.
  * [3] I. Adler.  Directed tree-width examples.  Journal of Combinatorial Theory, Series B, 97(5):718–725, 2007.  doi:10.1016/j.jctb.2006.12.006.
  * [4] D. Bienstock and P. D. Seymour.  Monotonicity in graph searching.  Journal of Algorithms, 12(2):239–245, 1991.  doi:10.1016/0196-6774(91)90003-H.
  * [5] H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks.  Approximating treewidth, pathwidth, frontsize, and shortest elimination tree.  Journal of Algorithms, 18(2):238–255, 1995.  doi:10.1006/jagm.1995.1009.
  * [6] J. Bolkema and C. Groothuis.  Hunting rabbits on the hypercube.  Discrete Mathematics, 342(2):360–372, 2019.  doi:10.1016/j.disc.2018.10.011.
  * [7] R. L. Breisch.  An intuitive approach to speleotopology.  Southwestern cavers, 6(5):72–78, 1967.
  * [8] J. R. Britnell and M. Wildon.  Finding a princess in a palace: a pursuit-evasion problem.  The Electronic Journal of Combinatorics, 20(1):25, 2013.  doi:10.37236/2296.
  * [9] M. Chapelle, M. Liedloff, I. Todinca, and Y. Villanger.  Treewidth and pathwidth parameterized by the vertex cover number.  Discrete Applied Mathematics, 216:114–129, 2017.  doi:10.1016/j.dam.2014.12.012.
  * [10] T. Chung, G. A. Hollinger, and V. Isler.  Search and pursuit-evasion in mobile robotics: A survey.  Autonomous Robots, 31(299):299–316, 2011.  doi:10.1007/s10514-011-9241-4.
  * [11] D. G. Corneil, Y. Perl, and L. K. Stewart.  A linear recognition algorithm for cographs.  SIAM Journal on Computing, 14(4):926–934, 1985.  doi:10.1137/0214065.
  * [12] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer Publishing Company, Incorporated, 1st edition, 2015.  doi:10.1007/978-3-319-21275-3.
  * [13] J. A. Ellis, I. H. Sudborough, and J. S. Turner.  The vertex separation and search number of a graph.  Information and Computation, 113(1):50–79, 1994.  doi:10.1006/inco.1994.1064.
  * [14] A. C. Giannopoulou, P. Hunter, and D. M. Thilikos.  Lifo-search: A min-max theorem and a searching game for cycle-rank and treedepth.  Discrete Applied Mathematics, 160(15):2089–2097, 2012.  doi:10.1016/j.dam.2012.03.015.
  * [15] G. Gottlob, N. Leone, and F. Scarcello.  Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width.  Journal of Computer and System Sciences, 66(4):775–808, 2003.  doi:10.1016/S0022-0000(03)00030-8.
  * [16] V. Gruslys and A. Méroueh.  Catching a mouse on a tree.  arXiv preprint, 2015.  URL: https://arxiv.org/abs/1502.06591, doi:10.48550/arXiv.1502.06591.
  * [17] J. Gustedt.  On the pathwidth of chordal graphs.  Discrete Applied Mathematics, 45(3):233–248, 1993.  doi:10.1016/0166-218X(93)90012-D.
  * [18] P. L. Hammer and B. Simeone.  The splittance of a graph.  Combinatorica, 1:275–284, 1981.  doi:10.1007/BF02579333.
  * [19] J. Haslegrave.  An evasion game on a graph.  Discrete Mathematics, 314:1–5, 2014.  doi:10.1016/j.disc.2013.09.004.
  * [20] D. Ilcinkas, N. Nisse, and D. Soguet.  The cost of monotonicity in distributed graph searching.  Distributed Computing, 22(2):117–127, 2009.  doi:10.1007/s00446-009-0089-1.
  * [21] A. Isaza, J. Lu, V. Bulitko, and R. Greiner.  A cover-based approach to multi-agent moving target pursuit.  In proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, pages 54–59. AAAI Press, 2008.  URL: http://www.aaai.org/Library/AIIDE/2008/aiide08-009.php, doi:10.1609/aiide.v4i1.18672.
  * [22] T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas.  Directed tree-width.  Journal of Combinatorial Theory Series B, 82(1):138–154, 2001.  doi:10.1006/jctb.2000.2031.
  * [23] A. S. LaPaugh.  Recontamination does not help to search a graph.  Journal of the ACM, 40(2):224–245, 1993.  doi:10.1145/151261.151263.
  * [24] F. Mazoit and N. Nisse.  Monotonicity of non-deterministic graph searching.  Theoretical Computer Science, 399(3):169–178, 2008.  doi:10.1016/j.tcs.2008.02.036.
  * [25] N. Nisse.  Network decontamination.  In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 516–548. Springer, 2019.  doi:10.1007/978-3-030-11072-7\\_19.
  * [26] T. D. Parsons.  Pursuit-evasion in a graph.  In Theory and Applications of Graphs, LNCS, volume 642, pages 426–441. Springer, 1978.  doi:10.1007/BFb0070400.
  * [27] P. D. Seymour and R. Thomas.  Graph searching and a min-max theorem for tree-width.  Journal of Combinatorial Theory, Series B, 58(1):22–33, 1993.  doi:10.1006/jctb.1993.1027.
  * [28] D. P. Williamson and D. B. Shmoys.  The Design of Approximation Algorithms. Cambridge University Press, 2011.  URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.
  * [29] B. Yang, D. Dyer, and B. Alspach.  Sweeping graphs with large clique number.  Discrete Mathematics, 309(18):5770–5780, 2009.  doi:10.1016/j.disc.2008.05.033.

##  Appendix A Appendix

See 6

###### Proof.

This clearly holds if $p=0$ (i.e., when $v\in V_{r}$) since $Z_{0}=V_{r}$. If
$p=1$ (i.e., when $v\in V_{w}$), there exists a rabbit trajectory $(r_{0}=u\in
N(v)\cap V_{r}\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 (and so $v\in V_{w}$): The rabbit can follow the following
trajectory: $(r_{0}=u,r_{1}=x,\ldots,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 (and so, $v\in V_{r}$): The rabbit can follow the following
trajectory: $(r_{0}=x,r_{1}=u,\ldots,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$
and $x,u\notin\bigcup_{j<i}S_{j}$. Therefore, $v\in Z_{p}$. ∎

See 18

###### Proof.

Let us recall that for any hunter strategy in $G$ with respect to $V_{r}$, if
$q$ is even, then $Z_{q}\subseteq V_{r}$ and $Z_{q}\subseteq V_{w}$ otherwise.
Thus , if $p=0$ or if $i=2$, $Z_{i}\subseteq Z_{p}$. Also, if $i=1$, then
$Z_{i}=Z_{p}$. Hence, let us assume that $p\geq 1$ and $i>2$. 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 6, $v\in Z_{p}$ for each $p\leq i$ such that $p$ and $i$ has the
same parity. ∎

See 19

###### 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}$.
W.l.o.g., let us assume that $u\in V_{r}$. Therefore, $N(u)\subseteq V_{w}$
and $q-1$ is odd.

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}$, $u\in N(x)$, $q-1$ is odd and $x\in
V_{w}$, by Proposition 6, 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 $v\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. ∎

See 20

###### Proof.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a monotone winning hunter strategy
for $G$ with respect to $V_{r}$.

If $|V(H)|=1$, the result clearly holds since $mh(H)=0$. Hence, let us assume
that $|V(H)|>1$. Let $m$ be the minimum integer such that $S_{m}\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$ and $H$ is connected, which implies that
$V_{r}\cap V(H)\neq\emptyset$). 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 5.

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$ with respect to $V_{r}\cap V(H)$. First, we show that
$\mathcal{S}^{\prime}$ is indeed a winning hunter strategy in $H$ with respect
to $V_{r}\cap V(H)$. Towards a contradiction, assume that
$\mathcal{S}^{\prime}$ is not a winning strategy in $H$ w.r.t. $V_{r}\cap
V(H)$. This implies that $Z_{\ell}({\cal S}^{\prime})\neq\emptyset$. Hence,
Claim 5 implies that $Z_{\ell}({\cal S})\neq\emptyset$, contradicting the fact
that $\mathcal{S}$ is a winning hunter strategy in $G$ with respect to
$V_{r}$.

Thus, $\mathcal{S}^{\prime}$ is a winning strategy in $H$ with respect to
$V_{r}\cap V(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 19, 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 5 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. ∎

See 21

###### Proof.

Let $\mathcal{S}=(S_{1},\dots,S_{\ell})$ be a monotone winning hunter strategy
with respect to $V_{r}$ using at most $k\geq mh_{V_{r}}(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<\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
winning hunter strategy with respect to $V_{r}$ 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+2i}\cap
Z_{j+2i-1}({\cal S})\neq\emptyset$. Let $v\in S_{j+2i}\cap Z_{j+2i-1}({\cal
S})$. Since $b\in Z_{j+2i-1}({\cal S})$, by Lemma 18, $v\in
Z_{j-1+2i^{\prime}}$ for every $0\leq i^{\prime}\leq i$.

Then, for every $0\leq i^{\prime}<i$, replace $S_{j+2i^{\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 strategyin $G$ with respect to $W\subseteq V_{r}$ using at most $k\geq
mh_{V_{r}}(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 19, 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$ and by the definition of $i$ above,
$v\notin\bigcup_{r<j+2i}S_{r}$ which implies that
$v\notin\bigcup_{r<j}S^{\prime}_{r}$. Since $v\in S^{\prime}_{j+2i^{\prime}}$
for all $0\leq i^{\prime}\leq i$ and, because $v\in Z_{j+2i-1}$ and by parity,
$v\notin Z_{j+2i^{\prime}}({\cal S}^{\prime})$ for all $0\leq i^{\prime}\leq
i$, we get that $m>j+2i$. 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+2i$) and $v\in
S_{j+2i}$, which contradicts the monotonicity of $\cal S$.

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

  * •

If $Z_{j+1}({\cal S})=Z_{j-1}({\cal S})$, then remove $S_{j}$ and $S_{j+1}$
from ${\cal S}$. Let ${\cal S}^{\prime}$ be the obtained strategy. We have
that $Z_{r}({\cal S})=Z_{r}({\cal S}^{\prime})$ and $S_{r}=S^{\prime}_{r}$ for
all $r<j$ and $Z_{r+2}({\cal S})=Z_{r}({\cal S}^{\prime})$ and
$S_{r+2}=S^{\prime}_{r}$ for all $j\leq r\leq\ell-2$. Hence, ${\cal
S}^{\prime}$ is winning since $Z_{\ell-2}({\cal S^{\prime}})=\emptyset$.
Moreover, if ${\cal S}^{\prime}$ is non-monotone, then, by Lemma 7, there
exists $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 $m<j$, this implies that $x\in Z_{m-1}({\cal S})\setminus S_{m}$ and
$x\in\bigcup_{h<m}S_{h}$ contradicting the monotonicity of $\cal S$. Otherwise
($m\geq j$), $x\in Z_{m+1}({\cal S})\setminus S_{m+2}$ and
$x\in\bigcup_{h<m+2}S_{h}$, also contradicting the monotonicity of $\cal S$.

Hence, we may assume that $Z_{j+1}({\cal S})\neq Z_{j-1}({\cal S})$.

  * •

Note first that by Lemma 18, $Z_{j+1}({\cal S})\subseteq Z_{j-1}({\cal S})$.
Thus, $Z_{j+1}({\cal S})\setminus Z_{j-1}({\cal S})=\emptyset$. Hence, since
$Z_{j+1}({\cal S})\neq Z_{j-1}({\cal S})$, we get that $Z_{j-1}({\cal
S})\setminus Z_{j+1}({\cal S})\neq\emptyset$.

Hence, there exists $v\in Z_{j-1}({\cal S})\setminus Z_{j+1}({\cal S})$. Let
${\cal S}^{\prime}$ be obtained by replacing $S_{j}$ by $\\{v\\}$. By
arguments similar to the ones of the third item of this proof, we can prove
that ${\cal S}^{\prime}$ is a monotone hunter strategy contradicting the
maximality of $j$.

This completes the proof. ∎

See 22

###### Proof.

First, for purpose of contradiction, let us assume that $v\in S_{i}\cap S_{j}$
and $v\notin S_{i+2}$ with $i<j$. Note that, since $G$ is bipartite, that
${\cal S}$ is a parsimonious strategy with respect to $V_{r}$ and $S_{i}\cap
S_{j}\neq\emptyset$, thus $i$ and $j$ must have the same parity and so, $j\geq
i+4$ (because $v\notin S_{i+2}$). Since $\mathcal{S}$ is parsimonious, $v\in
Z_{i-1}\cap Z_{j-1}$. Thus, by Lemma 18, $v\in Z_{i+1}\setminus S_{i+2}$ and
$v\in S_{i}$, contradicting the monotonicity of ${\cal S}$. Hence, the first
statement holds.

Let us now prove the second statement. Let us assume now that $v\in V_{r}$
(the case $v\in V_{w}$ can be handled similarly). If $v\notin Z_{i-1}$ for any
odd $1\leq i<\ell$, then $v\notin Z_{j-1}$ for any odd $i\leq j\leq\ell$ by
Lemma 18. Therefore, since ${\cal S}$ is parsimonious, $v\notin S_{j}$ for any
odd $i\leq j\leq\ell$. Moreover, since $G$ is bipartite and that ${\cal S}$ is
a parsimonious strategy with respect to $V_{r}$, for any even $1\leq
j\leq\ell$, $v\notin S_{j}$. ∎