# Parameterized Analysis of the Cops and Robber Problem

Harmender Gahlawat and Meirav Zehavi

Ben-Gurion University of the Negev, Beersheba, Israel

###### Abstract

Pursuit-evasion games have been intensively studied for several decades due to
their numerous applications in artificial intelligence, robot motion planning,
database theory, distributed computing, and algorithmic theory. Cops and
Robber (CnR) is one of the most well-known pursuit-evasion games played on
graphs, where multiple cops pursue a single robber. The aim is to compute the
cop number of a graph, $k$, which is the minimum number of cops that ensures
the capture of the robber.

From the viewpoint of parameterized complexity, CnR is W[2]-hard parameterized
by $k$ [Fomin et al., TCS, 2010]. Thus, we study structural parameters of the
input graph. We begin with the vertex cover number ($\mathsf{vcn}$). First, we
establish that $k\leq\frac{\mathsf{vcn}}{3}+1$. Second, we prove that CnR
parameterized by $\mathsf{vcn}$ is $\mathsf{FPT}$ by designing an exponential
kernel. We complement this result by showing that it is unlikely for CnR
parameterized by $\mathsf{vcn}$ to admit a polynomial compression. We extend
our exponential kernels to the parameters cluster vertex deletion number and
deletion to stars number, and design a linear vertex kernel for neighborhood
diversity. Additionally, we extend all of our results to several well-studied
variations of CnR.

##  1 Introduction

In pursuit-evasion, a set of agents, called pursuers, plan to catch one or
multiple evaders. Classically, pursuit-evasion games were played on geometric
setups, where pursuers and evaders move on the plane following some rules [46,
49, 67]. Parsons [65, 66] formulated pursuit-evasion on graphs to model the
search for a person trapped in caves, giving rise to the field of graph
searching. Since then, pursuit-evasion has been studied extensively, having
applications in artificial intelligence [50], robot motion planning [27, 55],
constraint satisfaction and database theory [42, 43, 44], distributed
computing [5, 29] and network decontamination [62], and significant
implications in graph theory and algorithms [75, 34, 1, 39].

Cops and Robber (CnR) is one of the most intensively studied pursuit-evasion
games on graphs, where a set of cops pursue a single robber. Players move in
discrete time steps alternately, starting with the cops. In each move, a
player can move to an adjacent vertex, and the cops win by capturing the
robber (i.e., if a cop and the robber occupy the same vertex). The goal is to
compute the cop number of a graph $G$, denoted $\mathsf{c}(G)$, which is the
minimum number of cops required to win in $G$. We define the game formally in
Section 2. CnR is well studied in the artificial intelligence literature under
the name Moving Target Pursuit (MTP) [51], where we consider sub-optimal but
faster strategies from an applicative point of view. The results have found
numerous applications in game design, police chasing, path planning, and robot
motion planning [78, 61, 77, 6, 81].

Determining the parameterized complexity of games is a well-studied research
topic [72, 18, 17]. Most pursuit-evasion games are, in fact, AW[*]-hard [73].
In particular, CnR is W[2]-hard parameterized by $\mathsf{c}(G)$ [36]. Thus,
we consider structural parameterizations, focusing on kernelization, also
known as polynomial-time preprocessing with a parametric guarantee. Due to the
profound impact of preprocessing, kernelization was termed “the lost continent
of polynomial time” [35]. We begin with the most studied structural parameter
in parameterized complexity: the vertex cover number ($\mathsf{vcn}$) of the
input graph. We bound $\mathsf{c}(G)$ in terms of $\mathsf{vcn}$, as well as
achieve both positive and negative results concerning the kernelization
complexity of CnR parameterized by $\mathsf{vcn}$. We generalize our
kernelization results to the smaller parameters cluster vertex deletion number
($\mathsf{cvd}$) and deletion to stars number ($\mathsf{dts}$), as well as to
the parameter neighborhood diversity ($\mathsf{nd}$). Furthermore, we extend
all our results to several well-studied variants of CnR.

The choice of $\mathsf{vcn}$ as a parameter to study pursuit-evasion games is
natural due to various scenarios where $\mathsf{vcn}$ is significantly smaller
than the graph size. For example, this includes scenarios where we model the
existence of one or few (possibly interconnected) central hubs—for
illustration, suppose an intruder is hiding in a system of buildings where we
have only few corridors but a large number of rooms, or suppose we have few
virtual servers with many stations (e.g., of private users) that can
communicate only with the servers. Furthermore, $\mathsf{vcn}$ is one of the
most efficiently computable parameters from both approximation [80] and
parameterized [28] points of view, making it fit from an applicative
perspective even when a vertex cover is not given along with the input.
Moreover, $\mathsf{vcn}$ is the best choice for proving negative
results—indeed, our negative result on the kernelization complexity of CnR for
$\mathsf{vcn}$ implies the same for many other well-known smaller parameters
such as treewidth, treedepth and feedback vertex set [37]. One shortcoming of
$\mathsf{vcn}$ as a parameter is that it is very high for some simple (and
easy to resolve) dense graphs like complete graphs. However, we generalize our
kernel to $\mathsf{cvd}$, which is small for these dense graphs, and for
$\mathsf{dts}$. Furthermore, we design a linear kernel for the well-studied
parameter $\mathsf{nd}$. We further discuss the utility of our kernels in the
Conclusion.

###  1.1 Brief Survey

CnR was independently introduced by Quilliot [71] and by Nowakowski and
Winkler [63] with exactly one cop111In fact, a specific instance of CnR on a
specific graph was given as a puzzle in Problem 395 of the book Amusements in
Mathematics [33] already in 1917.. Aigner and Fromme [3] generalized the game
to multiple cops and defined the cop number of a graph. The notion of cop
number and some fundamental techniques introduced by Aigner and Fromme [3]
yielded a plethora of results on this topic. For more details, we refer the
reader to the book [16].

The computational complexity of finding the cop number of a graph has been a
challenging subject of research. On the positive side, Berarducci and
Intrigila [10] gave a backtracking algorithm that decides whether $G$ is
$k$-copwin in $\mathcal{O}(n^{2k+1})$ time. On the negative side, Fomin et al.
[36] proved that determining whether $G$ is $k$-copwin is NP-hard, and
W[2]-hard parameterized by $k$. Moreover, Mamino [60] showed that the game is
PSPACE-hard, and later, Kinnersley [54] proved that determining the cop number
of a graph is, in fact, EXPTIME-complete. Recently, Brandt et al. [22]
provided fine-grained lower bounds, proving that the time complexity of any
algorithm for CnR is $\Omega(n^{k-o(1)})$ conditioned on Strong Exponential
Time Hypothesis ($\mathsf{SETH}$), and $2^{\Omega(\sqrt{n})}$ conditioned on
Exponential Time Hypothesis ($\mathsf{ETH}$).

Since CnR admits an XP-time algorithm, it is sensible to bound the cop number
for various graph classes or by some structural parameters. Nowadays, we know
that the cop number is 3 for the class of planar graphs [3] and toroidal
graphs [57], 9 for unit-disk graphs [11], 13 for string graphs [30], and is
bounded for bounded genus graphs [19] and minor-free graphs [4]. Moreover, it
is known that the cop number of a graph $G$ is at most
$\frac{\mathsf{tw}(G)}{2}+1$ [53], where $\mathsf{tw}(G)$ denotes the
treewidth of $G$, and at most $\mathsf{cw}(G)$ [36], where $\mathsf{cw}(G)$
denotes the clique-width of $G$.

###  1.2 Our Contribution

We conduct a comprehensive analysis of CnR parameterized by $\mathsf{vcn}$. We
start by bounding the cop number of a graph by its vertex cover number:

######  Theorem 1.

For a graph $G$, $\mathsf{c}(G)\leq\frac{\mathsf{vcn}}{3}+1$.

The proof is based on the application of three reduction rules. Each of our
rules controls its own cop that, in particular, guards at least three vertices
that belong to the vertex cover. Once our rules are no longer applicable, we
exhibit that the remaining unguarded part of the graph is of a special form.
In particular, we exploit this special form to prove that, now, the usage of
only two additional cops suffices. We complement Theorem 1 with an argument
(Lemma 20) that it might be difficult to improve this bound further using
techniques similar to ours.

Second, we prove that CnR parameterized by $\mathsf{vcn}$ is $\mathsf{FPT}$ by
designing a kernelization algorithm:

######  Theorem 2.

CnR parameterized by $\mathsf{vcn}$ admits a kernel with at most
$\mathsf{vcn}+\frac{2^{\mathsf{vcn}}}{\sqrt{\mathsf{vcn}}}$ vertices.

Our kernel is also based on the application of reduction rules. However, these
rules are very different than those used for the proof of Theorem 1. While our
main rule is quite standard in kernelization (involving the removal of, in
particular, false twins), the proof of its correctness is (arguably) not.
Theorem 2, along with Theorem 1 and an XP-algorithm (Proposition 13), gives
the following immediate corollary:

######  Corollary 3.

CnR is $\mathsf{FPT}$ parameterized by $\mathsf{vcn}$, and is solvable in
$\big{(}\mathsf{vcn}+\frac{2^{\mathsf{vcn}}}{\sqrt{\mathsf{vcn}}}\big{)}^{\\!\frac{\mathsf{vcn}}{3}+2}\\!\cdot
n^{\mathcal{O}(1)}$ time.

We complement our kernel by showing that it is unlikely for CnR to admit
polynomial compression, by providing a polynomial parameter transformation
from Red-Blue Dominating Set. In particular, our reduction makes non-trivial
use of a known construction of a special graph having high girth and high
minimum degree.

######  Theorem 4.

CnR parameterized by $\mathsf{vcn}$ does not admit polynomial compression,
unless NP $\subseteq$ coNP$/$poly.

Next, we present a linear kernel for CnR parameterized by neighbourhood
diversity:

######  Theorem 5.

CnR parameterized by $\mathsf{nd}$ admits a kernel with at most $\mathsf{nd}$
vertices.

On the positive side, we extend our exponential kernel to two smaller
structural parameters, $\mathsf{cvd}$ and $\mathsf{dts}$:

######  Theorem 6.

CnR parameterized by $\mathsf{cvd}$ admits a kernel with at most
$2^{2^{\mathsf{cvd}}+\sqrt{\mathsf{cvd}}}$ vertices. Moroever, CnR
parameterized by $\mathsf{dts}$ admits a kernel with at most
$2^{2^{\mathsf{dts}}+\mathsf{dts}^{1.5}}$ vertices.

Several variants of CnR have been studied due to their copious applications.
We extend our results, parameterized by vcn, to some of the most well-studied
ones. We define these variants (and used notations) in Section 2. We first
bound the cop number of these variants by $\mathsf{vcn}$:

######  Theorem 7.

For a graph $G$: (1) $\mathsf{c}_{lazy}\leq\frac{\mathsf{vcn}}{2}+1$; (2)
$\mathsf{c}_{attack}\leq\frac{\mathsf{vcn}}{2}+1$; (3)
$\mathsf{c}_{active}(G)\leq\mathsf{vcn}$; (4)
$\mathsf{c}_{surround}(G)\leq\mathsf{vcn}$; (5)
$\mathsf{c}_{s}(G)\leq\mathsf{vcn}$ (for any value of $s$); (6) for a strongly
connected orientation $\overrightarrow{G}$ of $G$,
$\mathsf{c}(\overrightarrow{G})\leq\mathsf{vcn}$.

We also extend our exponential kernel to these variants:

######  Theorem 8.

Cops and Attacking Robber and Lazy CnR parameterized by $\mathsf{vcn}$ admit a
kernel with at most
$\mathsf{vcn}+\frac{2^{\mathsf{vcn}}}{\sqrt{\mathsf{vcn}}}$ vertices.
Moreover, CnR on strongly connected directed graphs admits a kernel with at
most $3^{\mathsf{vcn}}+\mathsf{vcn}$ vertices.

Then, we present a slightly more general kernelization that works for most
variants of the game. In particular, we define a new variant of the game (in
Section 2), Generalized CnR,that generalizes various well studied variants of
CnR. We have the following result that proves that Generalized CnR
parameterized by $\mathsf{vcn}$ admits an exponential kernel.

######  Theorem 9.

Generalized CnR parameterized by $\mathsf{vcn}$ admits a kernel with at most
$\mathsf{vcn}+\mathsf{vcn}\cdot 2^{\mathsf{vcn}}$ vertices.

Then, we show that the same kernelization algorithm also provides us the
following result:

######  Theorem 10.

Fully Active CnR, Cops and Fast Robber, and Surrounding CnR parameterized by
$\mathsf{vcn}$ admit a kernel with at most $\mathsf{vcn}+\mathsf{vcn}\cdot
2^{\mathsf{vcn}}$ vertices.

Finally, we complement our exponential kernels for these variants by arguing
about their incompressibility:

######  Theorem 11.

Lazy CnR, Cops and Attacking Robber, Cops and Fast Robber, Fully Active CnR,
and CnR on strongly connected directed and oriented graphs parameterized by
$\mathsf{vcn}$ do not admit a polynomial compression, unless NP $\subseteq$
coNP$/$poly.

###  1.3 Additional Related Works

For a graph with girth at least 5, the cop number is lower bounded by the
minimum degree of the graph [3]. As implied by the lower bound for the
Zarankiewicz problem [82], an extremal graph with girth 5 has
$\Omega(n^{3/2})$ edges. In a graph with $\Omega(n^{3/2})$ edges, if there is
a vertex whose degree is smaller than $c\sqrt{n}$, for an appropriate constant
$c$, then we can remove it and still get a smaller graph with
$\Omega(n^{3/2})$ edges. Hence, eventually, every vertex has degree
$\Omega(\sqrt{n})$. Therefore, the cop number of such a graph is
$\Omega(\sqrt{n})$. Meyniel [38] conjectured this to be tight, that is,
$\mathcal{O}(\sqrt{n})$ cops are sufficient to capture the robber in any
connected graph. This is probably the deepest conjecture in this field (see
[7]). Since then, several attempts have been made to bound the cop number of
general graphs [26, 59, 74]. Although these results establish that the
$\mathsf{c}(G)=o(n)$, even the question whether
$c(G)=\mathcal{O}(n^{1-\epsilon})$, for $\epsilon>0$, remains open.

Many graph classes have unbounded cop number. The graph classes for which the
cop number is $\Omega(\sqrt{n})$ are called Meyniel extremal. These include
bipartite graphs [7], subcubic graphs [48], and polarity graphs [13].
Meyniel’s conjecture was also considered for random graphs [69, 70, 12].

Lastly, we remark that variations of CnR vary mainly depending on the
capabilities of the cops and the robber. Some of these variations were shown
to have correspondence with several width measures of graphs like treewidth
[75], pathwidth [65], tree-depth [41], hypertree-width [2], cycle-rank [41],
and directed tree-width [52]. Moreover, Abraham et al. [1] defined the concept
of a cop-decomposition, which is based on the cop strategy in the CnR game on
minor-free graphs provided by Andreae [4], and showed that it has significant
algorithmic applications.

##  2 Preliminaries

For $\ell\in\mathbb{N}$, let $[\ell]$ = $\\{1,\ldots,\ell\\}$. Whenever we
mention $\frac{a}{b}$, we mean $\lceil\frac{a}{b}\rceil$.

###  2.1 Graph Theory

For a graph $G$, we denote its vertex set by $V(G)$ and edge set by $E(G)$. We
denote the size of $V(G)$ by $n$ and size of $E(G)$ by $m$. In this paper, we
consider finite, connected222The cop number of a disconnected graph is the sum
of the cop numbers of its components; hence, we assume connectedness., and
simple graphs. Let $v$ be a vertex of a graph $G$. Then, by $N(v)$ we denote
the open neighbourhood of $v$, that is, $N(v)=\\{u\leavevmode\nobreak\
|\leavevmode\nobreak\ uv\in E(G)\\}$. By $N[v]$ we denote the close
neighbourhood of $v$, that is, $N[v]=N(v)\cup\\{v\\}$. For $X\subseteq V(G)$,
we define $N_{X}(v)=N(v)\cap X$ and $N_{X}[v]=N[v]\cap X$. We say that $v$
dominates $u$ if $u\in N[v]$. The girth of a graph $G$ is the length of a
shortest cycle contained in $G$. A $u,v$-path is a path with endpoints $u$ and
$v$. A path is isometric if it is a shortest path between its endpoints. For
$u,v\in V(G)$, let $d(u,v)$ denote the length of a shortest $u,v$-path.

