Replacing Cops with Zombies

Pursuit-Evasion games are played on a simple, undirected graph $G$ with vertex set $V(G)$ and edge set $E(G)$. The minimum number of cops for which there is a winning strategy for the Cop player in Cops and Robbers in a graph $G$ is called the cop number $c(G)$ of $G$, and the minimum number of zombies for which there is a winning strategy for the Zombie player in Zombies and Survivors in a graph $G$ is called the zombie number $z(G)$. A graph with cop number $k$ is called a k-cop-win graph. A 1-cop-win graph is also called a cop-win graph, and a graph that is not 1-cop-win is called a robber-win graph. A zombie-win graph, survivor-win graph and k-zombie-win graph are defined similarly.

Besides studying the number of pursuers, we also consider how quickly the pursuers can capture the evader. The capture time is a measure of the length of the game, that is, the number of rounds that elapse until capture, assuming that both players move optimally. When we say that the players move optimally, we mean that during each of the pursuer’s turns, given the current positions of all pieces, the pursuer moves its piece(s) to minimize the number of rounds required to capture the evader in the worst case considering all possible evader strategies. Similarly, during each of the evader’s turns, given the current positions of all piece(s), the evader moves its piece(s) to maximize the number of rounds for pursuers to capture the evader in the best case considering all possible pursuer strategies. We use the definition of capture time for Cops and Robbers from [3]: for any $p\ge c(G)$, the cop capture time, denoted by $cap{t}_c(G,p)$, is the minimum number of rounds needed for $p$ cops to capture the robber on $G$ over all possible games in which both players play optimally. We use the analogous definition of capture time for Zombies and Survivors [11]: for any $p\ge z(G)$, the zombie capture time, denoted by $cap{t}_z(G,p)$, is the minimum number of rounds needed for $p$ zombies to capture the survivor on $G$ over all possible games in which both players play optimally. For any graph G, $cap{t}_c(G,p)\le cap{t}_z(G,p)$, since $p$ cops can follow any $p$-zombie-strategy.

The throttling number is a measure that combines the number of pursuers and the capture time. Breen et al. [6] introduced the cop-throttling number, denoted by $t{h}_c(G)$, as the minimum value of $(p+cap{t}_c(G,p))$ taken over all $p\in \{c(G),\mathrm{\dots },|V(G)|\}$. We define the zombie-throttling number $t{h}_z(G)$ of a graph $G$ analogously: the zombie-throttling number, denoted by $t{h}_z(G)$, is the minimum value of $(p+cap{t}_z(G,p))$ taken over all $p\in \{z(G),\mathrm{\dots },|V(G)|\}$. For any graph $G$, we have $t{h}_c(G)\le t{h}_z(G)$, since $p+cap{t}_c(G,p)\le p+cap{t}_z(G,p)$ for any fixed $p$.

In Section 2, we study a graph class that exhibits a structure where having cops as pursuers seems to be more useful than having zombies. In particular, if a graph has a central vertex $c$ whose removal would shatter the graph into small pieces, then a good strategy for the Cop player would be to have one cop stay at vertex $c$ to guard it, and then have a small number of cops go chase and capture the robber in its component. In Zombies and Survivors, the Zombie player cannot implement this strategy since every zombie piece must move in every round, and so different strategies, and perhaps more zombies, are needed. We study a particularly simple such class of graphs, which we call foliage graphs, each of which consist of a collection of at least two cycles which meet at a single common intersection vertex. This graph class is a generalization of a set of graphs studied by Bartier et al. [1]. The cop number of any such graph is at most 2, using the strategy described above. We provide a characterization of foliage graphs that allows us to distinguish whether the zombie number is 1, 2, or neither. In other words, our characterization determines for which foliage graphs the zombie number is equal to the cop number.

In Section 3, we compare the cop-throttling number and zombie-throttling number of the Cartesian grid and the strong grid. In particular, we give matching upper and lower asymptotic bounds on the throttling number of such graphs, which are the same regardless of whether the pursuers are cops or zombies. More specifically, we prove that for any integers $a\ge b\ge 1$, and $G\in \{P_a\mathrm{\square }{P}_b,P_a⊠P_b\}$,

Due to space limitations, in some cases we omit or only sketch the proof details. Many of the omitted details can be found in [12].