Let $G$ be a graph and $U\subseteq V(G)$. Then, $G[U]$ denotes the subgraph of
$G$ induced by $U$. A set $U\subseteq V(G)$ is a vertex cover if
$G[V(G)\setminus U]$ is an independent set. The minimum cardinality of a
vertex cover of $G$ is its vertex cover number ($\mathsf{vcn}$). Moreover, $U$
is a cluster vertex deletion set if $G[V(G)\setminus U]$ is a disjoint union
of cliques. The minimum size of a cluster vertex deletion set of a graph is
its cluster vertex deletion number ($\mathsf{cvd}$). Additionally, $U$ is a
deletion to stars set if $G[V(G)\setminus U]$ is a disjoint union of star
graphs. The minimum size of a deletion to stars set of a graph is its deletion
to stars number ($\mathsf{dts}$). Two vertices $u,v\in V(G)$ have the same
type if and only if $N(v)\setminus\\{u\\}=N(u)\setminus\\{v\\}$. A graph $G$
has neighborhood diversity at most $w$ if there exists a partition of $V(G)$
into at most $w$ sets, such that all the vertices in each set have the same
type.

###  2.2 Cops and Robber

CnR is a two-player perfect information pursuit-evasion game played on a
graph. One player is referred as cop player and controls a set of cops, and
the other player is referred as robber player and controls a single robber.
The game starts with the cop player placing each cop on some vertex of the
graph, and multiple cops may simultaneously occupy the same vertex. Then, the
robber player places the robber on a vertex. Afterwards, the cop player and
the robber player make alternate moves, starting with the cop player. In the
cop player move, the cop player, for each cop, either moves it to an adjacent
vertex (along an edge) or keeps it on the same vertex. In the robber player
move, the robber player does the same for the robber. For simplicity, we will
say that the cops (resp., robber) move in a cop (resp., robber) move instead
of saying that the cop (resp., robber) player moves the cops (resp., robber).
Throughout, we denote the robber by $\small\mathcal{R}$.

A situation where one of the cops, say, $\small\mathcal{C}$, occupies the same
vertex as $\small\mathcal{R}$ is a capture. (We also say that the
$\small\mathcal{C}$ captures $\small\mathcal{R}$ and that $\small\mathcal{R}$
is captured by $\small\mathcal{C}$.) The cops win if they have a strategy to
capture $\small\mathcal{R}$, and $\small\mathcal{R}$ wins if it has a strategy
to evade a capture indefinitely. A graph $G$ is $k$-copwin if $k$ cops have a
winning strategy in $G$. The cop number of $G$, denoted $\mathsf{c}(G)$, is
the minimum $k$ such that $G$ is $k$-copwin. For brevity, $G$ is said to be
copwin if it is $1$-copwin (i.e. $\textsf{c}(G)=1$). Accordingly, we have the
following decision version of the problem.

Cops and Robber Input: A graph $G$, and an integer $k\in\mathbb{N}$ Question:
Is $G$ $k$-copwin?
---

We say that some cops guard a subgraph $H$ of $G$ if $\small\mathcal{R}$
cannot enter $H$ without getting captured by one of these cops in the next cop
move. We shall use the following result:

######  Proposition 12 ([3]).

Let $P$ be an isometric path in $G$. Then one cop can guard $P$ after a finite
number of rounds/cop moves.

Currently, the best known algorithm to decide whether $G$ is $k$-copwin is by
Petr et al. [68]:

######  Proposition 13 ([68]).

CnR is solvable in $\mathcal{O}(kn^{k+2})$ time.

If a cop $\small\mathcal{C}$ occupies a vertex $v$, then $\small\mathcal{C}$
attacks $N[v]$. A vertex $u$ is safe if it is not being attacked by any cop.
If $\small\mathcal{R}$ is on a vertex that is not safe, then
$\small\mathcal{R}$ is under attack.

###  2.3 Variations of CnR

Several variations of CnR have been studied in the literature, differing
mainly in the rules of movements of agents, the definition of the capture, and
the capabilities of the agents. We provide below the definitions of the games
considered in this paper. We list below some of the primary properties of the
gameplay in which these variations differ:

  1. 1.

Speed of agents: If an agent has speed $s$, where $s\in\mathbb{N}$, then the
agent can move along at most $s$ edges in its turn. We note that a robber with
speed $s$ cannot move over a cop, that is, the robber can move along a path of
length at most $s$ not containing any cop, in its turn.

  2. 2.

Lazy/active/flexible cops: Let $C$ be the set of cops and let $A\cup F\cup L$
be a partition of the set of cops such that $A$ is the set of active cops, $F$
be the set of flexible cops, and $L$ be the set of lazy cops. Then, in each
cop move, at most one cop from $L$ can make a move, each cop from $A$ must
make a move, and each cop from $F$ can either make a move or stay on the same
vertex. Unless mentioned otherwise, all cops are assumed to be flexible.

  3. 3.

Reach of cops: If a cop $\small\mathcal{C}_{i}$ has reach $\lambda_{i}$, then
$\small\mathcal{R}$ cannot access a vertex that is at a distance at most
$\lambda_{i}$ from the vertex occupied by $\small\mathcal{C}_{i}$. Here, think
of the cop $\small\mathcal{C}_{i}$ as having a gun with range $\lambda_{i}$.
Hence, if $\small\mathcal{C}_{i}$ can reach a vertex that is at most distance
$\lambda_{i}$ from the robber’s vertex at the end of a cop move, then
$\small\mathcal{C}_{i}$ can shoot $\small\mathcal{R}$, and the cops win.
Similarly, on a robber move, even if $\small\mathcal{R}$ has speed $s$, then
it can move only along a path of length at most $s$ that does not contain any
vertex that is at a distance at most $\lambda_{i}$ from
$\small\mathcal{C}_{i}$. In CnR, for each cop $\small\mathcal{C}_{i}$,
$\lambda_{i}=0$.

  4. 4.

Visible/invisible robber: If the robber is visible, then the cops know the
position of the robber. If the robber is invisible, then the cops do not know
the position of the robber. Moreover, we say that cops have $d$-visibility if
cops can see the position of the robber only if it is at most $d$ edges away
from at least one of the cops.

Next, we define the variants of CnR for which we will extend our results.

Lazy CnR: Lazy CnR [64] is one the the most well-studied variants of CnR games
[8, 76]. In this variant, the cops are lazy, that is, at most one cop can move
during a cops’ turn. This restricts the ability of the cops with respect to
the classical version. The minimum number of lazy cops that can ensure a
capture in a graph $G$ is known as the lazy cop number and is denoted by
$\mathsf{c}_{lazy}(G)$. Clearly, $\mathsf{c}(G)\leq\mathsf{c}_{lazy}(G)$, as
$\mathsf{c}_{lazy}(G)$ cops can capture the robber in the classical version
(using the winning strategy of the Lazy CnR game). We remark that this game is
also studied with the name one-cop-moves game [40, 79].

Cops and Attacking Robber: In Cops and Attacking Robber [15], the robber is
able to strike back against the cops. If on a robber’s turn, there is a cop in
its neighborhood, then the robber can attack the cop and eliminate it from the
game. However, if more than one cop occupy a vertex and the robber attacks
them, then only one of the cops gets eliminated, and the robber gets captured
by one of the other cops on that vertex. The cop number for capturing an
attacking robber on a graph $G$ is denoted by $\mathsf{c}_{attack}(G)$, and is
referred to as the attacking cop number of $G$. Clearly,
$\mathsf{c}(G)\leq\mathsf{c}_{attack}(G)\leq 2\cdot\mathsf{c}(G)$, as, on the
one hand, $\mathsf{c}_{attack}(G)$ cops can capture the robber in the
classical version. On the other hand, if we play the attacking version with
$2\cdot\mathsf{c}(G)$ cops using the strategy of the classical variant with
the only difference that there are always at least two cops on a vertex, then
the cops have a winning strategy.

Fully Active CnR: In the game of Fully Active CnR [45], each cop as well as
the robber are active, that is, in a cop/robber move, each cop/robber has to
move to an adjacent vertex. The active cop number of a graph $G$, denoted by
$\mathsf{c}_{active}(G)$, is the minimum number of cops that can ensure
capture in this game. It is easy to see that $\mathsf{c}_{active}(G)\leq
2\cdot\mathsf{c}(G)$, as if we keep one extra cop adjacent to each cop in the
winning strategy for CnR, then whenever some cop has to skip a move, it can
simply do so by switching with the extra cop adjacent to it.

Surrounding CnR: In the game of Surrounding CnR [23, 20], the definition of
capture is different. In this game, a cop and the robber can occupy the same
vertex of the graph during the game, but the robber cannot end its turn by
remaining at a vertex occupied by some cop. The cops win by surrounding the
robber, that is, if the robber occupies a vertex $v$, then there is a cop at
each vertex $u\in N(v)$. The surrounding cop number for a graph $G$ is denoted
as $\mathsf{c}_{surround}(G)$. It is easy to see that
$\mathsf{c}_{surround}(G)\geq\delta(G)$, where $\delta(G)$ is the minimum
degree of the graph.

Cops and Fast Robber: In the game of Cops and Fast Robber [36], the robber can
move faster than the cops. If $\small\mathcal{R}$ has speed $s$, then it can
move along a path with at most $s$ edges not containing any cop. The minimum
number of cops that can ensure capture of a fast robber with speed $s$ in a
graph $G$ is denoted by $\mathsf{c}_{s}(G)$. For $s\geq 2$, deciding whether
$\mathsf{c}_{s}(G)\leq k$ is NP-hard as well as W[2]-hard even when input
graph $G$ is restricted to be a split graph [36]. The game of Cops and Fast
Robber is well-studied [31, 9, 24].

CnR on Directed Graphs: The game of CnR is also well-studied for
oriented/directed graphs [58, 21, 47]. The game is played on a directed graph
$\overrightarrow{G}$, and the players can only move along the orientation of
the arcs.

Finally, we define a variant of CnR that generalizes many well-studied
variants of CnR:

Generalized CnR: Consider the following generalized version of CnR. Here the
input is
$(G,\small\mathcal{C}_{1},\ldots,\small\mathcal{C}_{k},\small\mathcal{R})$
where each cop $\small\mathcal{C}_{i}$ has speed $s_{i}$ (possibly different
for each cop) and $\small\mathcal{R}$ has speed $s_{R}$. Moreover, each cop
can be either forced to be active (all active cops have to move in each turn),
lazy (at most one lazy cop moves in each turn), or flexible (a flexible cop
can either move or stay on the same vertex in its move). Moreover, the robber
can also be forced to be either lazy or flexible. Furthermore, each cop
$\small\mathcal{C}_{i}$ can have reach $\lambda_{i}$ (possibly different for
each cop). This game generalizes several well-studied variants of CnR along
with Cops and Fast Robber, Fully Active CnR, and Cops and Robber From a
Distance [14]. It also generalizes the game of [61, 50].

Finally, we note that we assume the notion of “being active” to be defined
only when the agent has speed $s=1$. But, this notion can be defined in
multiple ways if the agent has speed $s>1$: the player might have to move at
least $s^{\prime}\leq s$ edges, the player may have to move to a vertex at a
distance at least $s^{\prime}\leq s$ from the current vertex, the player may
or may not be allowed to repeat edges, and so on. We remark that our
kernelization result for Generalized CnR can be made to work, with some
changes, considering any of these notions discussed.

###  2.4 An XP Algorithm for Variants

For graph searching games, there is a standard technique to get an XP-time
algorithm with running time $n^{\mathcal{O}(k)}$ (where $n$ is the size of
input graph and the question is whether $k$ cops have a winning strategy).
This technique involves generating a game graph where each vertex represents a
possible placement of all the agents on the vertices of $G$. Since $k$ cops
and a single robber can have $n^{k+1}$ possible placements on $G$, the game
graph has $n^{k+1}$ vertices. The following step is to mark all of the winning
states (that is, where the robber is captured). Afterwards, we use an
algorithm to keep adding states to the set of winning states in the following
manner. On a cop move, from a given state $S$, if there exists a movement of
cops that can change the game state $S$ to a winning state, we add $S$ to the
winning states. On a robber move, for a game state $S$, if all the possible
moves of the robber lead to a winning state, we add $S$ to the winning state.
Finally, if there exists a position of $k$ cops such that, for any position of
the robber, these states are in winning states, we declare that $k$ cops have
a winning strategy in $G$. It is easy to see that this algorithm can be
implemented in $n^{\mathcal{O}(k)}$ time.

Petr, Portier, and Versteegan [68] gave an implementation of this algorithm,
for CnR, that runs in $\mathcal{O}(kn^{k+2})$ time. It is not difficult to see
that this algorithm can be made to work for all the variants we discussed by
changing the rules to navigate between game states. For Cops and Attacking
Robber, the only extra consideration is that if $\small\mathcal{R}$ attacks a
cop (among $k$ cops) and does not get captured in the next cop move, then we
have a game state, say, $S^{\prime}$, with $k-1$ cops and one robber, where
the placement of these agents is a subset of a placement of $k+1$ agents in
one of the original game states, and hence we prune $S^{\prime}$. Thus, we
have the following proposition.

######  Proposition 14.

For any variant of CnR considered in this paper, an instance $(G,k)$ can be
solved in $\mathcal{O}(kn^{k+2})$ time.

###  2.5 Parameterized complexity

In the framework of parameterized complexity, each problem instance is
associated with a non-negative integer, called a parameter. A parametrized
problem $\Pi$ is fixed-parameter tractable ($\mathsf{FPT}$) if there is an
algorithm that, given an instance $(I,k)$ of $\Pi$, solves it in time
$f(k)\cdot|I|^{\mathcal{O}(1)}$ for some computable function $f(\cdot)$.
Central to parameterizedcomplexity is the W-hierarchy of complexity classes:
$\mathsf{FPT}\subseteq\mathsf{W[1]}\subseteq\mathsf{W[2]}\subseteq\ldots\subseteq\mathsf{XP}.$

Two instances $I$ and $I^{\prime}$ (possibly of different problems) are
equivalent when $I$ is a Yes-instance if and only if $I^{\prime}$ is a Yes-
instance. A compression of a parameterized problem $\Pi_{1}$ into a (possibly
non-parameterized) problem $\Pi_{2}$ is a polynomial-time algorithm that maps
each instance $(I,k)$ of $\Pi_{1}$ to an equivalent instance $I^{\prime}$ of
$\Pi_{2}$ such that size of $I^{\prime}$ is bounded by $g(k)$ for some
computable function $g(\cdot)$. If $g(\cdot)$ is polynomial, then the problem
is said to admit a polynomial compression. A kernelization algorithm is a
compression where $\Pi_{1}=\Pi_{2}$. Here, the output instance is called a
kernel. Let $\Pi_{1}$ and $\Pi_{2}$ be two parameterized problems. A
polynomial parameter transformation from $\Pi_{1}$ to $\Pi_{2}$ is a
polynomial time algorithm that, given an instance $(I,k)$ of $\Pi_{1}$,
generates an equivalent instance $(I^{\prime},k^{\prime})$ of $\Pi_{2}$ such
that $k^{\prime}\leq p(k)$, for some polynomial $p(\cdot)$. It is well-known
that if $\Pi_{1}$ does not admit a polynomial compression, then $\Pi_{2}$ does
not admit a polynomial compression [28]. We refer to the books [28, 37] for
details on parameterized complexity.

##  3 Bounding the Cop Number

In the following lemma, we give a general upper bound for the cop number,
which we use to derive bounds for several graph parameters.

######  Lemma 15.

Let $G$ be a graph and let $U\subseteq V(G)$ be a set of vertices such that
for each connected component $H$ of $G[V(G)\setminus U]$,
$\mathsf{c}(H)\leq\ell$. Then,
$\mathsf{c}(G)\leq\lceil\frac{|U|}{2}\rceil+\ell$.

###### Proof.

We note that this proof uses techniques used to bound $\mathsf{c}(G)$ in terms
of $tw(G)$ by Joret et al. [53]. Denote $U=\\{u_{1},\ldots,u_{q}\\}$. Consider
isometric paths $P_{1},\ldots,P_{\lceil\frac{q}{2}\rceil}$ such that the
endpoints of $P_{i}$ are $u_{2i-1}$ and $u_{2i}$. Note that these isometric
paths always exist as we assume that the graph is connected. Here,
$P_{\lceil\frac{q}{2}\rceil}$ might be a single vertex path containing only
the vertex $u_{q}$. Now, we guard each path $P_{i}$ using a single cop (due to
Proposition 12). These $\lceil\frac{q}{2}\rceil$ cops restrict the robber to
one connected component $H$ of $G[V(G)\setminus U]$. Since each of these
components is $\ell$-copwin, $\frac{q}{2}+\ell$ cops have a clear winning
strategy in $G$. ∎

We know that the classes of star graphs, complete graphs, chordal graphs, and
trees are copwin [63]. These bounds, along with Lemma 15, implies the
following theorem.