Fitzpatrick et al. [9] formally introduced Zombies and Survivors. Since the allowed zombies’ moves are a subset of the allowed cops’ moves, it follows that $z(G)\ge c(G)$, which allows us to relate upper and lower bounds from one problem to the other. Offner and Ojakian [16] proved that the ratio $z(G)/c(G)$ can be made arbitrarily large by showing that, for any $m\ge k\ge 1$, there is a graph with zombie number $m$ and cop number $k$. One direction of research is to determine the zombie number or bounds on the zombie number for specific graph classes, such as outerplanar graphs [1, 4, 9], hypercubes [8], and graph products [1, 5, 8, 9, 11, 13, 14, 16, 18]. Regarding capture time, Clarke and Nowakowski [7] showed that for a cop-win graph with $n$ vertices, the cop-win strategy in terms of cop-win ordering naturally leads to a capture time of at most $n$. Bonato et al. [3] improved the capture time bound to $n-3$ for graphs with $n\ge 5$ vertices, and Gavenčiak [10] improved the bound to $n-4$ when $n\ge 7$. Bonato et al. [3] showed that the capture time of $2$-dismantlable graphs (graphs that have at least two corners after recursively removing two corners) is bounded above by $\lceil n/2\rceil$. For the Cops and Robbers game, determining the capture time with $k$ cops for some fixed constant $k$ is in P [2]. Determining the minimum number of cops to capture the robber within $k$ rounds for some fixed constant $k$ is NP-complete [3]. Further, Keramatipour and Bahrak [11] proved that determining the minimum number of zombies to capture the survivor within $k$ rounds for an arbitrary given $k$ is NP-hard for Zombies and Survivors. Also, they provided a bound on the capture time of the Cartesian product of $G$ and $H$ with $z_G+z_H$ zombies, and showed $cap{t}_z(G\mathrm{\square }H,z_G+z_H)\le rad(G)+rad(H)+cap{t}_z(G,z_G)+cap{t}_z(H,z_H)$ [11]. Regarding throttling numbers, Breen et al. [6] proved that for the grid $G=P_a\mathrm{\square }{P}_b$, the cop-throttling number satisfies $t{h}_c(G)\in O(\sqrt{ab})$. Breen et al. [6, Observation 2.1] showed that for every graph $G$, the cop-throttling number satisfies $t{h}_c(G)\le \gamma (G)+1$ where $\gamma (G)$ denotes the domination number of $G$. The same upper bound applies to zombie-throttling number $t{h}_z(G)$, since by initially placing $\gamma (G)$ zombies on the vertices of a minimum dominating set, the survivor’s starting vertex is either in the dominating set or adjacent to a vertex in the dominating set, so the survivor will be captured by a zombie in the first round. Breen et al. [6, Example 2.2] then showed that the cop-throttling can be arbitrarily smaller than the domination number, and the same example also applies to the zombie-throttling number.

First, we establish matching upper and lower bounds on the zombie-throttling number of $a\times b$ Cartesian grids. Without loss of generality, we assume that $a\ge b$. Let $P_a\mathrm{\square }{P}_b$ be the $a\times b$ grid with vertex set $V=\{(x,y)\mid x\in \{0,1,2,\mathrm{\dots },a-1\},y\in \{0,1,2,\mathrm{\dots },b-1\}\}$, then the size of $P_a\mathrm{\square }{P}_b$ is $|V|=ab$. For convenience, assume that the grid $P_a\mathrm{\square }{P}_b$ is drawn in the first quadrant of the Euclidean plane, where the first element of each vertex corresponds to its $x$-coordinate, and the second element of each vertex corresponds to its $y$-coordinate.

For the upper bound, the idea is to divide the entire grid into smaller subgrids and place the zombies at the corners of the subgrids. Let $d_a,d_b$ be two positive integers such that $d_a\le a-1$ and $d_b\le b-1$, whose specific values will be set later during the analysis. Roughly speaking, the values $d_a$ and $d_b$ represent the width and height of the subgrids, respectively (except for some subgrids at the rightmost and topmost border of the grid, due to the width or height of the entire grid not being divisible by $d_a$ or $d_b$, respectively). The number of subgrids that fit horizontally in the grid is defined as $s_a=\lceil (a-1)/d_a\rceil$, and the number of subgrids that fit vertically in the grid is defined as $s_b=\lceil (b-1)/d_b\rceil$. The initial placement of the zombies is at the corner of these subgrids, and to ensure that the placement of zombies remains within the boundaries of the grid, the maximum value of the zombie’s initial coordinate is at most $a-1$ in the $x$-coordinate and at most $b-1$ in the $y$-coordinate. More specifically, for each $i\in \{0,\mathrm{\dots },s_a\}$ and $j\in \{0,\mathrm{\dots },s_b\}$, place one zombie, denoted $Z_{i,j}$, at vertex $(\min \{i\cdot d_a,a-1\},\min \{j\cdot d_b,b-1\})$. Note that, if $a-1$ is not an integer multiple of $d_a$, the initial distance between zombies $Z_{s_a-1,j}$ and $Z_{s_a,j}$ is less than $d_a$, and, if $b-1$ is not a multiple of $d_b$, the initial distance between zombies $Z_{i,s_b-1}$ and $Z_{i,s_b}$ is less than $d_b$. Then, place four additional zombies: one at each corner of the grid. Figure 1 illustrates an example of the initial placement of zombies for $P_{12}\mathrm{\square }{P}_{10}$ with $d_a=d_b=\lceil {(11\cdot 9)}^{1/3}\rceil =5$. This completes the description of the initial placement of zombies, leading to the following upper bound on the number of zombies.