######  Theorem 16.

Let $G$ be a graph and $t=\min\\{\mathsf{cvd},\mathsf{dts}\\}$. Then,
$\mathsf{c}(G)\leq\frac{t}{2}+1$.

###  3.1 Bounding Cop Number by $\mathsf{vcn}$:

Let $U$ be a vertex cover of size $t$ in $G$ and $I$ be the independent set
$V(G)\setminus U$. Lemma 15 implies that
$\mathsf{c}(G)\leq\lceil\frac{t}{2}\rceil+1$. In this section, we improve this
bound. First, we provide the following reduction rules.

######  Reduction Rule 1 (RR1).

If there is a vertex $v\in I$ such that $|N(v)|\geq 3$, then place a cop at
$v$ and delete $N[v]$.

######  Reduction Rule 2 (RR2).

If there is a vertex $v\in U$ such that $|N[v]\cap U|\geq 3$, then place a cop
at $v$ and delete $N[v]$.

######  Reduction Rule 3 (RR3).

If there is an isometric path $P$ such that $P$ contains at least three
vertices from $U$, then guard $P$ using one cop and delete $V(P)$ (see
Proposition 12).

We remark that RR1 and RR2 can be merged, but we prefer to keep them separate
to ease the presentation. Moreover, we note the following.

######  Note 17.

In the application of reduction rules RR1-RR3, whenever a set of vertices
$X\subseteq V(G)$ is deleted by the application of rules RR1-RR3, it implies
that each vertex $x\in X$ is being guarded by some cop, and hence, is not
accessible to $\small\mathcal{R}$. We do not actually delete the vertices, and
this deletion part is just for the sake of analysis. Hence, from the cop
player’s perspective, the graph remains connected.

Second, we have the following lemma concerning the structure of subgraphs
accessible to $\small\mathcal{R}$ after an exhaustive application of rules
RR1-RR3.

######  Lemma 18.

Let $H$ be a connected component of $G$ where rules RR1-RR3 cannot be applied
anymore. Then, for every two distinct vertices $x,y\in V(H)\cap U$, either
$xy\in E(G)$ or there exists a vertex $w\in I$ such that $xw\in E(G)$ and
$yw\in E(G)$.

###### Proof.

For contradiction, let us assume that there exist two distinct vertices
$x,y\in V(H)\cap U$ such that $xy\notin E(G)$ and there does not exist a
vertex $w\in I$ such that $xw\in E(G)$ and $yw\in E(G)$. Since $x$ and $y$ are
part of the connected component $H$, there exists an $x,y$-path. Let $P$ be an
isometric $x,y$-path.

Let $P=x,v_{1},\ldots,v_{\ell},y$. Since vertices in $I$ form an independent
set and $\ell\geq 2$, the vertices $v_{1},\ldots,v_{\ell}$ cannot be all from
$I$. So, there exists at least one $v_{i}$, for $i\in[\ell]$, such that
$v_{i}\in U$. Thus, $P$ contains at least three vertices from $U$, and $P$ is
an isometric path. Therefore, we can apply RR3, and hence, we reach a
contradiction. ∎

Next, we argue that, after an exhaustive application of rules RR1-RR3, the cop
number of each connected component accessible to $\small\mathcal{R}$ is
bounded. We have the following lemma.

######  Lemma 19.

Once we cannot apply rules RR1-RR3 anymore, let the robber be in a connected
component $H$. Then, $c(H)\leq 2$.

###### Proof.

We present a winning strategy for two cops. If $H$ contains at most two
vertices from $U$, then the cops have a winning strategy by placing a cop on
each of these vertices. Hence, we assume there exist at least three vertices
in $H$ from $U$. Let $x$ and $y$ be two distinct vertices of $H$ from $U$.
Then, we place a cop on each of these vertices. Denote the cops by
$\small\mathcal{C}_{1}$ and $\small\mathcal{C}_{2}$. We consider the two cases
as follows.

Case 1: If $\small\mathcal{R}$ is on a vertex in $w\in I$, then due to
reduction rule RR1, it can have at most two neighbors in $U$. Let them be $u$
and $v$. Now, due to Lemma 18, the cops can move to vertices such that one of
them, say $x^{\prime}$, dominates the vertex $u$ and the other, say
$y^{\prime}$, dominates the vertex $v$. See Figure 1 for reference. So, the
cops move to the vertices $x^{\prime}$ and $y^{\prime}$. This restricts
$\small\mathcal{R}$ to stay on its current vertex $w$ in $I$ (else it is
captured in the next move of the cops). Now, in the next move of the cops,
they move to the vertices $u$ and $v$. Again, this restricts
$\small\mathcal{R}$ to stay on the vertex $w$ (else it is indeed captured).
Finally, in the next move of the cops, the cops capture $\small\mathcal{R}$.

Figure 1: Illustration for the proof of Lemma 19.

Case 2: If $\small\mathcal{R}$ is on a vertex in $u\in U$, then
$\small\mathcal{C}_{1}$ can move to a vertex in $I$, say $x^{\prime}$, to
attack $\small\mathcal{R}$ (due to Lemma 18). This forces $\small\mathcal{R}$
to either move to a vertex $w\in I$ or to a vertex $z\in U$. Accordingly, we
consider two sub-cases.

  1. 1.

If $\small\mathcal{R}$ moves to a vertex $w\in I$, then note that $w$ can have
at most two neighbors in $U$ (due to RR1), and one of them is $u$ (being
attacked by $\small\mathcal{C}_{1}$). Let the other neighbor of $w$ be $v$.
Now, $\small\mathcal{C}_{2}$ can move to a vertex such that it attacks $v$
(due to Lemma 18). This game state is identical to case 1. Hence, the cops can
capture the robber in two rounds.

  2. 2.

If $\small\mathcal{R}$ moves to a vertex $z\in U$, then
$\small\mathcal{C}_{1}$ moves to $u$. This forces $\small\mathcal{R}$ to move
to a vertex in $I$ since $u$ can have only one neighbor in $U$ (due to RR2),
and that is occupied by $C_{1}$, with both cops being in $U$. This game state
is again identical to case 1, and thus the cops win in at most two rounds.

This completes our proof. ∎

Finally, we have the following theorem.

See 1

###### Proof.

The correctness of this theorem follows from Lemma 19 and the fact that using
each cop in the reduction rules RR1, RR2, and RR3, we remove at least three
vertices from $U$. If we can apply these rules $\frac{t}{3}$ times,
$\small\mathcal{R}$ gets restricted to a vertex in $I$, and thus one
additional cop can capture $\small\mathcal{R}$. Else, when we apply these
rules at most $\frac{t}{3}-1$ times, we then need two additional cops (by
Lemma 19), that is, we overall need at most $\frac{t}{3}+1$ cops to ensure
capture. ∎

We note here that a similar technique will fail if we try to “remove” four
vertices in each reduction rule. More precisely, if we have the following
reduction rules, then we might not get a graph with a bounded (by a constant
independent of the input) cop number.

######  Reduction Rule 4 (RR4).

If there is a vertex $v\in I$ such that $|N(v)|\geq 4$, then place a cop at
$v$ and delete $N[v]$.

######  Reduction Rule 5 (RR5).

If there is a vertex $v\in U$ such that $|N[v]\cap U|\geq 4$, then place a cop
at $v$ and delete $N[v]$.

######  Reduction Rule 6 (RR6).

If there is an isometric path $P$ such that $P$ contains at least four
vertices from $U$, then guard $U$ using one cop and delete $V(P)$ (see
Proposition 12).

We have the following claim.

######  Lemma 20.

For every $k\in\mathbb{N}$, there exists a graph $G$ with a vertex cover $U$
and independent set $I=V(G)\setminus U$, such that we cannot apply the rules
RR4-RR6, and $\mathsf{c}(G)>k$.

###### Proof.

Bonato and Burgess [13] proved that for every $k$, there exists a diameter-2
graph $H$ such that $c(H)\geq k$. Let $H$ be a diameter-2 graph such that
$c(H)\geq k$. Joret et al. [53] showed that subdividing each edge of a graph
an equal number of times does not reduce the cop number. So, we subdivide each
edge of $H$ to get the graph $G$ such that $\mathsf{c}(G)\geq k$. Now, we can
put the original vertices in the vertex cover $U$, and the newly introduced
vertices in the independent set $I$. We cannot apply any of the rules RR4
(because each vertex in $I$ has degree exactly 2), RR5 (because $U$ is an
independent set), and RR6 (since any isometric path in $G$ containing more
than three vertices of $U$ will contradict the fact that $H$ is a diameter-2
graph). Hence, $G$ is a graph that satisfies the conditions of our lemma. ∎

###  3.2 Bounding the Cop Number for Variants

Here we extend the result of Theorem 1 to several variations of the game. In
particular, we prove the following result.

######  Lemma 21.

Let $G$ be a graph with a vertex cover $U$ of size $t$. Then,

  1. 1.

$\mathsf{c}_{lazy}\leq\frac{t}{2}+1$.

  2. 2.

$\mathsf{c}_{attack}\leq\frac{t}{2}+1$.

###### Proof.

Let $I$ be the independent set $V(G)\setminus U$. First, we note here that in
Cops and Attacking Robber, one cop cannot ensure guarding of an isometric
paths [15], and in Lazy CnR, multiple cops, say, $\ell$ cops, cannot ensure
guarding $\ell$ paths simultaneously. (This is evident from the fact that
there exists a planar graph $G$ with $\mathsf{c}_{lazy}(G)\geq 4$ [40].)
Therefore, reduction rules RR1-RR3 will not directly imply an upper bound on
the respective cop numbers here. So, we have the following reduction rules:

######  Reduction Rule 7 (RR7).

If there is a vertex $v\in I$ such that $N(v)>1$, then place a cop at $v$ and
delete $N[v]$.

######  Reduction Rule 8 (RR8).

If there is a vertex $v\in U$ such that $N_{U}[v]>1$, then place a cop at $v$
and delete $N[v]$.

Observe that after an exhaustive application of reduction rules RR7 and RR8,
we are left with a collection of stars, each of which has its center vertex in
$U$.

In the case of Lazy CnR, we can easily apply rules RR7 and RR8, since cops do
not move once placed according to an application of reduction rules RR7 and
RR8, except for when they move to capture $\small\mathcal{R}$. Finally,
$\small\mathcal{R}$ is restricted to a star, and one extra lazy cop can move
and capture $\small\mathcal{R}$.

In the case of Cops and Attacking Robber, all cops start at the same vertex.
Whenever the cop player wants to station one of the cops at a vertex $v$
according to rules RR7 and RR8, all of the cops that are not stationed yet
move together to the vertex $v$ (to avoid getting attacked). Note that once a
cop is stationed at a vertex $u$, the cop never moves and hence can never be
attacked (because if $\small\mathcal{R}$ wants to attack a cop at vertex $v$,
it has to reach a vertex in $N(v)$ in the previous round, and now the cop at
$v$ can move and capture $\small\mathcal{R}$). Once we cannot apply rules RR7
and RR8 anymore, $\small\mathcal{R}$ is restricted to a star. At this point,
if there are at least two unstationed cops, then these two cops can move to
capture $\small\mathcal{R}$. Else, let $v$ be the last vertex where we
stationed a cop. Since at this point we have stationed all but one cop
($\frac{t}{2}$ cops stationed), observe that for each vertex $x\in U$, there
is a cop in $N[x]$, and therefore, $\small\mathcal{R}$ is restricted to one
vertex, say, $u$, of $I$. Now, $\small\mathcal{R}$ can only attack a cop if it
is at a vertex in $N(u)$ (and $N(u)\subseteq U$). Finally, the only
unstationed cop, say, $\small\mathcal{C}$, moves to a vertex in $N(u)$ in a
finite number of steps (at this point $\small\mathcal{R}$ cannot attack
$\small\mathcal{C}$ without getting captured as $\small\mathcal{C}$ is on a
vertex in $U$), and captures $\small\mathcal{R}$ in the next round.

The bound on the cop numbers follow from the fact that in each reduction rule,
we remove at least two vertices from $U$ and place only one cop. ∎

We have the following straightforward observation concerning the bounds on the
cop number for the remaining variants.

######  Observation 22.

Let $t$ be the $\mathsf{vcn}$ of a graph $G$. Then,
$\mathsf{c}_{active}(G)\leq t$, $\mathsf{c}_{surround}(G)\leq t$,
$\mathsf{c}_{s}(G)\leq t$ (for any value of $s$), and for a strongly connected
orientation $\overrightarrow{G}$ of $G$, $\mathsf{c}(\overrightarrow{G})\leq
t$.

We remark that the cop number for an oriented graph $\overrightarrow{G}$ (with
underlying graph $G$) that is not strongly connected can be arbitrarily larger
than the $\mathsf{vcn}$ of $G$. To see this, consider a vertex cover $U$ of
size $t$ in $G$. Next, we add $\ell$ vertices $v_{1},\ldots,v_{\ell}$ such
that each vertex $v_{i}$, for $i\in[\ell]$, has only outgoing edges to
vertices in $U$. Now, if we do not place a cop on some $v_{j}$, for
$j\in[\ell]$, then $\small\mathcal{R}$ can start at $v_{j}$ and cops can never
capture $\small\mathcal{R}$. Hence, $\mathsf{c}(\overrightarrow{G})\geq\ell$.

The proof of Theorem 7 directly follows from Lemma 21 and Observation 22.

##  4 Kernelization Algorithms

In this section, we provide kernelization algorithms for CnR and its variants.

###  4.1 Exponential Kernel for CnR by $\mathsf{vcn}$:

Let $G$ be a graph where a vertex cover $U$ of size $t$ is given. If no such
vertex cover is given, then we can compute a vertex cover $U$ of size $t\leq
2\cdot\mathsf{vc}(G)$ using a polynomial-time approximation algorithm [80].
Then, the vertices in $V(G)\setminus U$ form an independent set $I$ of size
$n-t$. Recall that the question is whether $G$ is $k$-copwin.

Our kernelization algorithm is based on the exhaustive application of the
following reduction rules.

######  Reduction Rule 9 (RR9).

If $k\geq\frac{t}{3}+1$, then answer positively.

######  Reduction Rule 10 (RR10).

If $k=1$, then apply an $\mathcal{O}(n^{3})$ time algorithm (Proposition 13)
to check whether $G$ is copwin.

######  Reduction Rule 11 (RR11).

If there are two distinct vertices $u,v\in I$ such that $N(u)\subseteq N(v)$,
then delete $u$.

The safeness of rule RR9 follows from Theorem 1. For the safeness of rule
RR11, we have the following lemma. We note that Lemma 23 can also be derived
from [10, Corollary 3.3], but we give a self-contained proof for the sake of
completeness.

######  Lemma 23.

Let $u$ and $v$ be two distinct vertices of $G$ such that $N(u)\subseteq
N(v)$. Consider the subgraph $H$ of $G$ induced by $V(G)\setminus\\{u\\}$. Let
$k\geq 2$. Then, $G$ is $k$-copwin if and only if $H$ is $k$-copwin.

###### Proof.

First, we show that if $G$ is $k$-copwin, then $H$ is $k$-copwin. For the
graph $H$, the $k$ cops borrow the winning strategy that they have for $G$,
with the only difference that whenever a cop has to move to the vertex $u$ in
$G$, it moves to $v$ (in $H$) instead. Since $N(u)\subseteq N(v)$, the cop can
make the next move as it does in the winning cop strategy for $G$. Note that
using this strategy, the cops can capture $\small\mathcal{R}$ if
$\small\mathcal{R}$ is restricted to $V(H)$ in $G$. Therefore, using this
strategy, $k$ cops will capture $\small\mathcal{R}$ in $H$ as well.

Second, we show that if $H$ is $k$-copwin, then $G$ is is $k$-copwin. Here,
for each vertex $x\neq u$ of $G$, we define $I(x)=x$, and for $u$, we define
$I(u)=v$. Observe that for each $x\in V(G)$, $I(x)$ is restricted to $H$ and
if $xy\in E(G)$, then $I(x)I(y)\in E(H)$. Therefore, every valid move of a
player from a vertex $x$ to $y$ in $G$ can be translated to a valid move from
$I(x)$ to $I(y)$ in $H$. Now, the cops have the following strategy. If the
robber is on a vertex $x$, the cops consider the image of the robber on the
vertex $I(x)$. Since the robber’s image is restricted to $H$, the cops can use
the winning strategy for $H$ to capture the image of the robber in $G$. Once
the image is captured, if the robber is not on the vertex $u$, then the robber
is also captured. Otherwise, the robber is on the vertex $u$, and at least one
cop is on $v$. See Figure 2 for an illustration. So, one cop, say
$\mathcal{C}_{1}$, stays on $v$ and this prevents the robber from ever leaving
$u$. Indeed this follows because $N(u)\subseteq N(v)$, and so, if
$\small\mathcal{R}$ ever leaves $u$, it will be captured by $\mathcal{C}_{1}$
in the next cop move. Finally, since $k>1$, some other cop, say
$\mathcal{C}_{2}$, can use a finite number of moves to reach $u$ and capture
the robber.