Next, the survivor selects its starting vertex. For $i\in \{0,\mathrm{\dots },s_a-1\}$ and $j\in \{0,\mathrm{\dots },s_b-1\}$, denote by subgrid $S{G}_{i,j}$ the subgrid with four corner vertices $(i\cdot d_a,j\cdot d_b)$, $(\min \{a-1,(i+1)\cdot d_a\},j\cdot d_b)$, $(i\cdot d_a,\min \{b-1,(j+1)\cdot d_b\})$, and $(\min \{a-1,(i+1)\cdot d_a\},\min \{b-1,(j+1)\cdot d_b\})$. These corners are initially occupied by $Z_{i,j}$, $Z_{i+1,j}$, $Z_{i,j+1}$, and $Z_{i+1,j+1}$, respectively, with the bottom-left corner of $S{G}_{i,j}$ occupied by $Z_{i,j}$. The survivor’s starting position lies within a subgrid $S{G}_{\alpha ,\beta }$ for some $\alpha \in \{0,\mathrm{\dots },s_a-1\}$ and $\beta \in \{0,\mathrm{\dots },s_b-1\}$. We refer to this subgrid as the survivor’s home subgrid (and if the survivor is on the boundary of multiple subgrids, the home subgrid is defined as the one that minimizes both $\alpha$ and $\beta$.)

Let $d=\max \{d_a,d_b\}$. To describe the zombie strategy when the survivor’s home subgrid is $S{G}_{\alpha ,\beta }$, we define four pairs of nearby zombies, called the confining zombies that surround the survivor in four directions: below, above, to the left, and to the right. More specifically, the four pairs are defined as follows:

• $\mathrm{■}$

  $Z_{H_1}≔\{Z_{\alpha ,j_{\mathrm{below}}},Z_{\alpha +1,j_{\mathrm{below}}}\}$, where $j_{\mathrm{below}}$ is the largest index such that the $y$-coordinate of the two zombies is initially at least $d$ below the survivor’s initially, or $j_{\mathrm{below}}=0$ if no such index exists.

• $\mathrm{■}$

  $Z_{H_2}≔\{Z_{\alpha ,j_{\mathrm{above}}},Z_{\alpha +1,j_{\mathrm{above}}}\}$, where $j_{\mathrm{above}}$ is the smallest index such that the $y$-coordinate of the two zombies is initially at least $d$ above the survivor’s initially, or $j_{\mathrm{above}}=s_b-1$ if no such index exists.

• $\mathrm{■}$

  $Z_{V_1}≔\{Z_{i_{\mathrm{left}},\beta },Z_{i_{\mathrm{left}},\beta +1}\}$, where $i_{\mathrm{left}}$ is the largest index such that the $x$-coordinate of the two zombies is initially at least $d$ to the left of the survivor’s, or $i_{\mathrm{left}}=0$ if no such index exists.

• $\mathrm{■}$

  $Z_{V_2}≔\{Z_{i_{\mathrm{right}},\beta },Z_{i_{\mathrm{right}},\beta +1}\}$, where $i_{\mathrm{right}}$ is the smallest index such that the $x$-coordinate of the two zombies is initially at least $d$ to the right of the survivor’s, or $i_{\mathrm{right}}=s_a-1$ if no such index exists.

No individual zombie needs to be used in more than one of the above pairs, even if $S{G}_{i,j}$ lies at a corner of $P_a\mathrm{\square }{P}_b$, because we placed an additional zombie at each corner of the grid during the initial setup.

We say that a zombie $Z$ catches the survivor’s $x$-shadow if $Z$ and the survivor have the same $x$-coordinate. Catching the survivor’s $y$-shadow is defined analogously. For each $H\in \{H_1,H_2\}$, we say that the pair of zombies in $Z_H$ have caught the survivor’s $x$-shadow if at least one zombie in $Z_H$ has done so. Similarly, for each $V\in \{V_1,V_2\}$, the pair of zombies in $Z_V$ has caught the survivor’s $y$-shadow if at least one zombie in $Z_V$ has done so.