This completes our proof. ∎

Figure 2: Illustration for Lemma 23. Here, $\small\mathcal{R}$ is at vertex
$u$ and $\small\mathcal{C}_{1}$ is at vertex $v$.

Note that the requirement for $k\geq 2$ in Lemma 23 is crucial. It might so
happen that we can get an $H$ such that $c(H)=1$, but $\mathsf{c}(G)>1$. To
see this, consider the example of $C_{4}$, where any two diagonal (i.e., non-
adjacent) vertices satisfy the property in Rule RR9, and if we remove one of
them, the cop number reduces from 2 to 1. However, this does not harm our
algorithm because if we are given $k=1$, then RR10 is applied (before RR11).

Two sets $A$ and $B$ are incomparable if neither $A\subseteq B$ nor
$B\subseteq A$. We shall use the following proposition that follows from
Sperner’s Theorem and Stirling’s approximation.

######  Proposition 24.

Let $X$ be a set of cardinality N. Moreover, let $Y$ be a set of subsets of
$X$ such that for each $a,b\in Y$, $a$ and $b$ are incomparable. Then,
$|Y|\leq\frac{2^{N}}{\sqrt{N}}$.

Once we cannot apply RR9-RR11 anymore, we claim that the size of the reduced
graph $G^{\prime}$ is bounded by a function of $t$. Let $U^{\prime}=U\cap
V(G^{\prime})$ and $I^{\prime}=I\cap V(G^{\prime})$. Clearly,
$|U^{\prime}|\leq t$. Now, each vertex $u\in I^{\prime}$ is associated with a
neighborhood $N(u)$ such that $N(u)\subseteq U^{\prime}$. Moreover, for any
two vertices $u,v\in I^{\prime}$, the sets $N(u)$ and $N(v)$ are incomparable.
Hence, due to Proposition 24, $|I^{\prime}|\leq\frac{2^{t}}{\sqrt{t}}$, and
therefore, $|V(G^{\prime})|\leq t+\frac{2^{t}}{\sqrt{t}}$, which proves the
following theorem. See 2

Now, we can apply the XP-time algorithm (Proposition 13) for CnR on our
kernel. Since $k\leq\frac{t}{3}$, the running time we get is exponential only
in $t$ and polynomial in $n$. Specifically, the running time of the algorithm
is $t\cdot\big{(}t+\frac{2^{t}}{\sqrt{t}}\big{)}^{\frac{t}{3}+2}\cdot
n^{\mathcal{O}(1)}$. Moreover, if a vertex cover $U$ of size
$t=\mathsf{vc}(G)$ is not given, then we can compute one in time
$1.2738^{t}\cdot n^{\mathcal{O}(1)}$ [25]. Thus, we have the following
corollary.

See 3

###  4.2 Exponential Kernel for CnR by $\mathsf{cvd}$:

To get a kernel for CnR parameterized by $\mathsf{cvd}$, we employ techniques
similar to the ones we used to get a kernel for CnR parameterized by
$\mathsf{vcn}$. Let $U$ be a cluster vertex deletion set of size $t$. Let
$S=V(G)\setminus U$, and $C_{1},\ldots,C_{\ell}$ be the set of disjoint
cliques that form the graph $G[S]$. Since $\mathsf{c}(G)\leq\frac{t}{2}+1$
(Theorem 16), we have the following reduction rule.

######  Reduction Rule 12 (RR12).

If $k\geq\frac{t}{2}+1$, then report Yes-instance.

Next, we have the following lemma.

######  Lemma 25.

Let $u$ and $v$ be vertices of some clique $C$ of $G[S]$. If
$N_{U}(u)\subseteq N_{U}(v)$, then
$\mathsf{c}(G)=\mathsf{c}(G\setminus\\{u\\})$.

###### Proof.

First we observe that, since $u$ and $v$ are part of the same clique $C$,
$N[u]\subseteq N[v]$. Then, the proof of this lemma follows from the proof of
Lemma 23. We remark that this proof also follows from the idea of retracts
used in the CnR literature [10, 63]. Additionally, we remark that, here,
$\mathsf{c}(G)$ need not be necessarily greater than 1. To see this, consider
the situation when $\small\mathcal{R}$ is at $u$ and a cop, say,
$\small\mathcal{C}_{1}$, is at $v$. Now, $\small\mathcal{R}$ cannot move to a
vertex in $U$ since $N_{U}(u)\subseteq N_{U}(v)$ and $\small\mathcal{R}$
cannot stay on a vertex in $C$ since $v$ is a part of $C$. Thus,
$\small\mathcal{R}$ gets captured in the next move by $\small\mathcal{C}_{1}$.
∎

Hence, we can apply the following reduction rule, whose safeness was proved by
Lemma 25.

######  Reduction Rule 13 (RR13).

Let $u$ and $v$ be vertices of some clique $C\in G[S]$ such that
$N[u]\subseteq N[v]$. Then, delete $u$.

Once we cannot apply reduction rule RR13 anymore, the size of each clique in
$G[S]$ is at most $\frac{2^{t}}{\sqrt{t}}$ (due to Proposition 24).

Similarly to Lemma 25, we have the following lemma.

######  Lemma 26.

Let $C_{i}$ and $C_{j}$ be two cliques in $G[S]$ such that for each vertex
$u\in V(C_{i})$, there exists a vertex $v\in V(C_{j})$ such that
$N_{U}(u)\subseteq N_{U}(v)$. Then, $k>1$ cops have a winning strategy in $G$
if and only if they have a winning strategy in $G[V(G)\setminus V(C_{i})]$.

###### Proof.

The proof idea here is similar to the proof idea of Lemma 23. Let
$H=G[V(G)\setminus V(C_{i})]$. Here, we will just prove that if $k$ cops have
a winning strategy in $H$, then $k$ cops have a winning strategy in $G$. (The
proof of the reverse direction is rather easy to see, combining arguments from
Lemma 23 and the arguments we present in the rest of this proof).

Let $k\geq 2$ cops have a winning strategy in $H$. Similarly to Lemma 23, for
each vertex $x\in V(G)\setminus V(C_{i})$, we define $I(x)=x$, and for each
vertex $u\in V(C_{i})$, we have a vertex $v\in V(C_{j})$ such that
$N_{U}(u)\subseteq N_{U}(v)$, and we define $I(u)=v$. (Note that there might
be multiple choices for $v$ here. We can choose any such vertex.)

Observe that for each vertex $x\in V(G)$, $I(x)$ is restricted to $H$.
Moreover, if $xy\in E(G)$, then $I(x)I(y)\in E(H)$ for the following reasons.
If $x,y\in V(G)\setminus V(C_{i})$, then it is obvious. Else, if $x,y\in
V(C_{i})$, then observe that $I(x)$ and $I(y)$ are part of some clique
$C_{j}$, and $N_{U}(x)\subseteq N_{U}(I(x))$ and $N_{U}(y)\subseteq
N_{U}(I(y))$. Hence, in this case, if $xy\in E(G)$, then $I(x)I(y)\in E(H)$.
Finally, assume without loss of generality that $x\in V(C_{i})$ and $y\in
V(G)\setminus V(C_{i})$. In this case, $xy\in E(G)$ only if $y\in U$. Since
$N_{U}(x)\subseteq N_{U}(I(x))$, $I(x)I(y)\in E(H)$. Thus, if $xy\in E(G)$,
then $I(x)I(y)\in E(H)$. Therefore, every valid move of a player from a vertex
$x$ to a vertex $y$ in $G$ can be translated to a move from $I(x)$ to $I(y)$
in $H$.

Now, cops play their winning strategy in $H$ with the following consideration:
When the robber is at a vertex $x$ in $G$, the cops consider the image of the
robber at vertex $I(x)$ in $G$. Since the robber’s image is restricted to the
vertices of $H$, the cops can use a winning strategy from $H$ to capture the
image of the robber in $G$. Once the image is captured, if the robber is at a
vertex $x\notin V(C_{i})$, then the robber is also captured. Otherwise, the
robber is at a vertex $x\in V(C_{i})$, and one of the cops is at vertex $I(x)$
in $C_{j}$. Now, observe that the robber cannot immediately move to a vertex
in $U$. Anyhow, the robber can move to some other vertex $y\in V(C_{i})$, and
in this case, the cop at vertex $I(x)$ can move to vertex $I(y)\in V(C_{j})$.
This way, the cop occupying the robber’s image can prevent the robber from
ever leaving $C_{i}$. Since $k\geq 2$, some other cop can move to capture the
robber in $C_{i}$ (as cliques are copwin). This completes our proof. ∎

Thus, we can apply the following reduction rule, whose safeness was proved by
Lemma 26.

######  Reduction Rule 14 (RR14).

Let $C_{i}$ and $C_{j}$ be two cliques in $G[S]$ such that for each vertex
$u\in V(C_{i})$, there exists a vertex $v\in V(C_{j})$ such that
$N_{U}(u)\subseteq N_{U}(v)$. Then, delete $V(C_{i})$.

Finally, we use the following lemma to bound the size of the desired kernel
from Theorem 6.

######  Lemma 27.

After an exhaustive application of RR12-RR14, the size of the reduced graph is
at most $2^{2^{t}+\sqrt{t}}$.

###### Proof.

Once we cannot apply the reduction rules RR13 and RR14, due to Proposition 24,
each clique can have at most $\frac{2^{t}}{\sqrt{t}}$ vertices. Moreover, the
total number of cliques possible is at most
$\frac{2^{\frac{2^{t}}{\sqrt{t}}}}{\sqrt{\frac{2^{t}}{\sqrt{t}}}}$ (due to
Proposition 24). Thus, the total number of vertices in the reduced graph is at
most $2^{2^{t}+\sqrt{t}}$. ∎

Since $k\leq\frac{t}{2}+1$ (by Reduction Rule RR12), applying the XP-algorithm
for CnR from Proposition 13 to the kernel in Theorem 6 gives us the following
corollary.

######  Corollary 28.

CnR is $\mathsf{FPT}$ parameterized by $\mathsf{cvd}$. Specifically, it is
solvable in
$(\mathsf{cvd}+2^{2^{\mathsf{cvd}}+\sqrt{\mathsf{cvd}}})^{\frac{\mathsf{cvd}}{2}+2}\cdot
n^{\mathcal{O}(1)}$ time.

###  4.3 Exponential Kernel for CnR by $\mathsf{dts}$

Using the ideas we presented in Section 4.2, we can also get a kernel for CnR
with respect to deletion to stars number. Let $U$ be a deletion to stars
vertex set of size $t$. Also, let $S=V(G)\setminus U$, and let $X_{1},\ldots
X_{\ell}$ be the stars in the graph $G[S]$. Specifically, we have the
following reduction rules along with reduction rule RR12.

######  Reduction Rule 15 (RR15).

Let $u$ and $v$ be two leaf vertices of some star $X$ in $G[S]$ such that
$N_{U}(u)\subseteq N_{U}(v)$. Then, delete $u$.

######  Reduction Rule 16 (RR16).

Let $X$ and $Y$ be two stars in $G[S]$ such that $V(X)=x,x_{1},\ldots,x_{p}$
and $V(Y)=y,y_{1},\ldots,y_{q}$, where $x$ and $y$ are center vertices of $X$
and $Y$, respectively. If $N_{U}(x)\subseteq N_{U}(y)$ and for each vertex
$x_{i}$ (for $i\in[p]$), there is a vertex $y_{j}$ (for $j\in[q]$) such that
$N_{U}(x_{i})\subseteq N_{U}(y_{j})$, then delete $X$.

The safeness of RR12 follows from Theorem 16. We have the following lemma,
which establishes that reduction rules RR15 and RR16 are safe.

######  Lemma 29.

Assuming $k>1$, reduction rules RR15 and RR16 are safe.

###### Proof.

To prove that rule RR15 is safe, it suffices to observe that for leaf vertices
$u$ and $v$ of some star $X\in S$, if $N_{U}(u)\subseteq N_{U}(v)$, then
$N(u)\subseteq N(v)$ in $G$. Indeed, the rest of the proof follows directly
from the proof of Lemma 23.

Next, we give a proof idea for the safeness of rule RR16. Here, we just define
the function of the image of the robber, and the rest of the proof is similar
to the proofs of Lemmas 23 and 26. For each vertex $u\notin V(X)$, $I(u)=u$.
For each $x_{i}$, $I(x_{i})=y_{j}$ such that $N_{U}(x_{i})\subseteq
N_{U}(y_{j})$ (there might be multiple choices for $y_{j}$ and we can choose
any one of them), and $I(x)=y$. ∎

Now, we claim that once we cannot apply rules RR15 and RR16 anymore, the size
of the graph is bounded by a function of $t$. First, we note that the size of
each star is at most $\frac{2^{t}}{\sqrt{t}}+1$ (by Proposition 24). Let $X$
and $Y$ be two stars in $G[S]$ such that $x$ and $y$ are the center vertices
of $X$ and $Y$, respectively. We say that $X$ and $Y$ have the same
neighbourhood type if $N_{U}(x)=N_{U}(y)$. Second, it is easy to see that
there can be at most $2^{t}$ neighbourhood types. Next, we bound the number of
stars in each neighbourhood type. Let $S_{1},\ldots,S_{z}$ be the stars having
the same neighbourhood type, and let $v_{i}$ be the center vertex of star
$S_{i}$. For each star $S_{i}$, for $i\in[z]$, let
$\mathcal{S}_{i}=\\{N(v):v\in V(S_{i})\setminus\\{v_{i}\\}\\}$. Since we have
applied reduction rule RR15 exhaustively, we know that for each
$A\in\mathcal{S}_{i}$, $A=N(v)$ for a unique vertex $v\in
V(S_{i})\setminus\\{v_{i}\\}$. Observe that each $S_{i}$ is a subset of the
power set of $U$ and the power set of $U$ has size $2^{t}$. Moreover, since we
have applied reduction rule RR16 exhaustively, we know that for any
$i,j\in[z]$, neither $\mathcal{S}_{i}\subseteq\mathcal{S}_{j}$ nor
$\mathcal{S}_{j}\subseteq\mathcal{S}_{i}$. Hence, due to Proposition 24,
$z\leq\frac{2^{2^{t}}}{\sqrt{2^{t}}}$. Therefore, the size of the reduced
graph can be at most $\frac{2^{2^{t}}}{\sqrt{2^{t}}}\cdot
2^{t}\cdot(\frac{2^{t}}{\sqrt{t}}+1)$. Thus, we have the desired kernel from
Theorem 6.

Since $k\leq\frac{t}{2}+1$ (by reduction rule RR12), applying the XP-algorithm
for CnR from Proposition 13 to the kernel in Theorem 6 gives us the following
corollary.

######  Corollary 30.

CnR is $\mathsf{FPT}$ parameterized by $\mathsf{dts}$. Specifically, it is
solvable in
$(\mathsf{dts}+2^{2^{\mathsf{dts}}+\mathsf{dts}^{1.5}})^{\frac{\mathsf{dts}}{2}+2}\cdot
n^{\mathcal{O}(1)}$ time.

###  4.4 Exponential Kernels for Different Variants

Here, we extend the result of Theorem 2 to several variations of the game. We
have the following results.

####  4.4.1 Lazy CnR and Cops and Attacking Robber:

First, we prove the following lemma.

######  Lemma 31.

Let $u$ and $v$ be two distinct vertices of $G$ such that $N(u)\subseteq
N(v)$. Consider the graph $H$ induced by $V(G)\setminus\\{u\\}$. Then for
$k>1$ and for $x\in\\{lazy,attack\\}$, $\mathsf{c}_{x}(G)\leq k$ if and only
if $\mathsf{c}_{x}(H)\leq k$.

###### Proof.

The proof for the forward direction ($c_{x}(G)\leq k$ implies $c_{x}(H)\leq
k$) is easy and follows from the arguments similar to the arguments in the
proof of Lemma 23. We prove the reverse side ($c_{x}(H)\leq k$ implies
$c_{x}(G)\leq k$) for both the variants below. Moreover, similarly to the
proof of Lemma 23, we define $I(u)=v$ and $I(x)=x$ when $x\neq u$. Similarly,
when $\small\mathcal{R}$ is at a vertex $x$, we say that the image of
$\small\mathcal{R}$ is at vertex $I(x)$. (Note that the image of
$\small\mathcal{R}$ is restricted to $H$.) In both of the variants, the cops
will play in $G$ to capture the image of the robber using the winning strategy
of $H$.

In Lazy CnR, the cops begin by capturing the image of $\small\mathcal{R}$ in
$G$. If $\small\mathcal{R}$ is at a vertex $x\neq u$, then $\small\mathcal{R}$
is captured. If $\small\mathcal{R}$ is at vertex $u$, then observe that there
is a cop, say, $\small\mathcal{C}$, at $v$ that has captured the image of
$\small\mathcal{R}$. Now, $\small\mathcal{C}$ ensures that $\small\mathcal{R}$
cannot move, and some other lazy cop can move to capture $\small\mathcal{R}$
in a finite number of rounds.

In Cops and Attacking Robber, the main observation is that if the cops can
capture $\small\mathcal{R}$ in $H$, they can capture the image of
$\small\mathcal{R}$ in $G$ without getting attacked by $\small\mathcal{R}$. If
$\small\mathcal{R}$ is at a vertex $x\neq u$ when the image of
$\small\mathcal{R}$ is captured, then $\small\mathcal{R}$ is captured.
Otherwise, $\small\mathcal{R}$ is at $u$, and a cop, say,
$\small\mathcal{C}_{1}$, is at vertex $v$. Now another cop, say,
$\small\mathcal{C}_{2}$, can move to a vertex $w\in N(v)$ (in a finite number
of steps) to capture $\small\mathcal{R}$. If $\small\mathcal{R}$ attacks
$\small\mathcal{C}_{2}$ at this point, then note that $\small\mathcal{C}_{1}$
can move to capture $\small\mathcal{R}$ in the next round. If
$\small\mathcal{R}$ does not attack, then $\small\mathcal{C}_{2}$ moves to
capture $\small\mathcal{R}$ in the next round. ∎

Lemma 31 establishes that reduction rule RR11 is safe for both Cops and
Attacking Robber and Lazy CnR. Before applying reduction rule RR11, we apply
the following reduction rules.

######  Reduction Rule 17 (RR17).

If $k\geq\frac{t}{2}+1$, then answer positively (Theorem 7).

######  Reduction Rule 18 (RR18).

If $k=1$, then apply the ${\mathcal{O}(n^{3})}$ time algorithm from
Proposition 14.

The size of the kernel, by using these reduction rules, is dependent on RR9.
Therefore, the proof of the existence of the desired kernel from Theorem 8
follows directly.

Moreover, Theorem 8, along with the XP-algorithms from Proposition 14 for
these variants, gives the following immediate corollary.

######  Corollary 32.

Cops and Attacking Robber and Lazy CnR are $\mathsf{FPT}$ parameterized by
$\mathsf{vcn}$. Specifically, they are solvable in
$\mathsf{vcn}+\frac{2^{\mathsf{vcn}}}{\sqrt{\mathsf{vcn}}})^{\frac{\mathsf{vcn}}{2}+2}\cdot
n^{\mathcal{O}(1)}$ time.

####  4.4.2 CnR on Directed Graphs:

Next, we consider the game of CnR on oriented graphs. For a directed graph
$\overrightarrow{G}$ and a vertex $v\in V(\overrightarrow{G})$, let $N^{+}(v)$
and $N^{-}(v)$ denote the set of out-neighbors and in-neighbors of $v$,
respectively. We have the following lemma.

######  Lemma 33.

Let $u$ and $v$ be two distinct vertices of a strongly connected directed
graph $\overrightarrow{G}$ such that $N^{+}(u)\subseteq N^{+}(v)$ and
$N^{-}(u)\subseteq N^{-}(v)$. Let $\overrightarrow{H}$ be the graph induced by
$V(\overrightarrow{G})\setminus\\{u\\}$. Then, for $k>1$, $k$ cops have a
winning strategy in $\overrightarrow{H}$ if and only if $k$ cops have a
winning strategy in $\overrightarrow{G}$

###### Proof.

First, observe that $H$ is also strongly connected.

Second, let $k$ cops have a winning strategy in $\overrightarrow{G}$. Then,
the cops can use this winning strategy in $\overrightarrow{H}$, with the only
difference that whenever a cop, say, $\small\mathcal{C}$, has to move to $u$
in $\overrightarrow{G}$, $\small\mathcal{C}$ moves to $v$ in
$\overrightarrow{H}$ instead ($\small\mathcal{C}$ can do so because
$N^{-}(u)\subseteq N^{-}(v)$). Next, whenever $\small\mathcal{C}$ has to move
to a vertex, say, $w$, from $u$, in the strategy in $G$, then
$\small\mathcal{C}$ can move to $w$ from $v$ also (since $N^{+}(u)\subseteq
N^{+}(v)$). As $\small\mathcal{R}$ is restricted to $V(\overrightarrow{H})$ in
$\overrightarrow{G}$, cops will capture $\small\mathcal{R}$ using this
strategy in $\overrightarrow{H}$ as well.

Finally, let $k$ cops have a winning strategy in $\overrightarrow{H}$. We use
this strategy to get a winning strategy in $\overrightarrow{G}$ using $k$
cops. First, we define $I(x)=x$ for $x\neq u$ and $I(u)=v$. Since $I(x)$ is
restricted to $\overrightarrow{H}$, we use the winning strategy in
$\overrightarrow{H}$ to capture $I(x)$. At this point if $x\neq u$, then
$\small\mathcal{R}$ is captured. Else, $\small\mathcal{R}$ is at $u$ and one
of the cops, say, $\small\mathcal{C}_{1}$, is at $v$. Since $N^{+}(u)\subseteq
N^{+}(v)$, $\small\mathcal{R}$ cannot move as long as $\small\mathcal{C}_{1}$
occupies $v$. Since $\overrightarrow{G}$ is strongly connected, one of the
other cops, say, $\small\mathcal{C}_{2}$, can move to $u$ in a finite number
of rounds to capture $\small\mathcal{R}$. ∎

Let $G$ be a graph with a vertex cover $U$ of size $t$, and let
$I=V(G)\setminus U$. Let $\overrightarrow{G}$ be a strongly connected
orientation of $G$. We apply the following reduction rules.

######  Reduction Rule 19 (RR19).

If $k\geq t$, then answer positively.

######  Reduction Rule 20 (RR20).

If $k=1$, then apply the $\mathcal{O}(n^{3})$ time algorithm from Proposition
14 to check whether $\overrightarrow{G}$ is copwin.

######  Reduction Rule 21 (RR21).

If $u$ and $v$ are two distinct vertices in $I$ such that $N^{+}(u)\subseteq
N^{+}(v)$ and $N^{-}(u)\subseteq N^{-}(v)$, then delete $u$.

Safeness of reduction rules RR19 and RR21 follow from Theorem 7 and Lemma 33,
respectively. Now, we argue that once we cannot apply reduction rules
RR19-RR21, the size of $\overrightarrow{G}$ is bounded by a function of $t$.
Observe that each vertex $u$ in $I$ has a unique neighbourhood ($N^{+}(u)\cup
N^{-}(u)$) and there are three choices for a vertex $v\in U$ to appear in the
neighbourhood of a vertex $u\in I$, that is, either $v\in N^{+}(u)$, or $v\in
N^{-}(u)$, or $v\notin N^{+}(u)\cup N^{-}(u)$. Therefore, the total number of
possible vertices in $I$ are at most $3^{t}$. Thus, applying reduction rules
RR19-RR21, we get the desired kernel from Theorem 8.

Theorem 8, along with rule RR21 and Proposition 14, gives the following
corollary.

######  Corollary 34.

CnR on strongly connected directed graphs is $\mathsf{FPT}$ parameterized by
the vertex cover number $t$. In particular, it is solvable in
$(3^{t}+t)^{t+1}\cdot n^{\mathcal{O}(1)}$ time.

###  4.5 General Kernelization

In this section, we provide a general reduction rule that works for most
variants of CnR parameterized by the vertex cover number. Let $U$ be a vertex
cover of size $t$ in $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\in I\colon N(v)=S\\}$. Given an instance $((G,k),t)$, we
have the following reduction rule.

######  Reduction Rule 22 (RR22).

If there is an equivalence class $\mathcal{C}_{S}$ such that
$|\mathcal{C}_{S}|>k+1$, then keep only $k+1$ arbitrary vertices from
$\mathcal{C}_{S}$ in $G$, and delete the rest.

First, we present (informal) intuition why reduction rule RR22 is safe. Since
the neighbourhood of each vertex in $\mathcal{C}_{S}$ is the same, all of
these vertices are equivalent with respect to the movement rules in any of the
variants discussed. We keep $k+1$ copies of such vertices because, on a robber
move, there is at least one vertex that is not occupied by any cop. We refer
to such a vertex as a free vertex. Note that there might be multiple free
vertices. On a robber player’s turn, if $\small\mathcal{R}$ plans to move to a
vertex in $\mathcal{C}_{S}$, it can move to a free vertex. Moreover, if a fast
robber wants to use a vertex from $\mathcal{C}_{S}$ as an intermediate vertex,
it can use a free vertex for this purpose as well. We prove safeness for
individual variants later in this section.

Moreover, we have the following lemma that we will use later.

######  Lemma 35.

Let $G$ be a graph with a vertex cover $U$ of size $t$. After an exhaustive
application of reduction rules RR19 and RR22, the reduced graph has at most
$t+t\cdot 2^{t}$ vertices.

###### Proof.

There can be at most $2^{t}$ equivalence classes, and for each equivalence
class, we keep at most $k+1$ vertices in $I$. Due to rule RR19, we can assume
$k<t$. Thus, size of $I$ is at most $t\cdot 2^{t}$. The size of $G$ is,
therefore, at most $|U|+|I|\leq t+t\cdot 2^{t}$. ∎

####  4.5.1 Generalized CnR

In this section, we establish that RR22 is safe for Generalized CnR. We have
the following lemma to prove this claim.

######  Lemma 36.

Let $G$ be a graph with a vertex cover $U$ of size $t$. Let $\mathcal{C}_{S}$
(for $S\subseteq U$) be an equivalence class such that
$|\mathcal{C}_{S}|=\ell>k+1$. Moreover, let $H$ be a subgraph formed by
deleting an arbitrary vertex $v$ of $\mathcal{C}_{S}$ from $G$. Then,
$(G,\small\mathcal{C}_{1},\ldots,\small\mathcal{C}_{k},\small\mathcal{R})$ is
a Yes-instance if and only if
$(H,\small\mathcal{C}_{1},\ldots,\small\mathcal{C}_{k},\small\mathcal{R})$ is
a Yes-instance.

###### Proof.

Let $\mathcal{C}_{S}=\\{v_{1},\ldots,v_{\ell}\\}$. Without loss of generality,
let us assume that vertices $v_{1},\ldots v_{\ell-1}$ belong to the graph $H$,
and $v=v_{\ell}$. Since there are at most $k$ cops in the game and $\ell>k+1$,
at least one vertex of $v_{1},\ldots,v_{\ell-1}$ is not occupied by any cop.
We denote this vertex by $x$ ($x$ is dependent on the position of the cops and
may change during the course of the game). Moreover, here we modify the
definition of a safe vertex slightly: A vertex $y$ is safe if it is at a
distance at least $\lambda_{i}+1$ from $\small\mathcal{C}_{i}$, for $i\in[k]$.
Since each vertex in $\mathcal{C}_{S}$ has the same neighborhood, observe that
either each vertex in $\mathcal{C}_{S}$ not occupied by a cop is a safe vertex
or none of the vertices in $\mathcal{C}_{S}$ is safe. Moreover, for each
vertex $y\in V(G)\setminus\\{v\\}$, let $I(y)=y$ and $I(v)=x$. Note that for
each vertex $u$, $I(u)$ is restricted to vertices of $V(H)$, $N(u)=N(I(u))$,
and if $u$ is a safe vertex, then $I(u)$ is also a safe vertex. To ease the
presentation, instead of saying that the cops/robber has a winning strategy in
$(G,\small\mathcal{C}_{1},\ldots,\small\mathcal{C}_{k},\small\mathcal{R})$ (or
$(G,\small\mathcal{C}_{1},\ldots,\small\mathcal{C}_{k},\small\mathcal{R})$),
we will say that the cops/robber has a winning strategy in $G$ (or $H$).

First, let $\small\mathcal{R}$ has a winning strategy $\mathcal{S}$ in $G$. To
show that $\small\mathcal{R}$ has a winning strategy in $H$, we will prove a
slightly stronger statement that $\small\mathcal{R}$ has a winning strategy,
say, $\mathcal{S}^{\prime}$, in $G$ even if $\small\mathcal{R}$ is restricted
to the vertices of $V(H)$ in $G$. We get $\mathcal{S}^{\prime}$ from
$\mathcal{S}$ as follows: If $\small\mathcal{R}$ has to use a vertex $y$ in
$\mathcal{S}$ in some move during the game, it uses $I(y)$ instead. We first
show that $\small\mathcal{R}$ can safely enter the graph. Let $y$ be the
vertex $\small\mathcal{R}$ enters in the strategy $\mathcal{S}$. Then,
$\small\mathcal{R}$ enters at $I(y)$ in $\mathcal{S}^{\prime}$. Since $y$ is a
safe vertex (as $\mathcal{S}$ is a winning strategy for $\small\mathcal{R}$),
$I(y)$ is also a safe vertex. Hence $\small\mathcal{R}$ can safely enter a
vertex. Now, the only thing to argue is that if $\small\mathcal{R}$ can move
safely from a vertex $y$ to a vertex $z$ in $G$, then it can safely move from
vertex $I(y)$ to $I(z)$ in $G$. Let $\small\mathcal{R}$ moves from $y$ to $z$
using a path $P_{1}=(y=y_{1},\ldots,y_{r}=z)$, where $r\in[s_{R}]$, during
some move in $\mathcal{S}$. Notice that since $\mathcal{S}$ is a winning
strategy, each vertex $y_{i}$ ($i\in[r]$) is a safe vertex, and hence, each
vertex $I(y_{i})$ is also a safe vertex. Moreover, since
$N(y_{i})=N(I(y_{i}))$, $W=(I(y_{1}),\ldots,I(y_{r}))$ is a walk with at most
$r$ vertices between $I(y)$ and $I(z)$. (It might not be a path since vertex
$x$ may repeat in this walk.) Since the existence of a walk between two
vertices implies the existence of a path between these vertices using vertices
from a subset of the walk vertices, we have an $I(y),I(z)$-path of length at
most $r$ using (safe) vertices from $\\{I(y_{1}),\ldots,I(y_{r})\\}$. Hence
$\small\mathcal{R}$ can safely move from $I(y)$ to $I(z)$. Thus,
$\mathcal{S}^{\prime}$ is a winning strategy for $\small\mathcal{R}$ even when
$\small\mathcal{R}$ is restricted to vertices of $V(H)$ in $G$.

In the reverse direction, let $\small\mathcal{R}$ has a winning strategy in
$H$. Then, we show that $\small\mathcal{R}$ has a winning strategy in $G$ as
well. Here, whenever a cop $\small\mathcal{C}_{i}$ moves to a vertex $y$,
$\small\mathcal{R}$ assumes its image at the vertex $I(y)$. Observe that
$I(y)$ is restricted to $V(H)$ in $G$. Let $y_{1},\ldots,y_{k}$ be the
vertices occupied by cops during some instance in the game. Let $F$ be the set
of vertices in $V(H)$ that are safe during this turn. Moreover, let
$F^{\prime}$ be the set of the vertices in $V(H)$ that are safe if cops are
occupying the vertices $I(y_{1}),\ldots,I(y_{k})$. Then, we have the following
claim.

######  Claim 37.

$F^{\prime}\subseteq F$.

###### Proof of Claim.

Targetting contradiction, assume that $y\in F^{\prime}$ but $y\notin F$. Then,
there exists some $i\in[k]$ such that $d(y,y_{i})\leq\lambda_{i}$ but
$d(y,I(y_{i}))>\lambda_{i}$. If $y_{i}\neq v$, then this is not possible since
for $y_{i}\neq v$, $I(y_{i})=y_{i}$. Hence, we can assume that $y_{i}=v$ and
$I(y_{i})=x$. Since $N(v)=N(x)$, for each vertex $y$ in $V(G)\setminus\\{v\\}$
(and $y\in F^{\prime}\subseteq V(H)$), $d(y,x)\leq d(y,v)$, that is,
$d(y,I(y_{i}))\leq d(y,y_{i})$, a contradiction.

We note that it might not be true that $F\subseteq F^{\prime}$, as it might so
happen that $F$ contains the vertex $x$, but $F^{\prime}$ does not. ∎