In this section, we modify our approach for the Cartesian grid $P_a\mathrm{\square }{P}_b$ from Section 3.1 to prove tight asymptotic bounds on the zombie-throttling number in the strong grid $P_a⊠P_b$. The main difference is that, in a strong grid, if a zombie doesn’t have the same $x$ and $y$ coordinates as the survivor, then the zombie can move closer to the survivor in both coordinates during its turn. Let $P_a⊠P_b$ be the $a\times b$ strong grid with vertex set $V=\{(x,y)\mid x\in \{0,1,2,\mathrm{\dots },a-1\},y\in \{0,1,2,\mathrm{\dots },b-1\}\}$. As in Section 3.1, suppose that the grid $P_a⊠P_b$ is drawn in the Euclidean plane.

For the upper bound, we initially place the zombies as we did in Section 3.1, but we don’t place four additional zombies at the four corners of the graph. Figure 2(a) illustrates an example of the initial zombie placement for $P_{10}⊠P_{10}$ with $d_a=d_b=\lceil {(9\cdot 9)}^{1/3}\rceil =5$, and the corresponding subgrids. Subtracting 4 from the bound obtained in Lemma 5, we obtain the following upper bound on the number of zombies.

Next, the survivor chooses its starting vertex, which lies within a subgrid $S{G}_{\alpha ,\beta }$ for some $\alpha \in \{0,\mathrm{\dots },s_a-1\}$ and $\beta \in \{0,\mathrm{\dots },s_b-1\}$. We refer to this subgrid as the survivor’s home subgrid (and if the survivor is on the boundary of multiple subgrids, the home subgrid is defined as the one that minimizes both $\alpha$ and $\beta$.) The four corners of the home subgrid are occupied by zombies $Z_{\alpha ,\beta },Z_{\alpha ,\beta +1},Z_{\alpha +1,\beta +1},Z_{\alpha +1,\beta }$, and we call these four zombies the corner zombies. We define four pairs of zombies using the four corner zombies of the home subgrid $S{G}_{\alpha ,\beta }$, and each pair is lying on the boundaries of $S{G}_{\alpha ,\beta }$ in four directions: bottom, top, left, and right. More specifically, let $Z_{H_1}=\{Z_{\alpha ,\beta },Z_{\alpha +1,\beta }\}$, $Z_{H_2}=\{Z_{\alpha ,\beta +1},Z_{\alpha +1,\beta +1}\}$, $Z_{V_1}=\{Z_{\alpha ,\beta },Z_{\alpha ,\beta +1}\}$, $Z_{V_2}=\{Z_{\alpha +1,\beta },Z_{\alpha +1,\beta +1}\}$.

In Lemma 15, we show that at least one of the four corner zombies in the set $Z_{H_1}\cup Z_{H_2}\cup Z_{V_1}\cup Z_{V_2}$ will capture the survivor, and this will happen within $\lfloor \frac{\max \{d_a,d_b\}}{2}\rfloor$ rounds.

Combining Lemmas 14 and 15, we get an upper bound on the zombie-throttling number of $P_a⊠P_b$.

It remains to set the values of $d_a,d_b$, i.e., the width and height of the subgrids. We separately consider two cases depending on the relationship between $a$ and $b$. For strong grids $P_a\mathrm{\square }{P}_b$ that are “square-like”, i.e., if $a\ge b>{(ab)}^{1/3}$, we set $d_a=d_b=\lceil {(ab)}^{1/3}\rceil$, so the entire grid is divided into subgrids of size $\lceil {(ab)}^{1/3}\rceil$-by-$\lceil {(ab)}^{1/3}\rceil$. Otherwise, the grid $P_a\mathrm{\square }{P}_b$ is “path-like”, i.e., one dimension is significantly larger. In particular, if $a\ge {(ab)}^{1/3}>b$, we set $d_a=\lceil a^{1/2}\rceil$ and $d_b=b-1$, the entire grid is divided into subgrids of size $\lceil a^{1/2}\rceil$-by-$(b-1)$. Analogously to Lemmas 9 and 10, we obtain the following upper bounds on the zombie-throttling number.

To prove lower bounds on the zombie-throttling number for $P_a⊠P_b$, we use the same approach as for Lemma 11 in Section 3.1, except that the bound differs since the number of neighborhoods of radius $k$ needed to cover the strong grid is smaller. The same lower bound from Lemma 12 holds.

Combining Lemmas 17 and 18, we get the following asymptotically tight bounds on the zombie-throttling number of $P_a⊠P_b$.

The lower bounds from Sections 3.1 and 3.2 also apply to Cops and Robbers, since the proofs only rely on the fact that the game pieces can move to at most one adjacent vertex, once per round. Moreover, upper bounds from Zombies and Survivors immediately apply to Cops and Robbers since the cops can follow the zombie strategy. Thus, we get the following bounds on the cop-throttling number.