Due to Claim 37, it is sufficent to show that if $\small\mathcal{R}$ has a
winning strategy in $H$ considering the image of cop $\small\mathcal{C}_{i}$
as a cop with the capabilities of $\small\mathcal{C}_{i}$, then
$\small\mathcal{R}$ has a winning strategy in $G$. To this end,
$\small\mathcal{R}$ can use its winning strategy from $H$ since images of the
cops are restricted to $V(H)$. Thus, $\small\mathcal{R}$ has a winning
strategy in $G$.

Finally, note that, in both directions of proofs, $\small\mathcal{R}$ moves in
$H$ (respectively, in $G$) if and only if $\small\mathcal{R}$ moves in $G$
(respectively, in $H$). Hence, if $\small\mathcal{R}$ is active/flexible in
the original strategy, $\small\mathcal{R}$ is active/flexible in the designed
strategy. This completes the proof. ∎

Observe that $\mathsf{vcn}+1$ cops always have a winning strategy in $G$.
Therefore, we have the following theorem as a consequence of Lemma 36 and
Lemma 35.

See 9

Theorem 9 directly implies the existence of the desired kernel for Fully
Active CnR and Cops and Fast Robber from Theorem 10. The existence of the
desired kernel for Surrounding CnR from Theorem 10 follows from Lemma 35 and
the following lemma, which proves the safeness of RR22 for Surrounding CnR.

######  Lemma 38.

Let $G$ be a graph with a vertex cover $U$ of size $t$. Let $\mathcal{C}_{S}$
(for $S\subseteq U$) be an equivalence class such that
$|\mathcal{C}_{S}|=\ell>k+1$. For a subgraph $H$ formed by deleting $\ell-k-1$
arbitrary vertices of $\mathcal{C}_{S}$ from $G$,
$\mathsf{c}_{surround}(H)\leq k$ if and only if $\mathsf{c}_{surround}(G)\leq
k$.

###### Proof.

Let $\mathcal{C}_{S}=\\{v_{1},\ldots,v_{\ell}\\}$. Without loss of generality,
let us assume that the vertices $v_{1},\ldots v_{k+1}$ belong to the graph $H$
and vertices $v_{k+2},\ldots,v_{\ell}$ are deleted. We begin by noting that
$\small\mathcal{R}$ cannot be surrounded at a vertex in $S$ in $G$ (since each
vertex in $S$ has at least $k+1$ neighbours). Therefore, throughout the proof,
we have the implicit assumption that when $\small\mathcal{R}$ is surrounded,
it is not on a vertex in $S$.

Let $k$ cops have a winning strategy in $G$. Then, to surround
$\small\mathcal{R}$, cops use this strategy with the following changes in $H$.
Whenever a cop has to move to a vertex in $\\{v_{k+2},\ldots,v_{\ell}\\}$, it
moves to vertex $v_{1}$ instead. Since all vertices in $\mathcal{C}_{S}$ have
the same neighbourhood, the next move of this cop can be the same as it was in
(the winning strategy of) $G$. Note that using this strategy, the cops can
surround the robber in $G$ if $\small\mathcal{R}$ is restricted to $V(H)$ in
$G$, and also the moves of cops are restricted to $V(H)$ in $G$. Therefore,
the cops can surround $\small\mathcal{R}$ using this strategy in $H$ as well.

Now, let $k$ cops have a winning strategy in $H$. We use this strategy to
surround $\small\mathcal{R}$ in $G$, in the following manner. Since we have
only $k$ cops, during any time in the gameplay, there is at least one vertex
in $\\{v_{1},\ldots,v_{k+1}\\}$ that is not occupied by any cop. Let us call
this vertex a free vertex (there might be multiple free vertices). Again we
use the concept of the image of the robber. For each vertex $x\in V(G)$, if
$x\in V(H)$, then we define $I(x)=x$; else, if $x\in\\{v_{k+1},\ldots
v_{\ell}\\}$, then we define $I(x)=y$, where $y$ is a free vertex at that
instance. Whenever $\small\mathcal{R}$ moves to a vertex $x\in V(G)$, we say
that the image of the robber moves to $I(x)$. Moreover, we remind that, in
this game, although some cop and $\small\mathcal{R}$ can be at the same
vertex, the robber cannot end its move at the same vertex as one of the cops.
Cops use this capability to force $\small\mathcal{R}$ to move from a vertex.
Therefore, we also have to argue that whenever cops force $\small\mathcal{R}$
to move, they force the image of the robber to move as well. To this end,
observe that the image of the robber and the robber are on different vertices
only if $\small\mathcal{R}$ is on some vertex
$x\in\\{v_{k+1},\ldots,v_{\ell}\\}$ and the image of the robber is on a free
vertex, say, $y$. Notice that if, in the strategy for $H$, $\small\mathcal{R}$
was occupying $y$ and the cop player wants to force $\small\mathcal{R}$ to
move out of $y$, then it does so by moving a cop, say, $\small\mathcal{C}$,
from a vertex $w\in N(y)$ to $y$. Cop player adapts this strategy in $G$ by
moving $\small\mathcal{C}$ form $w$ to $x$ instead of $w$ to $y$. This move is
possible because $N(x)=N(y)$. Thus, $\small\mathcal{R}$, as well as the image
of $\small\mathcal{R}$, are forced to move as they would have been forced to
move in the winning strategy of $k$ cops in $H$.

Hence, the image of $\small\mathcal{R}$ is restricted to $V(H)$ in $G$ and has
to follow the rules of the movement of the robber. Thus, the cops will finally
surround the image of $\small\mathcal{R}$ in $G$. At this point, if
$\small\mathcal{R}$ is on a vertex $v\in\\{v_{k+2},\ldots,v_{\ell}\\}$, note
that $I(\small\mathcal{R})$ is on a vertex $u\in\\{v_{1},\ldots,v_{k+1}\\}$.
Observe that here, if $I(\small\mathcal{R})$ is surrounded, then there is a
cop on each vertex in $S$, and thus, $\small\mathcal{R}$ is surrounded as
well. If $\small\mathcal{R}$ was on a vertex in $V(H)\setminus S$ when
surrounded, then $I(\small\mathcal{R})$ and $\small\mathcal{R}$ are at the
same vertex, and thus, $\small\mathcal{R}$ is surrounded as well. ∎

This finishes the proof of Theorem 10. The following corollary is a direct
consequence of Theorem 7, Theorem 10, Theorem 9, and Proposition 14.

######  Corollary 39.

Cops and Fast Robber, Fully Active CnR, Surrounding CnR, and Generalized CnR
are $\mathsf{FPT}$ prameterized by $\mathsf{vcn}$. Specifically, each of these
variants is solvable in $(\mathsf{vcn}\cdot
2^{\mathsf{vcn}}+\mathsf{vcn})^{\mathsf{vcn}+1}\cdot n^{\mathcal{O}(1)}$ time.

##  5 Polynomial Kernels for CnR

In this section, we provide a linear kernel for CnR parameterized by the
neighbourhood diversity ($\mathsf{nd}$) of the input graph. One of the key
benefits of $\mathsf{nd}$ as a parameter is that it is computable in
polynomial time [56]. More specifically, in polynomial time, we can compute a
minimum partition of $V(G)$ into classes $V_{1},\ldots,V_{w}$ such that each
$V_{i}$ contains vertices of the same type. Hence, a linear kernel
parameterized by $\mathsf{nd}$ can be very useful from an applicative
perspective.

Since for any two vertices $u,v\in V_{i}$, for $i\in[w]$,
$N(v)\setminus\\{u\\}=N(v)\setminus\\{u\\}$, we have that either each $V_{i}$
is an independent set ($N(v)=N(u)$ in this case) or each $V_{i}$ is a clique
($N[v]=N[u]$ in this case). Now, we use the following reduction rules.

######  Reduction Rule 23 (RR23).

If $k\geq w$, then answer positively.

We have the following lemma to prove that RR23 is safe.

######  Lemma 40.

For a graph $G$, $\mathsf{c}(G)\leq\mathsf{nd}$.

###### Proof.

Let $S$ be a set of vertices such that $S$ contains exactly one vertex, say
$v_{i}$, from each neighbourhood class $V_{i}$. Then, (since we assume $G$ to
be connected) observe that $S$ is a dominating set of $G$. Hence, the cops
have a trivial winning strategy by placing a cop on each vertex of $S$ (and
$|S|\leq w$). Therefore, $\mathsf{c}(G)\leq\mathsf{nd}$. ∎

Next, if $k=1$, then we apply RR10 (the XP-algorithm for CnR from Proposition
13). Hence, we assume that $k\geq 2$. Next, we have the following reduction
rule.

######  Reduction Rule 24 (RR24).

For each neighbourhood class $V_{i}$, keep one arbitrary vertex and delete the
rest.

We have the following lemma to prove that RR24 is safe.

######  Lemma 41.

Let $V_{i}=\\{v_{1},\ldots,v_{\ell}\\}$ be a neighbourhood class of $G$ having
at least two vertices ($\ell\geq 2$). Consider the subgraph $H$ of $G$ induced
by $V(G)\setminus\\{v_{\ell}\\}$. Then, for $k>1$, $G$ is $k$-copwin if and
only if $H$ is $k$-copwin.

###### Proof.

We have the following two cases depending on whether $V_{i}$ is an independent
set or a clique.

  1. 1.

$V_{i}$ is an independent set: Note that, in this case,
$N(v_{\ell})=N(v_{1})$. Therefore, due to Lemma 23, we have that $G$ is
$k$-copwin if and only if $H$ is $k$-copwin.

  2. 2.

$V_{i}$ is a clique: Note that in this case, $N[v_{\ell}]=N[v_{1}]$. The
proof, in this case, (specifically the forward direction) follows from
arguments presented in the proof of Lemma 23. For the reverse direction, here
for $x\neq v_{\ell}$, $I(x)=x$ and $I(v_{\ell})=v_{1}$. Now, note that every
possible move of $\small\mathcal{R}$ in $G$ can be mapped to a valid move of
the image of the robber in $H$, just like in the proof of Lemma 23. The only
difference here is that when $\small\mathcal{R}$ is at $v_{\ell}$ (image of
$\small\mathcal{R}$ is at $v_{1}$), $\small\mathcal{R}$ can move to $v_{1}$ as
well (along with vertices in $N(v_{1})$). Notice that this move can be
translated to the movement of the image of $\small\mathcal{R}$ in $H$ where
the image of $\small\mathcal{R}$ chooses to stay on the same vertex in its
move. Hence, the cops will first capture the image of $\small\mathcal{R}$ in
$H$, and then capture $\small\mathcal{R}$ in $G$.

This completes the proof of this lemma. ∎

Since we keep only one vertex of each type and there are at most $w$ types, we
have the following theorem.

See 5 We have the following corollary as a consequence of Theorem 5.

######  Corollary 42.

CnR is $\mathsf{FPT}$ parameterized by $\mathsf{nd}$. Specifically, it is
solvable in $\mathsf{nd}^{\mathsf{nd}}\cdot n^{\mathcal{O}(1)}$ time.

Moreover, it is not difficult to see that this kernelization can be extended
to Lazy CnR and Cops and Attacking Robber using an extension of Lemma 31,
giving us a kernel with at most $\mathsf{nd}$ vertices. Moreover, using a
reduction rule similar to RR22 where we keep $k$ vertices of each type, we can
have a kernel with at most $k\cdot\mathsf{nd}$ vertices for Cops and Fast
Robber and Fully Active CnR. We have the following lemma, for which we provide
a proof outline.

######  Lemma 43.

Let $V_{i}=\\{v_{1},\ldots,v_{\ell}\\}$ is a neighbourhood class of $G$
containing at least $k+2$ vertices $(\ell\geq k+2)$. Consider the subgraph of
$G$ induced by $V(G)\setminus\\{v_{\ell}\\}$. Then, for $k>1$, $s\geq 1$, and
$x\in\\{active,s\\}$, $\mathsf{c}_{x}(G)\leq k$ if and only if
$\mathsf{c}_{x}(H)\leq k$.

###### Proof Sketch.

Similar to the proof of Lemma 41, we have the following two cases depending on
whether $V_{i}$ is an independent set or a clique.

  1. 1.

$V_{i}$ is an independent set: Proof of this case follows from the proof of
Lemma 36.

  2. 2.

$V_{i}$ is a clique: Here, for each $v_{j}\in V_{i}$, $N[v_{j}]=N[v_{\ell}]$.
For each vertex $x\neq v_{\ell}$, let $I(x)=x$ and $I(v_{\ell})=v_{1}$.

First, let $\mathsf{c}_{x}(G)\leq k$. Then, we use the strategy of the cops
from $G$ to capture $\small\mathcal{R}$ in $H$ with the only change that
whenever a cop, say, $\small\mathcal{C}_{i}$, wants to move to a vertex $x$ in
$G$, it moves to $I(x)$ in $H$ instead with the only contingency that if
$\small\mathcal{C}_{i}$ wants to move from $v_{1}$ to $v_{\ell}$, then it
moves to $v_{2}$ (so that if the cops are active, then this is indeed a valid
move of $\small\mathcal{C}_{i}$ in $H$). Observe that the cops can capture
$\small\mathcal{R}$ in $G$ using this strategy even when the cops are
restricted to the vertices of $H$. Hence, the cops can capture
$\small\mathcal{R}$ using this strategy in $H$.

In the reverse direction, let $\mathsf{c}_{x}(H)\leq k$. Note that if $k$
active cops have a winning strategy against a flexible robber in $G$, then $k$
active cops have a winning strategy against an active robber in $G$ as well.
Hence, for the ease of arguments, we show that $k$ active cops have a winning
strategy in $G$ even if $\small\mathcal{R}$ is flexible to show that
$\mathsf{c}_{active}\leq k$. The cops assume that the image of
$\small\mathcal{R}$ is occupying the vertex $I(x)$ when $\small\mathcal{R}$ is
occupying the vertex $x$. Thus, we have an image of $\small\mathcal{R}$ moving
in $H$ with the same capabilities as $\small\mathcal{R}$. The cops will
capture the image of $\small\mathcal{R}$ using their winning strategy from
$H$. Notice that once the image of $\small\mathcal{R}$ is captured, if
$\small\mathcal{R}$ is at a vertex $x\neq v_{\ell}$, then $\small\mathcal{R}$
is captured as well. Otherwise, $\small\mathcal{R}$ is at $v_{\ell}$ and there
is some cop, say, $\small\mathcal{C}_{1}$, at $v_{1}$. In the case of Fully
Active CnR, $\small\mathcal{R}$ will be captured in the next move of cops
(since $v_{1}v_{\ell}\in E(G)$). In the case of Cops and Fast Robber, if this
is a cop move (that is, the image of $\small\mathcal{R}$ is captured on a
robber move), then $\small\mathcal{C}_{1}$ will capture $\small\mathcal{R}$ in
the next move. Otherwise, in the previous move of the cops,
$\small\mathcal{C}_{1}$ moved to $v_{1}$ while $\small\mathcal{R}$ was at
$v_{\ell}$. In this case, since $N[v_{1}]=N[v_{\ell}]$,
$\small\mathcal{C}_{1}$ could have moved to $v_{\ell}$ to capture
$\small\mathcal{R}$ itself. Hence, $\mathsf{c}_{x}(G)\leq k$.

This completes the proof. ∎

Since $\mathsf{c}(G)\leq\mathsf{nd}$ for all of these variants (as there is a
dominating set of size $\mathsf{nd}$ in $G$), we have the following result as
a consequence of Lemma 43 (and arguments presented above).

######  Theorem 44.

Lazy CnR and Cops and Attacking Robber parameterized by $\mathsf{nd}$ admit a
kernel with at most $\mathsf{nd}$ vertices. Moreover, Cops and Fast Robber and
Fully Active CnR parameterized by $\mathsf{nd}$ admit a kernel with at most
$\mathsf{nd}^{2}$ vertices.

Finally, we remark that this technique of kernelization will not work directly
for Surrounding CnR. For example, consider a complete graph on $n$ vertices,
for which $\mathsf{nd}=1$ (all the vertices have the same type) and
$\mathsf{c}_{surround}=n$, and if we remove any vertex from this clique,
$\mathsf{c}_{surround}$ decreases. Moreover, as evident from our example of
complete graphs, $\mathsf{c}_{surround}$ cannot be bounded by any computable
function that depends only on $\mathsf{nd}$.

##  6 Incompressibility

###  6.1 Incompressibility of CnR

In this section, we show that it is unlikely that the CnR problem
parameterized by $\mathsf{vcn}$ admits a polynomial compression. For this
purpose, we first define the following problem. In Red-Blue Dominating Set, we
are given a bipartite graph $G$ with a vertex bipartition $V(G)=T\cup N$ and a
non-negative integer $k$. A set of vertices $N^{\prime}\subseteq N$ is said to
be an RBDS if each vertex in $T$ has a neighbour in $N^{\prime}$. The aim of
Red-Blue Dominating Set is to decide whether there exists an RBDS of size at
most $k$ in $G$. Accordingly, we have the following decision version of Red-
Blue Dominating Set.

Red-Blue Dominating Set Input: A bipartite graph $G$ with vertex bipartition
$V(G)=T\cup N$, and a non-negative integer $k$. Question: Does $G$ has an RBDS
of size at most $k$?
---

Dom, Lokshtanov, and Saurabh [32] proved that it is unlikely for Red-Blue
Dominating Set parameterized by $|T|+k$ to admit a polynomial compression.
More precisely, they proved the following result.

######  Proposition 45 ([32]).

Red-Blue Dominating Set parameterized by $|T|+k$ does not admit a polynomial
compression, unless NP $\subseteq$ coNP$/$poly.

We show that CnR parameterized by the $\mathsf{vcn}$ does not have a
polynomial compression by developing a polynomial parameter transformation
from Red-Blue Dominating Set parameterized by $|T|+k$ to CnR parameterized by
$\mathsf{vcn}$.

####  6.1.1 Bipartite Graphs with Large Degree and Girth

For our reduction, we borrow a construction by Fomin at al. [36] of bipartite
graphs having high girth and high minimum degree, which they used to prove NP-
hardness (and $W[2]$-hardness for the solution size $k$) of CnR. For positive
integers $p,q$, and $r$, we can construct a bipartite graph $H(p,q,r)$ with
$rqp^{2}$ edges and a bipartition $(X,Y)$, with $|X|=|Y|=pq$. The set $X$ is
partitioned into sets $U_{1},\ldots,U_{p}$, and the set $Y$ is partitioned
into sets $W_{1},\ldots W_{p}$, with $|U_{i}|=|W_{i}|=q$. By $H_{i,j}$ we
denote the subgraph of $H(p,q,r)$ induced by $U_{i}\cup W_{j}$, and by
$\mathsf{deg}_{i,j}(z)$ we denote the degree of vertex $z$ in $H_{i,j}$. Fomin
et al. [36] provided the following construction:

######  Proposition 46 ([36]).

Let $q\geq 2p(r+1)\frac{(p(r+1)-1)^{6}-1}{(p(r+1)-1)^{2}-1}$. Then, we can
construct $H(p,q,r)$ in time $\mathcal{O}(r\cdot q\cdot p^{2})$ with the
following properties.

  1. 1.

The girth of $H(p,q,r)$ is at least 6.

  2. 2.

For every vertex $z\in V(H_{i,j})$ and every $i,j\in[p]$, we have
$r-1\leq\mathsf{deg}_{i,j}(z)\leq r+1$.

####  6.1.2 Polynomial Parameter Transformation

Suppose that we are given an instance $(G,k)$ with $V(G)=T\cup N$ of the Red-
Blue Dominating Set problem. First, we construct a graph $G^{\prime}$ with
$V(G^{\prime})=T^{\prime}\cup N^{\prime}$ from $G$ by introducing two new
vertices, $x$ and $y$, such that $T^{\prime}=T\cup\\{x\\}$ and
$N^{\prime}=N\cup\\{y\\}$, and $E(G^{\prime})=E(G)\cup\\{xy\\}$. We have the
following observation.

######  Observation 47.

$G$ has an RBDS of size at most $k$ if and only if $G^{\prime}$ has an RBDS of
size at most $k+1$. Moreover, any RBDS of $G^{\prime}$ contains $y$.

Now, we present the main construction for our reduction. Denote the vertex set
$V(T^{\prime})$ by $\\{v_{1},v_{2},\ldots,v_{p^{\prime}},x\\}$. Moreover, let
$p=p^{\prime}+1$, $\ell=k+1$, $r=\ell+2$, and $q=\lceil
2p(r+1)\frac{(p(r+1)-1)^{6}-1}{(p(r+1)-1)^{2}-1}\rceil$.

We construct $H(p,q,r)$ such that each of $U_{i}$ and $W_{i}$, for $0<i\leq
p^{\prime}$, contains $q$ copies of vertex $v_{i}$, and each of $U_{p}$ and
$W_{p}$ contains $q$ copies of vertex $x$. Now, we obtain a graph
$G^{\prime\prime}$ by adding one more set of vertices $P$ to $H(p,q,r)$ such
that $V(P)=V(N^{\prime})$. Moreover, if there is an edge between a vertex
$u\in N^{\prime}$ and a vertex $v_{i}\in T^{\prime}$, then we add an edge
between $u$ and every vertex of $U_{i}$, and also between $u$ and every vertex
of $W_{i}$. Similarly, we add an edge between $y$ and every vertex of $U_{p}$,
and between $y$ and every vertex of $W_{p}$. Finally, we make the vertex $y$
adjacent to every vertex of $P$. See Figure 3 for reference.

For correctness, we have the following lemma.

Figure 3: Illustration for $H(p,q,r)$ and $P$. If a vertex $u$ is connected to
$v_{j}$ in $G$, then here $u$ is connected to every vertex of $W_{j}$ and
$U_{j}$. Moreover, for every $i,j$, each vertex in $U_{i}$ has at least $r-1$
neighbors in $U_{j}$.

######  Lemma 48.

$G^{\prime}$ has an RBDS of size at most $\ell$ if and only if
$G^{\prime\prime}$ is $\ell$-copwin.

###### Proof.

First, we show that if $G^{\prime}$ has an RBDS of size $\ell$, then $\ell$
cops have a winning strategy in $G^{\prime\prime}$. Let $S\subseteq
N^{\prime}$ be an RBDS in $G^{\prime}$ of size at most $\ell$. The cops begin
by choosing the vertices corresponding to $S$ in $P$. Observe that the vertex
$y$ has to be present in $S$. Since vertex $y$ dominates each vertex in $P$,
the robber cannot safely enter a vertex in $P$. Additionally, due to the
construction of $G^{\prime\prime}$, the vertices of $S$ dominate each vertex
in $H$. Hence, the robber cannot safely enter a vertex in $H$. Therefore, the
robber will be captured in the first move of the cops.

Next, we show that if there is no RBDS of size $\ell$ in $G^{\prime}$, then
$\ell$ cops do not have a winning strategy. We prove this by giving a winning
strategy for the robber. First, we show that the robber can safely enter the
graph. In the beginning, let there be $\ell_{1}\leq\ell$ cops in $P$ and
$\ell_{2}\leq\ell$ cops in $H$. Since there is no RBDS of size $\ell$ in
$G^{\prime}$, for every placement of at most $\ell$ cops in $P$, there exists
at least one pair of $U_{i}$ and $W_{i}$ such that no vertex of $U_{i}$ and
$W_{i}$ is dominated by the cops from $P$. Let $U_{i}$ and $W_{i}$ be one such
pair of sets such that no vertex of $U_{i}$ and $W_{i}$ is dominated by the
cops from $P$. Moreover, since each vertex of $H$ can dominate at most
$p(r+1)$ vertices in $H$, $\ell_{2}$ cops can dominate at most $\ell\cdot
p(r+1)$ vertices. Since $U_{i}$ (and $W_{i}$ also) contains $q$ vertices, and
$q>\ell\cdot p(r+1)$, the $\ell_{2}$ cops in $H$ cannot dominate all vertices
of $U_{i}$, and hence the robber can safely enter a vertex of $U_{i}$.

Now, whenever the robber is under attack, it does the following. Without loss
of generality, let us assume that the robber is in $U_{i}$ (the case of
$W_{i}$ is symmetric). Since there are at most $\ell$ cops in $P$, there is
always a $W_{j}$ such that no vertex of $W_{j}$ is dominated by cops from $P$.
Since each vertex in $U_{i}$ has at least $r-1=\ell+1$ neighbours in $W_{j}$,
the robber can move to at least $\ell+1$ vertices of $W_{j}$. Since the girth
of $H$ is at least 6, no vertex from $H$ can dominate two vertices of $W_{j}$
that are adjacent to the robber; else, we get a cycle on four vertices. Hence,
at most $\ell$ cops from $H$ can dominate at most $\ell$ neighbors of the
robber in $W_{j}$, and the robber has at least $\ell+1$ neighbors in $W_{j}$.
Hence, the robber can move to a safe vertex in $W_{j}$. Since the graph $H$ is
symmetric, the robber can move safely from $W_{j^{\prime}}$ to
$W_{i^{\prime}}$ also. The robber follows this strategy to avoid capture
forever.

This completes the proof of our lemma. ∎

Next, we have the following observation to show that there exists a vertex
cover $U$ of $G^{\prime\prime}$ such that $|U|=poly(|T|,k)$.

######  Observation 49.

$V(H)\cup\\{y\\}$ is a vertex cover of $G^{\prime\prime}$. Therefore, the
vertex cover number of $G^{\prime\prime}$ is at most $2\cdot p\cdot
q+1=1+2p\cdot\lceil 2p(k+3)\frac{(p(k+3)-1)^{6}-1}{(p(k+3)-1)^{2}-1}\rceil$,
where $p=|T|+1$.

This completes the proof of the argument that CnR parameterized by the
$\mathsf{vcn}$ is unlikely to admit a polynomial compression. Thus, we have
the following theorem as a consequence of Lemma 48, Observation 49 and
Proposition 45.

See 4

We prove the incompressibility of the variants (Theorem 11) in the Appendix.

###  6.2 Incompressibility for Variants

In this section, we prove Theorem 11. In Theorem 4, we proved that it is
unlikely for CnR to admit a polynomial compression. For this purpose, we
constructed a graph $G^{\prime\prime}$ where $k$ cops have a winning strategy
if and only if the graph $G^{\prime}$ has an $RBDS$ of size at most $k$. If
$G^{\prime}$ has an $RBDS$ of size $k$, then there is a dominating set of size
$k$ in $G^{\prime\prime}$. Else, there is no winning strategy for $k$ cops in
$G^{\prime\prime}$. Here, we use the same construction to show that the
variants we study (except for Surrounding CnR) are unlikely to admit a
polynomial compression parameterized by $\mathsf{vcn}$. We establish this by
proving that $G^{\prime\prime}$ is $k$-copwin for these variants if and only
if $G^{\prime}$ has an $RBDS$ of size at most $k$.

As discussed earlier, for a graph $G$,
$\mathsf{c}(G)\leq\mathsf{c}_{lazy}(G)$,
$\mathsf{c}(G)\leq\mathsf{c}_{attacking}(G)$, and
$\mathsf{c}(G)\leq\mathsf{c}_{s}(G)$ (for any $s\geq 1$). Therefore, if $G$
does not have an $RBDS$ of size at most $k$, then $\mathsf{c}(G)>k$, and
hence, $\mathsf{c}_{lazy}(G)>k$, $\mathsf{c}_{attacking}(G)>k$, and
$\mathsf{c}_{s}(G)>k$ (for $k>0$). To see the reverse direction, observe that
in each of these three variants, if the cops start by occupying a dominating
set, then they win in the next round. Hence, this establishes that it is
unlikely for Cops and Attacking Robber, Cops and Fast Robber, Lazy CnR
parameterized by $\mathsf{vcn}$ to admit to admit a polynomial compression.

Similarly, it is true for Fully Active CnR also, that if the cops start by
occupying a dominating set, then they win in the next round. Hence, we have to
only show that if there is no $RBDS$ of size $k$ in $G^{\prime}$ (and hence,
no dominating set of size $k$ in $G^{\prime\prime}$), then $k$ cops do not
have a winning strategy in $G$ for Fully Active CnR. The robber uses the
following strategy. When $\small\mathcal{R}$ is under attack, it follows the
strategy from Cops and Robber. Now, $\small\mathcal{R}$ is forced to move
(because it is active) even when it is on a safe vertex. Note that
$\small\mathcal{R}$ always stays in $H(p,q,r)$. Due to symmetry, let us assume
it is in some vertex $v$ in some block $U_{i}$. In this case,
$\small\mathcal{R}$ can simply move to a vertex in $W_{i}$. Observe here that
since vertices in $U_{i}$ are safe, the vertices in $W_{i}$ are also safe.

Thus, we have the following lemma to establish that these variants are
unlikely to admit a polynomial compression.

Figure 4: Illustration for $H(p,q,r)$ and $P$. If a vertex $u$ is connected to
$v_{j}$ in $G$, then for every vertex $v\in W_{j}\cup X_{j}\cup U_{j}$, we
orient the arc $\overrightarrow{uv}$. For each vertex $v\in
V(P)\setminus\\{y\\}$, we orient the arc $\overrightarrow{yv}$. We add a
vertex $z$, and arcs $\overrightarrow{zy}$ and $\overrightarrow{xz}$ for each
$x\in U_{p}\cup X_{p}\cup W_{P}$.

######  Lemma 50.

Lazy CnR, Cops and Attacking Robber, Cops and Fast Robber, and Fully Active
CnR parameterized by the vertex cover number do not admit a polynomial
compression, unless NP $\subseteq$ coNP$/$poly.

This result can also be extended to directed (or oriented) graphs. We have the
following lemma.

######  Lemma 51.

CnR on strongly connected directed and oriented graphs parameterized by vertex
cover number does not admit a polynomial compression, unless NP $\subseteq$
coNP$/$poly.

###### Proof.

For the case of directed graphs, we can simply replace each edge in the
construction with a loop edge (directed cycle on two vertices).

To prove this result for oriented graphs, we do the following. Here, we change
the underlying graph $G^{\prime\prime}$. First, instead of having two
partitions $U$ and $W$, we have three partitions $U,W$, and $X$ (with the same
rules). See Figure 4 for an illustration. Second, we add edges between $U$ and
$W$, $W$ and $X$, and $X$ and $U$ following the rules of the construction.
Moreover, the edge rules for vertices in $P$ are the same (that is, if a
vertex has edges with each vertex in some $U_{i}$, it has edges with each
vertex in $W_{i}$ and $X_{i}$ as well). Next, we define orientations. For the
vertex $y$, we orient all the edges as outgoing. For every vertex $u\in
P\setminus\\{y\\}$, we mark all the edges as outgoing, except for the edge
$uy$ (which is oriented $\overrightarrow{yu}$). For each edge $uv$ such that
$u\in U$ and $w\in W$, orient the edge $\overrightarrow{uw}$. For every edge
$wx$ such that $w\in W$ and $x\in X$, orient the edge $\overrightarrow{wx}$.
For each edge $xu$ such that $x\in X$ and $u\in U$, orient the edge
$\overrightarrow{xu}$. Finally, add an extra vertex $z$, and add arc
$\overrightarrow{zy}$. Moreover, for each vertex $v\in U_{p}\cup W_{p}\cup
X_{p}$, add an arc $\overrightarrow{vz}$.

It is straightforward to see that $\overrightarrow{G^{\prime\prime}}$ is a
strongly connected oriented graph. Moreover, if $G^{\prime\prime}$ has a
dominating set of size $k$, then $k$ cops have a winning strategy by occupying
these vertices in $\overrightarrow{G^{\prime\prime}}$. Observe that, at this
point, $\small\mathcal{R}$ can enter only at vertex $z$ and cannot move as
long as there is a cop, say, $\small\mathcal{C}_{1}$, at $y$ (which there is
due to the construction of $G^{\prime}$ and $G^{\prime\prime}$). Now, since
$\overrightarrow{G^{\prime\prime}}$ is strongly connected, some other cop,
say, $\small\mathcal{C}_{2}$, can move to capture $\small\mathcal{R}$ in a
finite number of rounds. For the reverse direction, if $G^{\prime}$ does not
have an $RBDS$ of size $k$ (and hence $G^{\prime\prime}$ does not have a
dominating set of size $k$), then following the arguments of Lemma 48,
$\small\mathcal{R}$ can enter at a safe vertex in $U$. Then, whenever
$\small\mathcal{R}$ is under attack, it can move to a safe vertex in $W$.
Similarly, it can move from $W$ to $X$ and from $X$ to $U$ when under attack.
Moreover, note that vertex $z$ does not attack any vertex in $U\cup W\cup X$.
Hence, $\small\mathcal{R}$ has a clear evading strategy.

This completes our proof. ∎

Lemma 50 and Lemma 51 directly imply Theorem 11.

##  7 Conclusion and Future Directions

In this paper, we conducted a comprehensive analysis of the parameterized
complexity of CnR parameterized by $\mathsf{vcn}$. First, we showed that the
cop number of a graph is upper bounded by $\frac{\mathsf{vcn}}{3}+1$. Second,
we proved that CnR parameterized by $\mathsf{vcn}$ is $\mathsf{FPT}$ by
designing an exponential kernel. We complemented this result by proving that
it is unlikely for CnR parameterized by $\mathsf{vcn}$ to admit a polynomial
compression. We then extended these results to other variants as well as to
other parameters.

To achieve our kernelization results, the rules we used concerned removing
(false or true) twins from the graph. These rules are easy to implement and
hence can be used to reduce the complexity of the input graph, even when the
input graph is far from the considered parameters. For example, for cographs,
none of the considered parameters is constant/bounded, but cographs can be
reduced to a single vertex with the operation of removing twins, and hence,
our reduction rules give an alternate proof that the cop number of cographs is
at most two [53] for several variants. Moreover, MTP is well-studied with the
motivation of designing computer games. Some examples of these variants
include: multiple targets and multiple pursuer search [81] with applications
in controlling non-player characters in video games; MTP from the robber’s
perspective with faster cops [61] where the strategies were tested on Baldur’s
Gate; MTP modeled with edge weights and different speeds of agents [50] with
the specific examples of Company of Heroes and Supreme Commander. Moreover,
the PACMAN game’s movement can be considered as an instance of Fully Active
CnR on a partial grid. One of the key aspects of designing these games is to
come up with scenarios that are solvable but look complex and challenging. Our
reduction rule can help in this regard. One can begin with an easy-to-resolve
instance of CnR, and then keep adding twins to this instance (recursively) to
get an instance that looks sufficiently complex but has the same complexity.

Finally, we defined a new variant of CnR, named Generalized CnR, that
generalizes many well-studied variants of CnR including Cops and Fast Robber,
Fully Active CnR, Cops and Robber From a Distance [14], and also generalizes
the games of [61, 50]. We showed that RR22 provides a kernel for Generalized
CnR as well. This gives hope that RR22 can be used to get kernels for many
practical variants not explicitly studied in this paper.

Still, many questions on the parameterized complexity of CnR remain open. We
list some of these questions below.

######  Question 52.

Does there exist an $\mathsf{FPT}$ algorithm for CnR parameterized by
$\mathsf{vcn}$ with running time $2^{\mathcal{O}(\mathsf{vcn})}\cdot
n^{\mathcal{O}(1)}$?

######  Question 53.

Does there exist a better bound for the cop number with respect to
$\mathsf{vcn}$? In particular, is $\mathsf{c}(G)=o(\mathsf{vcn})$?

######  Question 54.

Does CnR parameterized by $\mathsf{vcn}$ admit a polynomial
$\alpha$-approximate kernel?

######  Question 55.

Study CnR with respect to the following parameters: (1) feedback vertex set
(2) treewidth (3) treedepth. In particular, is CnR $\mathsf{FPT}$
parameterized by treewidth?

## References

  * [1] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  SIAM Journal on Computing, 48(3):1120–1145, 2019.  doi:10.1137/17M1112406.
  * [2] I. Adler.  Marshals, monotone marshals, and hypertree-width.  Journal of Graph Theory, 47(4):275–296, 2004.
  * [3] M. Aigner and M. Fromme.  A game of cops and robbers.  Discrete Applied Mathematics, 8(1):1–12, 1984.
  * [4] T. Andreae.  On a pursuit game played on graphs for which a minor is excluded.  Journal of Combinatorial Theory Series B, 41(1):37–47, 1986.
  * [5] D. Angelo, A. Navarra, and N. Nisse.  A unified approach for gathering and exclusive searching on rings under weak assumptions.  Distributed Computing, 30:17–48, 2017.
  * [6] J. A. Baier, A. Botea, D. Harabor, and C. Hernández.  Fast algorithm for catching a prey quickly in known and partially known game maps.  IEEE Transactions on Computational Intelligence and AI in Games, 7(2):193–199, 2015.  doi:10.1109/TCIAIG.2014.2337889.
  * [7] W. Baird and A. Bonato.  Meyniel’s conjecture on the cop number: A survey.  Journal of Combinatorics, 3(2):225–238, 2013.
  * [8] D. Bal, A. Bonato, W. B. Kinnersley, and P. Prałat.  Lazy cops and robbers played on random graphs and graphs on surfaces.  Journal of Combinatorics, 7(4):627–642, 2016.
  * [9] P. Balister, B. Bollobás, B. Narayanan, and A. Shaw.  Catching a fast robber on the grid.  Journal of Combinatorial Theory Series A, 152:341–352, 2017.
  * [10] A. Berarducci and B. Intrigila.  On the cop number of a graph.  Advances in Applied mathematics, 14(4):389–403, 1993.
  * [11] A. Beveridge, A. Dudek, A. Frieze, and T. Müller.  Cops and robbers on geometric graphs.  Combinatorics, Probability and Computing, 21(6):816–834, 2012.
  * [12] B. Bollobás, G. Kun, and I. Leader.  Cops and robbers in a random graph.  Journal of Combinatorial Theory Series B, 103(2):226–236, 2013\.
  * [13] A. Bonato and A. Burgess.  Cops and robbers on graphs based on designs.  Journal of Combinatorial Designs, 21(9):404–418, 2013.
  * [14] A. Bonato, E. Chiniforooshan, and P. Prałat.  Cops and robbers from a distance.  Theoretical Computer Science, 411(43):3834–3844, 2010.
  * [15] A. Bonato, S. Finbow, P. Gordinowicz, A. Haidar, W. B. Kinnersley, D. Mitsche, P. Prałat, and L. Stacho.  The robber strikes back.  In proceedings of Computational Intelligence, Cyber Security and Computational Models, volume 246, pages 3–12. Springer, 2014.
  * [16] A. Bonato and R. Nowakowski.  The Game of Cops and Robbers on Graphs.  American Mathematical Society, 2011.
  * [17] E. Bonnet, S. Gaspers, A. Lambilliotte, S. Rümmele, and A. Saffidine.  The parameterized complexity of positional games.  In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 90:1–90:14, 2017.
  * [18] E. Bonnet, F. Jamain, and A. Saffidine.  On the complexity of connection games.  Theoretical Computer Science, 644:2–28, 2016.
  * [19] N. Bowler, J. Erde, F. Lehner, and M. Pitz.  Bounding the cop number of a graph by its genus.  SIAM Journal on Discrete Mathematics, 35(4):2459–2489, 2021.
  * [20] P. Bradshaw and S. A. Hosseini.  Surrounding cops and robbers on graphs of bounded genus.  arXiv:1909.09916, 2019.  doi:https://doi.org/10.48550/arXiv.1909.09916.
  * [21] P. Bradshaw, S. A. Hosseini, and J. Turcotte.  Cops and robbers on directed and undirected abelian Cayley graphs.  European Journal of Combinatorics, In Press, 2021.  doi:https://doi.org/10.1016/j.ejc.2021.103383.
  * [22] S. Brandt, Y. Emek, J. Uitto, and R. Wattenhofer.  A tight lower bound for the capture time of the cops and robbers game.  Theoretical Computer Science, 839:143–163, 2020.
  * [23] A. C. Burgess, R. A. Cameron, N. E. Clarke, P. Danziger, S. Finbow, C. W. Jones, and D. A. Pike.  Cops that surround a robber.  Discrete Applied Mathematics, 285:552–566, 2020.
  * [24] J. Chalopin, V. Chepoi, N. Nisse, and V. Vaxès.  Cop and robber games when the robber can hide and ride.  SIAM Journal on Discrete Mathematics, 25(1):333–359, 2011.
  * [25] J. Chen, I. A. Kanj, and G. Xia.  Improved upper bounds for vertex cover.  Theoretical Computer Science, 411(40–42):3736–3756, 2010.
  * [26] E. Chiniforooshan.  A better bound for the cop number of general graphs.  Journal of Graph Theory, 58(1):45–48, 2008.
  * [27] T. H. Chung, G. A. Hollinger, and V. Isler.  Search and pursuit-evasion in mobile robotics: A survey.  Autonomous Robots, 31(299):299–316, 2011.
  * [28] 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.
  * [29] J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak.  Evacuating robots via unknown exit in a disk.  In F. Kuhn, editor, Distributed Computing (DISC 2014), volume 8784 of Lecture Notes in Computer Science, pages 122–136, 2018.  doi:https://doi.org/10.1007/978-3-662-45174-8_9.
  * [30] S. Das and H. Gahlawat.  On the Cop Number of String Graphs.  In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1–45:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ISAAC.2022.45.
  * [31] D. Dereniowski, T. Gavenčiak, and J. Kratochvíl.  Cops, a fast robber and defensive domination on interval graphs.  Theoretical Computer Science, 794:47–58, 2019.
  * [32] M. Dom, D. Lokshtanov, and S. Saurabh.  Incompressibility through colors and ids.  In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP ’09, page 378–389, Berlin, Heidelberg, 2009\. Springer-Verlag.  doi:10.1007/978-3-642-02927-1_32.
  * [33] H. E. Dudeney.  Amusements in Mathematics.  1917\.
  * [34] 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.
  * [35] M. R. Fellows.  The lost continent of polynomial time: Preprocessing and kernelization.  IWPEC’06, page 276–277, Berlin, Heidelberg, 2006. Springer-Verlag.  doi:10.1007/11847250_25.
  * [36] F. Fomin, P. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan.  Pursuing a fast robber on a graph.  Theoretical Computer Science, 41(7-9):1167–1181, 2010.
  * [37] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.  doi:10.1017/9781107415157.
  * [38] P. Frankl.  Cops and robbers in graphs with large girth and Cayley graphs.  Discrete Applied Mathematics, 17(3):301–305, 1987.
  * [39] N. Galesi, N. Talebanfard, and J. Torán.  Cops-robber games and the resolution of tseitin formulas.  ACM Transactions on Computation Theory, 12(2):1–22, 2020.
  * [40] Z. Gao and B. Yang.  The one-cop-moves game on planar graphs.  Journal of Combinatorial Optimization, 2019.  doi:https://doi.org/10.1007/s10878-019-00417-x.
  * [41] A. C. Giannopoulou, P. Hunter, and D. M. Thilikos.  Lifo-search: A min–max theorem and a searching game for cycle-rank and tree-depth.  Discrete Applied Mathematics, 160(15):2089–2097, 2012.
  * [42] G. Gottlob, N. Leone, and F. Scarcello.  A comparison of structural csp decomposition methods.  Artificial Intelligence, 124(2):243–282, 2000.
  * [43] G. Gottlob, N. Leone, and F. Scarcello.  The complexity of acyclic conjunctive queries.  Journal of the ACM, 48(3):431–498, 2001.
  * [44] 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.
  * [45] I. Gromovikov, W. B. Kinnersleyb, and B. Seamone.  Fully active cops and robbers.  Australian Journal of Combinatorics, 76(2):248–265, 2020.
  * [46] Y. C. Ho, A. E. Bryson Jr., and S. Baron.  Diffrential games and optimal pursuit-evasion strategies.  IEEE Transactions on Automatic Control, 10(4):385–389, 1965.
  * [47] S. A. Hosseini and B. Mohar.  Game of cops and robbers in oriented quotients of the integer grid.  Discrete Mathematics, 341(2):439–450, 2018.
  * [48] S. A. Hosseini, B. Mohar, and S. G. H. de la Maza.  Meyniel’s conjecture on graphs of bounded degree.  Journal of Graph Theory, 97(3):401–407, 2021.
  * [49] R. Isaacs.  Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization.  John Wiley and Sons, New York, 1965.
  * [50] 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\.
  * [51] T. Ishida and R. E. Korf.  Moving target search.  In Proceedings of the 12th International Joint Conference on Artificial Intelligence, IJCAI’91, pages 204–210, San Francisco, CA, USA, 1991\. Morgan Kaufmann Publishers Inc.
  * [52] T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas.  Directed tree-width.  Journal of Combinatorial Theory Series B, 82(1):138–154, 2001.
  * [53] G. Joret, M. Kaminski, and D. O. Theis.  Cops and robber game on graphs with forbidden (induced) subgraphs.  Contributions to Discrete Mathematics, 5(2):40–51, 2010.
  * [54] W. B. Kinnersley.  Cops and robbers is exptime-complete.  Journal of Combinatorial Theory Series B, 111:201–220, 2015.
  * [55] K. Klein and S. Suri.  Catch me if you can: Pursuit and capture in polygonal environments with obstacles.  In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2012), volume 26, pages 2010–2016, 2012.  doi:DOI:https://doi.org/10.1609/aaai.v26i1.8375.
  * [56] M. Lampis.  Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica, 64(1):19–37, 2012.
  * [57] F. Lehner.  On the cop number of toroidal graphs.  Journal of Combinatorial Theory, Series B, 151:250–262, 2021.
  * [58] P. Loh and S. Oh.  Cops and robbers on planar directed graphs.  Journal of Graph Theory, 86(3):329–340, 2017.
  * [59] L. Lu and X. Peng.  On Meyniel’s conjecture of the cop number.  Journal of Graph Theory, 71(2):192–205, 2011.
  * [60] M. Mamino.  On the computational complexity of a game of cops and robbers.  Theoretical Computer Science, 477:48–56, 2013.
  * [61] C. Moldenhauer and N. R. Sturtevant.  Evaluating strategies for running from the cops.  In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI’09, pages 584–589, San Francisco, CA, USA, 2009\. Morgan Kaufmann Publishers Inc.
  * [62] N. Nisse.  Network decontamination.  In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 516–548. Springer, 2019.
  * [63] R. Nowakowski and P. Winkler.  Vertex-to-vertex pursuit in a graph.  Discrete Mathematics, 43(2-3):235–239, 1983.
  * [64] D. Offner and K. Ojakian.  Variations of cops and robber on the hypercube.  Australasian Journal of Combinatorics, 59(2):229–250, 2014.
  * [65] T. D. Parsons.  Pursuit-evasion in a graph.  In Theory and Applications of Graphs, LNCS, volume 642, pages 426–441. Springer, 1978.
  * [66] T. D. Parsons.  The search number of a connected graph.  In Proceedings of the Ninth Southeastern Conference on Combinatorics, GraphTheory, and Computing, volume XXI, pages 549–554. Utilitas Math., 1978.
  * [67] V. Patsko, S. Kumkov, and V. Turova.  Pursuit-evasion games.  In Handbook of Dynamic Game Theory, pages 951–1038. Springer, 2018\.
  * [68] J. Petr, J. Portier, and L. Versteegen.  A faster algorithm for cops and robbers.  arXiv:2112.07449v2, 2021.
  * [69] P. Prałat and N. Wormald.  Meyniel’s conjecture holds for random graphs.  Random Structures and Algorithms, 48(2):396–421, 2015.
  * [70] P. Prałat and N. Wormald.  Meyniel’s conjecture holds for random $d$-regular graphs.  Random Structures and Algorithms, 55(3):719–741, 2019.
  * [71] A. Quilliot.  Thése d’Etat.  PhD thesis, Université de Paris VI, 1983.
  * [72] A. Scott.  On the Parameterized Complexity of Finding Short Winning Strategies in Combinatorial Games.  PhD thesis, University of Victoria, 2009.
  * [73] A. Scott and U. Stege.  Parameterized pursuit-evasion games.  Theoretical Computer Science, 411(43):3845–3858, 2010.
  * [74] A. Scott and B. Sudakov.  A bound for the cops and robbers problem.  SIAM Journal on Discrete Mathematics, 25(3):1438–1442, 2011.
  * [75] 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.
  * [76] K. A. Sim, T. S. Tan, and K. B. Wong.  Lazy cops and robbers on generalized hypercubes.  Discrete Mathematics, 340(7):1693–1704, 2017.
  * [77] B. Tastan, Y. Chang, and G. Sukthankar.  Learning to intercept opponents in first person shooter games.  In 2012 IEEE Conference on Computational Intelligence and Games (CIG), pages 100–107, 2012.  doi:10.1109/CIG.2012.6374144.
  * [78] R. Vidal, O. Shakernia, H.J. Kim, D.H. Shim, and S. Sastry.  Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation.  IEEE Transactions on Robotics and Automation, 18(5):662–669, 2002\.  doi:10.1109/TRA.2002.804040.
  * [79] L. Wang and B. Yang.  The one-cop-moves game on graphs with some special structures.  Theoretical Computer Science, 847:17–26, 2020.
  * [80] D. P. Williamson and D. B. Shmoys.  The Design of Approximation Algorithms. Cambridge University Press, 2011.
  * [81] F. Xie, A. Botea, and A. Kishimoto.  A scalable approach to chasing multiple moving targets with multiple agents.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI’17, pages 4470–4476. AAAI Press, 2017.
  * [82] K. Zarankiewicz.  Problem P101.  Colloquium Mathematicum, 3:19–30, 1954.