Department of Computer Science and Engineering, and Indian Institute of
Technology, Gandhinagar and http://www.neeldhara.com
neeldhara.m@iitgn.ac.inhttps://orcid.org/0000-0003-1727-5388Department of
Mathematics, and Indian Institute of Technology,
<EMAIL_ADDRESS>N. Misra and S. Nanoti <ccs2012>
<concept> <concept_id>10003752.10003809.10010052</concept_id>
<concept_desc>Theory of computation Parameterized complexity and exact
algorithms</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept> <concept_id>10003752.10003809.10011254</concept_id>
<concept_desc>Theory of computation Algorithm design techniques</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Parameterized complexity and exact algorithms
[500]Theory of computation Algorithm design techniques A shorter version of
this paper will appear in the Proceedings of the 48th International Symposium
on Mathematical Foundations of Computer Science (MFCS 2023). Both authors
acknowledge support from IIT Gandhinagar. Further, the first author
acknowledges support from the SERB grant ECR/2018/002967 and the second author
acknowledges support from CSIR.

###### Acknowledgements.

The authors are grateful to several anonymous reviewers for helpful comments
on earlier versions of this manuscript. Jérôme Leroux, Sylvain Lombardy, and
David Peleg 3 48th International Symposium on Mathematical Foundations of
Computer Science (MFCS 2023) MFCS 2023 MFCS 2023 August 28 to September 1,
2023 Bordeaux, France 272 68

# Spartan Bipartite Graphs are Essentially Elementary

Neeldhara Misra  Saraswati Girish Nanoti

###### Abstract

We study a two-player game on a graph between an attacker and a defender. To
begin with, the defender places guards on a subset of vertices. In each move,
the attacker attacks an edge. The defender must move at least one guard across
the attacked edge to defend the attack. The defender wins if and only if the
defender can defend an infinite sequence of attacks. The smallest number of
guards with which the defender has a winning strategy is called the eternal
vertex cover number of a graph $G$ and is denoted by $evc(G)$. It is clear
that $evc(G)$ is _at least_ $mvc(G)$, the size of a minimum vertex cover of
$G$. We say that $G$ is _Spartan_ if $evc(G)=mvc(G)$. The characterization of
Spartan graphs has been largely open. In the setting of bipartite graphs on
$2n$ vertices where every edge belongs to a perfect matching, an easy strategy
is to have $n$ guards that always move along perfect matchings in response to
attacks. We show that these are essentially the only Spartan bipartite graphs.

###### keywords:

Bipartite Graphs, Eternal Vertex Cover, Perfect Matchings, Elementary, Spartan

###### category:

##  1 Introduction

A _vertex cover_ of a graph $G$ is a subset $S$ of vertices such that every
edge in $G$ has at least one of its endpoints in $S$. An _optimal_ vertex
cover of a graph $G$ is a vertex cover of the smallest possible size and the
size of this optimal vertex cover is denoted by $mvc(G)$. A _bipartite graph_
$G=(V,E)$ is a graph whose vertex set can be partitioned into two independent
sets, say $V=(A\cup B)$, that is every edge is between a vertex in $A$ and one
in $B$. Clearly, both $A$ and $B$ are vertex covers of $G$. If a bipartite
graph $G=(A\cup B,E)$ is connected and its _only_ optimal vertex covers are
$A$ and $B$, then we say that $G$ is _elementary_. If every connected
component of a bipartite graph is elementary, then we call it _essentially
elementary_.

Klostermeyer and Mynhardt [8] introduced the notion of the _eternal vertex
cover_ number of a graph $G$. There are two players — an _attacker_ and a
_defender_ , who are playing on a simple, undirected graph $G$. In the
beginning, the defender can choose to place guards on some of the vertices of
$G$. The attacker’s move involves choosing an edge to “attack”. The defender
is able to “defend” this attack if she can move the guards along the edges of
the graph in such a way that at least one guard moves along the attacked edge.
If both the endpoints of the attacked edge have guards on them, the guards can
simply exchange their places and the attack is defended as well as the
original configuration of guards is restored. Note that any number of guards
can move after an attack, but each guard can move only one “step”, i.e., just
along a single edge. If such a movement is not possible, then the attacker
wins. If the defender can defend the graph against an infinite sequence of
attacks, then the defender wins (see Figure 1). The minimum number of guards
with which the defender has a winning strategy is called the _eternal vertex
cover number_ of the graph $G$ and is denoted by $evc(G)$.

There are two variations of this game, one where only one guard can be present
per vertex at a given time and a variant where more than one guard can be
present on a vertex at a given time. Our results apply to both the variants of
the game.

(a) The intial positions of the guards are denoted by the star-shaped
vertices.

(b) The attacker’s move targets the edge to the far-right, highlighted by a
wavy red line.

(c) The defender responds to defend the attack by moving a guard along the
attacked edge.

(d) Simultaneously, the defender moves another guard to ensure that no edges
are left vulnerable. This is the resultant position of the guards.

Figure 1: An attack that is defended by moving two guards.

If $S_{\ell}$ is the subset of vertices that have guards on them after the
defender has played her $\ell$-th move, and $S_{\ell}$ is not a vertex cover
of $G$, then the attacker can target any of the uncovered edges to win the
game. Therefore, when the defender has a winning strategy, it implies that she
can always “reconfigure” one vertex cover into another in response to any
attack, where the reconfiguration is constrained by the rules of how the
guards can move and the requirement that at least one of these guards needs to
move along the attacked edge. It follows that $evc(G)\geq mvc(G)$, where
$mvc(G)$ is the size of the smallest vertex cover for any graph $G$.

We call graphs $G$ which enjoy $evc(G)=mvc(G)$ _Spartan_ , to indicate that
these graphs can manage attacks without using “additional” guards.
Understanding Spartan graphs for several special cases have been addressed in
the literature (see, for instance, [3]). However, the characterization of
bipartite graphs that are Spartan has been left open. We show that bipartite
graphs are Spartan if and only if they are essentially elementary.

We also consider a natural extension of the eternal vertex cover problem:
where the guards are allowed to move two or more steps on each turn instead of
one, without retracing. An attack is defended only if the guard moves along
the attacked edge on their first step. We show that with just one additional
step, we need either just as many guards as the size of the smallest vertex
cover or one more: so in this variant all graphs are “almost” Spartan. We also
show that the extra guard is needed only if the graph has a degree one vertex
not contained in any minimum vertex cover. Finally, we show that allowing for
more than one extra step is the same as allowing exactly one extra step.

Related Work. Among characterizations related to Spartan graphs, we have the
following. Let the graph class $\mathcal{F}$ denote the class of all connected
graphs $G$ for which each minimum vertex cover of $G$ that contains all the
cut vertices of $G$ induces a connected subgraph in $G$. (A cut vertex is a
vertex whose removal disconnects the graph.) Let $G(V,E)$ be a graph that
belongs to $\mathcal{F}$, with at least two vertices, and $X\subset V$ be the
set of cut vertices of $G$. Then Babu et al. [2] showed that $G$ is Spartan if
and only if for every vertex $v\in V\backslash X$, there exists a minimum
vertex cover $S_{v}$ of $G$ such that $X\cup\\{v\\}\subset S_{v}$.
Klostermeyer and Mynhardt [7] also study graphs for which the eternal vertex
cover number coincides with the eternal domination number, a closely related
notion. This is a similar game, except that the attacks happen on vertices and
if the attacked vertex does not have a guard already, then a guard from a
neighbouring vertex must come to the attacked vertex. All other guards can
stay on their initial position or move to a neighbouring vertex. The minimum
number of guards required to protect the graph from an infinite sequence of
attacks is called the _eternal domination number_.

Note that twice as many vertices as the $mvc(G)$ always suffice to defend
against any sequence of attacks — by placing guards on both endpoints of any
maximum matching to begin with and after any attack, reconfiguring the guards
to obtain another maximum matching. Using this strategy, a $2-$approximation
algorithm for Eternal Vertex Cover was obtained by Fomin et al. [5]. This also
implies $mvc(G)\leq evc(G)\leq 2mvc(G)$. [8] gave a characterization of the
graphs for which the upper bound is achieved. The notion of elementary graphs
was considered by Lovász and Plummer [9] and several useful characterizations
were given by Hetyei [6]. We adapt these definitions to suit the context of
bipartite graphs.

### Methodology.

Recall that a _matching_ is a collection of vertex disjoint edges, and a
matching which contains one edge incident to each vertex of a graph is called
a _perfect matching_. We say that an edge is _allowed_ if it is contained in
some perfect matching. A graph $G$ is said to be _elementary_ if and only if
it is connected and every edge is allowed.

It turns out that a connected bipartite graph $G=(A\cup B,E)$ is elementary if
and only if its _only_ optimal vertex covers are $A$ and $B$, as we make
explicit in the proposition below.

######  Proposition 1.1 ([6]).

The following are equivalent for any connected bipartite graph $G=(A\cup
B,E)$.

  1. 1.

$A$ and $B$ are the only minimum vertex covers of $G$, and in particular
$|A|=|B|.$

  2. 2.

Every edge in $G$ is allowed.

Notice that it is easy to see that for bipartite graphs, if $G$ is elementary
then it is Spartan (see also Lemma 2.1 and Araki, Fujito, and Inoue [1]).
Indeed, we start by placing guards on all vertices of $A$. If the edge $e$ is
attacked, then we move guards to $B$ along the edges of the perfect matching
$M$ that contains the edge $e$. Future attacks can be similarly defended, so
the guards alternate between occupying $A$ and $B$ in response to edge
attacks.

What we focus on demonstrating in this contribution is the converse, namely
that if a connected bipartite graph $G$ does not have this structure, then it
is also not Spartan: in some sense, the trivial scenario is the only one in
which we can hope to manage without employing any “extra” guards.

Spartan $\implies$ Perfect Matching. To begin with, notice that if $G=(A\cup
B,E)$ is connected and does not have a perfect matching, we already need more
than $mvc(G)$ guards (see also Proposition 2.4). In particular, let $M$ be a
maximum matching in $G$. Recall that $|M|=mvc(G)$ by König’s theorem. Without
loss of generality, let $b\in B$ be a vertex not incident to any edge of $M$.
Since $G$ is connected, $b$ has some neighbor $a\in A$, which must belong to
any vertex cover of $G$. In particular, the defender is forced to position a
guard on $a$ in the initial configuration. If the edge $ab$ is attacked, the
guard on $a$ is forced to move to $b$. This creates a situation where $|M|-1$
guards have to reposition themselves to protect all the edges of $M$ — which
is impossible since the edges of $M$ are disjoint.

Therefore, a necessary condition for a connected bipartite graph to be Spartan
is that it must admit a perfect matching. This is, however, evidently not
sufficient: indeed, there are connected bipartite graphs with perfect
matchings that are not Spartan (see also Figure 2).

Figure 2: A graph with a perfect matching where $mvc(G)$ many guards do not
suffice. For each choice of $mvc(G)$ many guards at the initial configuration,
attacking the dashed edge shown in the figure leads to an indefensible
position in one or two steps.

Spartan $\implies$ No Degree One Vertices. We observe that a connected
bipartite Spartan graph $G=(A\cup B,E)$ on at least three vertices cannot have
a degree one vertex (see also Proposition 2.6 and Babu et al. [2]). Assume to
the contrary that $G$ has a degree one vertex, say $a\in A$. Let $b$ denote
$a$’s unique neighbor in $G$. Since $G$ has at least one vertex other than $a$
and $b$, and $G$ is connected, $b$ must have another neighbor in $G$: say
$a^{\prime}$. Now, if the initial configuration has a guard on $a$, then
attack the edge $ba^{\prime}$; otherwise attack the edge $ab$ to force a guard
on $a$ and then attack $ba^{\prime}$. Both cases lead to a scenario where both
endpoints of the edge $ab$ have guards on them. However, since $G$ is Spartan,
it has a perfect matching $M$. Further, since $a$ is a degree one vertex, $M$
is forced to contain the edge $ab$. This in turn implies that at least $|A|-1$
guards are required to defend the rest of the graph, contradicting the
assumption that $G$ is Spartan.

Proof by Structure-Preserving Contractions. So far, we have seen that a
connected bipartite graph $G=(A\cup B,E)$ which is Spartan must have a perfect
matching and no degree one vertices. Fix an arbitrary perfect matching $M$,
and let $ab\in M$. Let $P$ be a maximal walk (without repeating edges)
starting at $a$, alternating between edges of $M$ and $E\setminus M$. The
terminal vertex of $P$ is either $a$, or a vertex $v$ which must have a
neighbor on $P$, since $G$ has no degree one vertices. So from $P$, we can
derive a cycle whose edges alternate between $M$ and $E\setminus M$ (see also
Proposition 2.23).

At a high level (see Figure 3), our proof relies on “contracting” each such
cycle to a single matching edge and arguing that the resulting graph remains
Spartan provided the original graph was also Spartan. In particular, we show
the following. If $G$ is Spartan to begin with, and $M$ is a perfect matching
with $S$ is a set of endpoints of $M^{\prime}\subseteq M$ such that $G[S]$ is
elementary, then “replacing” $G[S]$ with a single edge until this operation is
no longer possible; keeps the graph Spartan (see also Lemma 2.17). Here it is
useful that any bipartite graph obtained by adding edges to a cycle (while
preserving the bipartite-ness) is elementary, a fact that we establish
separately (see also Proposition 2.9) — thus we can simply keep contracting
along cycles $C$. The idea of the proof is then the following. Consider what
happens once we are stuck, i.e., we cannot contract any further: we either
have an edge, or we have a graph that is not an edge but must have a degree
one vertex (if not, note that we would not be stuck). But from our previous
discussion, we know that a connected bipartite Spartan graph on at least three
vertices cannot have a degree one vertex. So in this situation, we have
transformed the Spartan graph we started with into one that is not Spartan,
and in particular, there is an attack that $mvc(\cdot)$ many guards will not
be able to defend on the “contracted” graph. It turns out that this attack can
be mimicked on the graph we started with, contradicting our assumption that
the original graph is Spartan. Thus, our process must end at a single edge.

To conclude the proof, we show that if we take an elementary bipartite graph
$G$ and “inject” an elementary graph into it by substituting an edge with an
elementary graph, then the resulting graph is also elementary. This lets us
run the contraction operations on $G$ in reverse, starting from the edge that
we ended up with; and since an edge is elementary, we conclude that $G$ must
have also been elementary (see also Lemma 2.20).

arrow style=<->,back arrow disabled=true [flow
diagram:horizontal]$G_{0}=G$,$G_{1}$,$\cdots$,$G_{t}=\\{e\\}$

Figure 3: Proof idea: The sequence of forward contractions preserves “Spartan-
ness” overall (i.e, $G_{t}$ is Spartan if $G_{0}$ is Spartan) while the
backward expansions preserve “elementary-ness”.

When $G$ is not connected, the arguments we made can be made independently of
every connected component of $G$. This leads to our final characterization:
that a biparitite graph $G$ is Spartan if and only if each of its components
are elementary. Since it is straightforward to check if a bipartite graph
$G=(A\cup B,E)$ is elementary (for instance, by checking if
$G\setminus\\{u,v\\}$ admits a perfect matching for every $uv\in E$), our
result also implies a polynomial-time recognition algorithm for bipartite
Spartan graphs. We note that, in contrast to $mvc(G)$, determining $evc(G)$ is
known to be NP-hard even for bipartite graphs.

In Section 2, we describe the proofs of the claims mentioned in the outline
here in greater detail. Our notation largely follows conventions from Diestel
[4].

##  2 Spartan Bipartite Graphs are Essentially Elementary

We begin with the (easy) forward implication, which was also observed by [1] —
we provide an explicit proof here in the interest of completeness.

######  Lemma 2.1.

If a bipartite graph $G$ is essentially elementary, $evc(G)=|V(G)|/2=mvc(G)$,
i.e., $G$ is Spartan.

######  Proof 2.2.

We first make the argument for the case when $G$ is connected. Since $G$ is
elementary, $mvc(G)=|V(G)|/2$ by the previous proposition. Since $evc(G)\geq
mvc(G)$ for any graph $G$, we just need to show that the defender has a
winning strategy when the number of guards is $mvc(G)$. Initially place all
the guards on one side, wlog say $A$. Suppose the attacker attacks an edge
$e$, since $e$ is allowed there exists a perfect matching containing $e$. Use
this matching to transfer all the guards to $B$ to ensure that one guard has
moved along $e$. Similarly transfer all the guards to $A$ using the perfect
matching containing the attacked edge in the next attack. Since the defender
can always transfer all the guards to the other side ensuring the movement of
one guard across the attacked edge, any sequence of attacks can be defended
and thus the defender wins.

Now, if $G$ has more than one connected component, the argument above can be
repeated for each connected component. If the components have sizes
$|C_{1}|,\ldots,|C_{\ell}|$ then the overall size of the eternal vertex cover
will be: $\frac{1}{2}\sum_{i=1}^{\ell}|C_{i}|=|V(G)|/2$.

Now, let $G$ be a Spartan biparitite graph with connected components
$C_{1},\ldots,C_{\ell}$. Note that:

$\mathsf{evc}(G)=\sum_{i=1}^{\ell}\mathsf{evc}(G[C_{i}])\geqslant\sum_{i=1}^{\ell}\mathsf{mvc}(G[C_{i}])=\mathsf{mvc}(G).$

Therefore, if $G$ is Spartan then $G[C_{i}]$ is Spartan for all $1\leqslant
i\leqslant[\ell]$. Indeed, if not, then there exists a component $C_{i}$ for
which $\mathsf{evc}(G[C_{i}])>\mathsf{mvc}(G[C_{i}])$. But combined with the
inequality above, this will imply that $\mathsf{evc}(G)>\mathsf{mvc}(G)$,
contradicting our assumption that $G$ is Spartan. Therefore, we may assume
without loss of generality that $G$ is connected, and our goal amounts to
showing the following.

######  Lemma 2.3.

If $G$ is a connected bipartite graph that is Spartan, then it is elementary.

We first argue that any connected Spartan bipartite graph must have a perfect
matching.

######  Proposition 2.4.

If $G$ is a Spartan connected bipartite graph, it admits a perfect matching.

######  Proof 2.5.

Let $G$ be a connected Spartan bipartite graph with bipartition $(A,B)$ where
$A=\\{a_{1},\ldots,a_{p}\\}$ and $B=\\{b_{1},\ldots,b_{q}\\}$ (see also Figure
4). For the sake of contradiction, assume that $G$ does _not_ admit a perfect
matching, i.e., without loss of generality let $q>k$. Let $S$ be a minimum
vertex cover in $G$ of size $k$ such that the guards are placed on $S$ in the
initial configuration. Let $M$ be any maximum matching. Without loss of
generality, let the edges of $M$ be given by:

$\\{e_{1}=(a_{1},b_{1}),\ldots,e_{i}=(a_{i},b_{i}),e_{i+1}=(a_{i+1},b_{i+1}),\ldots,e_{k}=(a_{k},b_{k})\\},$

where $S\cap A=\\{a_{1},\ldots,a_{i}\\}$ and $S\cap
B=\\{b_{i+1},\ldots,b_{k}\\}$.

Since $M$ is not a perfect matching, $|V(G)|>2k$ i.e. there exists a vertex in
$G$ which is not an endpoint of any edge in $M$. Without loss of generality,
let this vertex be $b_{q}$. Since $b_{q}$ is not an isolated vertex, it must
have a neighbour on the $A$ side. Since $S$ is a vertex cover, this neighbour
must lie in $S\cap A$. Without loss of generality, let this neighbour be
$a_{1}$. If the attacker attacks $a_{1}b_{q}$, the guard on $a_{1}$ must come
to $b_{q}$ and cannot move further. Now there are $k-1$ guards on the vertices
of $M$ to protect $k$ matching edges. So no matter how these guards arrange
themselves, at least one edge of $M$ must be vulnerable before the next
attack. The attacker attacks this edge in the next move and wins thus
contradicting the fact that $G$ is Spartan. Therefore, the graph $G$ must
admit a perfect matching.

$a_{1}$$a_{2}$$a_{3}$$a_{i}$$a_{i+1}$$a_{i+2}$$a_{k}$$b_{1}$$b_{2}$$b_{3}$$b_{i}$$b_{i+1}$$b_{i+2}$$b_{k}$$b_{q}$
(a) A graph which does not have a perfect matching and the red edge is
attacked

$a_{1}$$a_{2}$$a_{3}$$a_{i}$$a_{i+1}$$a_{i+2}$$a_{k}$$b_{1}$$b_{2}$$b_{3}$$b_{i}$$b_{i+1}$$b_{i+2}$$b_{k}$$b_{q}$
(b) After defending the attack, there are only $k-1$ guards to protect $k$
matching edges. So an edge will remain vulnerable.

Figure 4: Demonstrating that Spartan connected bipartite graphs must have
perfect matching towards a proof of Proposition 2.4.

So we now have that connected Spartan bipartite graphs $G$ have at least one
perfect matching. From now on we denote the bipartitions of $G$ by
$A=\\{a_{1},a_{2},\ldots a_{n}\\}$ and $B=\\{b_{1},b_{2},\ldots b_{n}\\}$
where each $a_{i}$ and $b_{i}$ have an edge between them so that we have a
perfect matching $M=\bigcup_{i=1}^{n}\\{a_{i}b_{i}\\}$. Since $G$ is
connected, these bipartitions are unique upto permutations. We now show that
connected bipartite graphs that are Spartan do not have degree one vertices.
This follows from known results (for example, as shown by [2]), however, our
argument is more direct and we make it explicit to make our presentation self-
contained.

######  Proposition 2.6 (No Degree One Vertex).

Let $G$ be a connected bipartite graph with $|V(G)|>2$ and with a perfect
matching. If $evc(G)=mvc(G)$, then $G$ has no degree one vertex.

######  Proof 2.7.

Let $G$ be a connected bipartite graph with $|V(G)|>2$ and with a perfect
matching. Assume that $evc(G)=mvc(G)$, and that $G$ has a degree $1$ vertex.
We will show that this leads to a contradiction (c.f LABEL:fig-nodegone).
Suppose $G$ has a degree $1$ vertex on the $A$ side, say $a_{1}$. Since the
graph is connected, $b_{1}$ has an edge with some other vertex say $a_{2}$. If
$b_{1}$ has a guard in the initial configuration, then attack $a_{1}b_{1}$.
This will cause the guard on $b_{1}$ to move to $a_{1}$. (It is not possible
that $a_{1}$ already had a guard because $a_{1}b_{1}$ belongs to a perfect
matching $M$ and we have only $n$ guards so some other edge in $M$ will be
left with no guard). After this no other guard can come to $b_{1}$ for a
similar reason. So without loss of generality we can assume that $a_{1}$ has a
guard and $b_{1}$ has no guard in the initial configuration.

Since $b_{1}$ has no guard, $a_{2}$ must have a guard to protect $a_{2}b_{1}$.
Now attack the edge $a_{2}b_{1}$. The guard on $a_{2}$ must move to $b_{1}$.
The guard on $a_{1}$ cannot move anywhere. So we have an overprotected edge
$a_{1}b_{1}$ which belongs to a perfect matching which means that some other
edge in the matching must be vulnerable. So $n$ guards are not sufficient to
protect the graph and hence $evc(G)\neq mvc(G)$.

From Lemma 2.1 and Proposition 2.6, we have the following.

######  Corollary 2.8.

Let $G$ be a connected bipartite graph with more than two vertices. If $G$ is
elementary, then $G$ cannot have a degree one vertex.

Next, we show that a bipartite graph with a cycle that visits every vertex is
elementary.

######  Proposition 2.9 (Adding edges to cycles).

Consider a connected bipartite graph $G=(A\cup B,E)$ which is a cycle
$a_{1}b_{1}a_{2}b_{2}\ldots a_{k}b_{k}a_{1}$ (where $k>1$). The graph
$G^{\prime}$ formed after adding any number of edges between $A$ and $B$
(preserving bipartiteness) will be elementary.

######  Proof 2.10.

Let $G$ be a connected bipartite graph $G$ which is a cycle
$a_{1}b_{1}a_{2}b_{2}\ldots a_{k}b_{k}a_{1}$, where $k>1$ (see also Figure 5).
Here the two sides of the bipartition are $A=\\{a_{1},a_{2},\ldots,a_{k}\\}$
and $B=\\{b_{1},b_{2},\ldots,b_{k}\\}$.

The graph $G$ has two perfect matchings which are given by
$M=\\{a_{1}b_{1},a_{2}b_{2},\ldots,a_{k}b_{k}\\}$ and
$M^{\prime}=\\{b_{1}a_{2},b_{2}a_{3},\ldots,b_{k-1}a_{k},b_{k}a_{1}\\}$. It is
easily seen that any edge of $G$ lies in one of these two perfect matchings.

Suppose we add some edges from $A$ to $B$. Notice that the vertex set of the
new graph $G^{\prime}$ is same as the vertex set of $G$. In order to prove
that $G^{\prime}$ is elementary, it is sufficient to show that each of the
newly added edges belongs to a perfect matching of $G^{\prime}$.

Consider a newly added edge $a_{i}b_{j}$. This clearly preserves
bipartiteness. Here, $i\neq j,j+1$ because the edges $a_{i}b_{i}$ and
$a_{i}b_{i-1}$ were already in $G$.

First, let $i>j+1$. Consider the matching:

$M_{1}=\\{a_{i}b_{j},b_{i}a_{i+1},b_{i+1}a_{i+2},\ldots,b_{k-1}a_{k},b_{k}a_{1},b_{1}a_{2},\ldots,b_{j-1}a_{j},a_{j+1}b_{j+1},a_{j+2}b_{j+2},\ldots,a_{i-1}b_{i-1}\\}.$

Clearly $M_{1}$ is a perfect matching containing $a_{i}b_{j}$.

Now let $i<j$. Let
$N_{1}=\\{a_{i}b_{j},b_{i}a_{i+1},b_{i+1}a_{i+2},\ldots,b_{j-1}a_{j}\\};N_{2}=\\{a_{1}b_{1},\ldots,a_{i-1}b_{i-1}\\};$
and $N_{3}=\\{a_{j+1}b_{j+1},\ldots,a_{k}b_{k}\\}.$

Consider the matching $M_{2}$ given by $N_{1}\cup N_{2}\cup N_{3}$. Clearly
$M_{2}$ is a perfect matching containing $a_{i}b_{j}$.

This concludes our argument showing that $G^{\prime}$ is elementary.

$a_{1}$$b_{1}$$a_{2}$$b_{2}$$a_{3}$$b_{3}$$a_{4}$$b_{4}$ (a) This figure shows
a cycle with $k=4$.

$a_{1}$$b_{1}$$a_{2}$$b_{2}$$a_{3}$$b_{3}$$a_{4}$$b_{4}$ (b) Each newly added
edge is allowed: Suppose $a_{1}b_{2}$ is the new edge, it can be combined with
the existing edges to form the perfect matching denoted by the dashed purple
lines.

Figure 5: An example of a bipartite graph with a spanning cycle.

We now introduce the terminology “special subset” to indicate that we are
working with a subset of endpoints of some edges in a perfect matching.

######  Definition 2.11 (Special Subset).

Let $G$ be a connected bipartite graph with a perfect matching
$M=\\{a_{1}b_{1},a_{2}b_{2},\ldots,a_{n}b_{n}\\}$. Consider:
$S=\\{a_{i_{1}},b_{i_{1}},a_{i_{2}},b_{i_{2}},\ldots,a_{i_{k}},b_{i_{k}}\\}$
for some distinct $i_{1},i_{2},\ldots,i_{k}\in[n]$ and $2\leq k\leq n$. Then
$S$ is said to be a special subset of $V(G)$.

A “special induced subgraph” is a subgraph induced by a special subset.

######  Definition 2.12 (Special Induced Subgraph).

Let $G$ be a connected bipartite graph with a perfect matching and $S$ be a
special subset of $V(G)$. The subgraph $G[S]$ induced by $S$ is called a
special induced subgraph of $G$.

We now note that edges allowed in special induced subgraphs of a graph $G$ are
also allowed in $G$.

######  Proposition 2.13 (Allowed Edge).

Let $G$ be a connected bipartite graph with a perfect matching $M$. Let $S$ be
a special subset of $G$ and $H=G[S]$ be the corresponding special induced
subgraph. An edge which is allowed in $H$ is also allowed in $G$.

######  Proof 2.14.

If $S=V(G)$, we are done. Otherwise without loss of generality, let $S$ be the
set $\\{a_{1},b_{1},a_{2},b_{2},\ldots,a_{k},b_{k}\\}$. Consider an edge
$a_{i}b_{j}$ which is allowed in $H$ for some $i,j\in[k]$. Consider the
matching $M_{H}$ which is a perfect matching of $H$ containing $a_{i}b_{j}$.
Consider $M^{\prime}=M_{H}\cup\\{a_{i+1}b_{i+1},\ldots,a_{k}b_{k}\\}$. Clearly
$M^{\prime}$ is a perfect matching of $G$ containing $a_{i}b_{j}$. Thus,
$a_{i}b_{j}$ is allowed in $G$.

We now turn to a key definition: one of “contracting” a special elementary
subset to a single edge. We refer the reader to Figure 6 for an example of an
application of this operation.

######  Definition 2.15 (Matching Contraction Graph).

Consider a connected bipartite graph $G$ with bipartition $A$ and $B$ and a
perfect matching $M$. Let $S$ and $H=G[S]$ be a special subset of $V(G)$ and
the corresponding special induced subgraph of $G$. If $H$ is elementary,
replace $A\cap S$ by a new vertex $\alpha$ and $B\cap S$ by a new vertex
$\beta$ in $G$. Add an edge $\alpha\beta$ in the new graph. For an edge $ab$
where $a\in A\backslash S$ and $b\in S$, add an edge $a\beta$ to the new
graph. Similarly for an edge $ab$ where $a\in S$ and $b\in B\backslash S$, add
an edge $\alpha b$ to the new graph. Keep all the other edges and vertices of
$G$ unchanged. If there are any parallel edges, replace them by a single edge.
The new graph $G_{S}$ thus obtained is called the matching contraction graph
of $G$ w.r.t. $S$ and the procedure of obtaining a matching contraction graph
is called as contraction.

Note that if $G$ is a connected bipartite graph and $S$ is a special subset,
then the matching contraction graph $G_{S}$ is also connected and bipartite.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$a_{7}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$b_{6}$$b_{7}$
(a) A graph $G$ with special elementary subset
$S=\\{a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\\}$.

$a_{3}$$a_{4}$$a_{5}$$a_{6}$$a_{7}$$b_{3}$$b_{4}$$b_{5}$$b_{6}$$b_{7}$ (b) The
matching contraction graph of $G$ w.r.t. $S$.

Figure 6: Demonstrating the operation of contracting a special elementary
subset to a single edge. For a more elaborate example involving a sequence of
contractions, see Figure 12.

It can be seen that if the special subset $S$ has size $2k$, then the matching
contraction graph has $2(n-k+1)$ vertices, a perfect matching of size $n-k+1$
and thus a minimum vertex cover of size $n-k+1$.

######  Definition 2.16 (Special elementary subset).

Let $G$ be a connected bipartite graph with a perfect matching. A special
subset $S$ such that $G[S]$ is elementary is called a special elementary
subset.

We consider a series of contractions over a graph $G$. Each time we contract a
special elementary subset $S$ of $G$. We rename each vertex in the new graph
as the largest indexed vertex in the original graph. We associate a label with
each vertex, which carries the names of the vertices of the original graph
that were contracted to this new vertex. We keep on repeating this procedure
until we reach a graph which cannot be contracted further. We denote this
graph by $G_{\bar{S}}$. We fix a perfect matching $M$ in $G$ and in each
contracted graph, we get a matching given by $M\setminus
E(G[S])\cup\\{\alpha\beta\\}$ where $\alpha$ and $\beta$ denote the newly
obtained vertices on the $A$ and $B$ side respectively. Whenever we say
“matched partner” or “matching edge” in the new graph, unless mentioned
otherwise, we will be referring to this matching.

######  Lemma 2.17 (Matching Contraction Graph Property).

Suppose that $G$ is a connected bipartite graph with a perfect matching $M$.
Then, if $G$ is Spartan, then $G_{\bar{S}}$ is Spartan.

######  Proof 2.18.

If $G_{\bar{S}}$ is a single edge, then $G$ was elementary to begin with, as
each expansion preserves the “elementary-ness” by Lemma 2.20. And since a
single edge is Spartan, $G_{\bar{S}}$ is Spartan in this case.

Consider the case where $G_{\bar{S}}$ is not a single edge. Now by Proposition
2.25, $G_{\bar{S}}$ must have a degree-$1$ vertex. Without loss of generality,
we assume that this degree-$1$ vertex is on the $B$ side and let us denote
this vertex by $\beta_{1}$ and its matched partner by $\alpha_{1}$. Also, note
that $G_{\bar{S}}$ is not Spartan by Proposition 2.6. We show that $G$ was
also not Spartan in this case.

Let $B_{1}$ be the set of vertices in $G$ in the label of $\beta_{1}$, i.e,
which were contracted to get $\beta_{1}$ and similarly $A_{1}$ be the set of
vertices in $A$ which were contracted to get $\alpha_{1}$ and let
$|A_{1}|=|B_{1}|=k$. Note that this contraction may not have happened in one
step, but over a series of steps. Notice that $G\setminus\\{A_{1}\cup
B_{1}\\}$ is non-empty, as $G_{\bar{S}}$ is not a single edge. Note that no
vertex in $B_{1}$ can be adjacent to a vertex in $A\setminus A_{1}$. Suppose
some vertex $b\in B_{1}$ is adjacent to a vertex $a\in A\setminus A_{1}$, this
will result in an edge $a\beta_{1}$ in $G_{\bar{S}}$ which contradicts the
fact that $\beta_{1}$ is a degree-$1$ vertex. Also, we know that after a
series of contractions, $G[A_{1}\cup B_{1}]$ got contracted to a single edge.
By Lemma 2.20, $G[A_{1}\cup B_{1}]$ is elementary. Therefore, any minimum
sized vertex cover of $G$ will contain all the $k$ vertices of $A_{1}$ and no
vertex from $B_{1}$ or all the $k$ vertices of $B_{1}$ and no vertex from
$A_{1}$.

Now consider any initial configuration of guards on $G$ with $n$ guards. As
seen above, either all the vertices of $B_{1}$ have guards or all the vertices
of $A_{1}$ have guards and only one of these can happen. If all the vertices
of $A_{1}$ are occupied by guards, the attacker attacks a matched edge
$a_{i}b_{i}$ such that $a_{i}\in A_{1}$. The guard on $a_{i}$ is forced to
move to $b_{i}$ and cannot move any further. If all the guards cannot
reconfigure to form a vertex cover, then $G$ is not Spartan and hence we are
done. Otherwise, all the guards must reconfigure in such a way that all the
vertices in $B_{1}$ have guards and all the vertices in $A_{1}$ do not have
guards. Thus without loss of generality, we can assume that all the vertices
in $B_{1}$ have guards and all the vertices in $A_{1}$ do not have guards.

Now recall that no vertex in $B_{1}$ has a neighbour in $A\setminus A_{1}$.
Since $G$ is connected, there exists $a_{p}\in A_{1}$ and $b_{q}\in B\setminus
B_{1}$ such that $a_{p}b_{q}\in E(G)$. Since $a_{p}$ does not have a guard,
$b_{q}$ must have a guard as the guards are occupying a vertex cover. Now
suppose the attacker attacks the edge $a_{p}b_{q}$, the guard on $b_{q}$ must
move to $a_{p}$. Since all the vertices in $B_{1}$ have guards but none of
them has a neighbour in $A\setminus A_{1}$ and no vertex in $A_{1}$ had a
guard before this guard just moved to $a_{p}$, now no guard can move from
$\\{A_{1}\cup B_{1}\\}$ to $V(G)\setminus A_{1}$. Thus there will be $k+1$
guards on $k$ matching edges in $G[A_{1}\cup B_{1}]$. Therefore, some edge in
$G[V(G)\setminus\\{A_{1}\cup B_{1}\\}]$ will be vulnerable and can be attacked
in the next move. Hence, $G$ is not Spartan.

_Remark:_ We have actually shown that any bipartite graph $G$ which is not
“essentially elementary” can be destroyed by the attacker in at most three
moves when the defender has $mvc(G)$ many guards.

Figure 7: Demonstrating a sequence of contractions.

Figure 8: Demonstrating how attacks are mimicked.

######  Definition 2.19 (Maximal Contraction Graph).

Let $G$ be a connected bipartite graph with a perfect matching and there does
not exist any special elementary subset $S$ of $V(G)$. Then $G$ is said to be
a maximal contraction graph.

Note that by definition the size of a special subset is always more than $2$
and hence if $|V(G)|=2$, i.e., $G$ is a single edge, then $G$ is a maximal
contraction graph as $G$ has no special subset and hence no special elementary
subset. Note that the sequence of contractions above ends in a maximal
contraction graph that is in fact an edge.

######  Lemma 2.20 (Maximal Contraction Graph).

Let $G$ be a connected bipartite graph with a perfect matching $M$. Let $S$ be
a special elementary subset of $V(G)$ and $G_{S}$ be the corresponding
matching contraction graph. Then, if $G_{S}$ is elementary, then $G$ is also
elementary.

######  Proof 2.21.

Let $G=(A\cup B,E)$. To show that $G$ is elementary, we show that $A$ and $B$
are the only optimal vertex covers of $G$. We assume that the edges of the
perfect matching in $G$ are $\\{a_{1}b_{1},a_{2}b_{2},\cdots,a_{n}b_{n}\\}$
and that the special subset $S$ is induced by the vertices based on the edges
$\\{a_{1}b_{1},\cdots,a_{k}b_{k}\\}$. Let $\alpha$ and $\beta$ denote the
endpoints of the edge in $G_{S}$ created by the contraction of $S$. Finally,
let $(A^{\prime},B^{\prime})$ denote the partition of $G_{S}$.

Note that $G[S]$ is assumed to be elementary. If $X$ is an optimal vertex
cover for $G$, then $X\cap S$ is a vertex cover for $G[S]$ of size $k$, since
$G\setminus S$ has a matching of size $(n-k)$. Observe that:

  * •

either $X\cap A=\\{a_{1},\cdots,a_{k}\\}$ and $X\cap B=\emptyset$, or

  * •

$X\cap A=\emptyset$ and $X\cap B=\\{b_{1},\cdots,b_{k}\\}$,

because any other subset of $k$ vertices that forms a valid vertex cover for
$G[S]$ would contradict the assumption that $G[S]$ is elementary.

Now assume that $G$ has a vertex cover $X$ such that $X\neq A$ and $X\neq B$.
Without loss of generality, assume that $X\cap A=\\{a_{1},\cdots,a_{k}\\}$
(the argument for the other case is symmetric). We let
$X_{A}:=X\cap\\{a_{k+1},\cdots,a_{n}\\}$ and
$X_{B}=X\cap\\{b_{k+1},\cdots,b_{n}\\}$. Note that $X_{B}\neq\emptyset$
because $X\neq A$.

We now claim that $X^{\prime}:=X_{A}\cup X_{B}\cup\\{\alpha\\}$ is an optimal
vertex cover in $G_{S}$ that is different from both $A^{\prime}$ and
$B^{\prime}$. It is clear that $|X^{\prime}|=(n-k+1)$, thus the size of
$X^{\prime}$ is $mvc(G_{S})$. Further, since $\alpha\in A^{\prime}$ and
$X_{B}\neq\emptyset$, $X^{\prime}\neq A^{\prime}$ and $X^{\prime}\neq
B^{\prime}$. It remains to be shown that $X^{\prime}$ covers all edges in
$G_{S}$.

Note that if any edge $a_{i}b_{j}$ in
$G_{S}[\\{a_{k+1},\cdots,a_{n}\\}\cup\\{b_{k+1},\cdots,b_{n}\\}]$ is not
covered by $X^{\prime}$, then the $a_{i}b_{j}$ is also not covered by $X$ in
$G$. All edges incident on $\alpha$ are also covered. Now suppose an edge of
the form $\beta a_{\ell}$ is not covered by $X^{\prime}$ for some
$\ell\in\\{a_{k+1},\cdots,a_{n}\\}$. Note that for this edge to be present in
$G_{S}$, by the definition of the contraction operation, there must have been
an edge of the form $b_{i}a_{\ell}$, for some $i\in[k]$. Note that if $\beta
a_{\ell}$ is not covered by $X^{\prime}$ then $b_{i}a_{\ell}$ is not covered
by $X$ in $G$ either, which contradicts our assumption that $X$ was a vertex
cover in $G$.

This shows that $G_{S}$ has an optimal vertex cover different from both
$A^{\prime}$ and $B^{\prime}$, but this contradicts our assumption that
$G_{S}$ was elementary to begin with. Therefore it must be the case that $G$
is also elementary.

######  Definition 2.22 (Alternating cycle).

Let $G$ be a connected bipartite graph with no degree $1$ vertex and a perfect
matching $M=\\{a_{1}b_{1},a_{2}b_{2},\ldots a_{n}b_{n}\\}$. We define a cycle
$a_{i_{1}}b_{i_{1}}a_{i_{2}}b_{i_{2}}\ldots b_{i_{k}}a_{i_{k}}a_{i_{1}}$ in
$G$ as an alternating cycle where $i_{1},i_{2},\ldots,i_{k}\in[n]$ and $2\leq
k\leq n$.

######  Proposition 2.23 (No alternating cycle).

Let $G$ be a maximal contraction graph. Then $G$ cannot contain any
alternating cycle.

######  Proof 2.24.

Let $G$ be a maximal contraction graph. It is clear that $G$ is a connected
bipartite graph with a perfect matching. Let
$M=\\{a_{1}b_{1},a_{2}b_{2},\ldots,a_{n}b_{n}\\}$ be a perfect matching of
$G$. If $n=1$, $G$ cannot contain any cycle and hence cannot contain any
alternating cycle. Let $n\geq 2$ and let
$C=a_{i_{1}}b_{i_{1}}a_{i_{2}}b_{i_{2}}\ldots b_{i_{k}}a_{i_{k}}a_{i_{1}}$ be
an alternating cycle in $G$. Let $S=V(C)$. Clearly $S$ is a special subset of
$V(G)$ and by Proposition 2.9 and Proposition 2.13, $S$ is a special
elementary subset of $V(G)$. This contradicts the fact that $G$ is a maximal
contraction graph. Thus $G$ cannot have an alternating cycle.

######  Proposition 2.25 (Structure of the Maximal Contraction).

Let $G$ be a maximal contraction graph. Then $G$ must have a degree $1$
vertex.

######  Proof 2.26.

Let $G$ be a maximal contraction graph. It is clear that $G$ is a connected
bipartite graph with a perfect matching. Let
$M=\\{a_{1}b_{1},a_{2}b_{2},\ldots,a_{n}b_{n}\\}$ be a perfect matching of
$G$. If $n=1$, then $G$ is a single edge and thus $G$ has a degree $1$ vertex.
Now let $n\geq 2$ and assume that $G$ has no degree $1$ vertices. Consider the
set $S=\\{a_{1},b_{1}\\}$. Since $b_{1}$ is not a degree $1$ vertex, we are
done. So there exits $a_{i_{1}}\neq a_{1}$ which is a neighbor of $b_{1}$. Add
$a_{i_{1}}$ and $b_{i_{1}}$ to $S$. Now for each $b_{i_{p}}$ for
$p=1,2,\ldots$, there exists $a_{p+1}$ which is a neighbor of $b_{i_{p}}$
because $G$ has no degree $1$ vertex or alternating cycle. Add $a_{p+1}$ and
$b_{p+1}$ to $S$. Thus $S$ will be an infinite set. But $S\subset V(G)$ which
is finite. Hence we have a contradiction. Thus $G$ must have a degree $1$
vertex.

To sum up the proof of Lemma 2.3: consider any connected bipartite graph $G$.
First we have shown that if $G$ is Spartan, it must have a perfect matching
and no degree one vertices. Therefore, a maximal contraction graph derived
from $G$ must be an edge. But note that an edge is elementary, and running the
contractions in reverse to recover $G$ preserves the property of the graph
being elementary, and we have the desired conclusion. We remark that our proof
shows that every connected bipartite graph with a Hamiltnonian cycle is
Spartan. However, it turns out that the converse is not true in the sense that
there exist connected bipartite graphs that are Spartan but do not have
Hamiltonian cycles: for instance, Figure 9 presents an example of a connected
bipartite Spartan graph that is not Hamiltonian.

$b_{1}$$a_{2}$$b_{2}$$a_{3}$$b_{3}$$a_{1}$$b_{4}$$a_{4}$ Figure 9: An example
of an elementary bipartite graph where the two independent sets are
$A=\\{a_{1},a_{2},a_{3},a_{4}\\}$ and $B=\\{b_{1},b_{2},b_{3},b_{4}\\}$ and
all the edges belong to one of the three perfect matchings:
$M_{1}=\\{a_{1}b_{1},a_{2}b_{2},a_{3}b_{3},a_{4}b_{4}\\},M_{2}=\\{a_{1}b_{3},a_{3}b_{2},a_{2}b_{1},a_{4}b_{4}\\}$
or $M_{3}=\\{a_{1}b_{1},a_{2}b_{4},a_{4}b_{3},a_{3}b_{2}\\}$. It can be
verified that this graph does not have a Hamiltonian cycle.

##  3 EVC with Extra Steps

Almost all of the proofs in the previous sections rely crucially on the fact
that a guard can only move one step after each attack. This gives rise to the
question that what happens if multiple moves are allowed? If retracing of
steps is allowed, then any guard can clean up an attack and come back to their
original position. Thus this problem will the same as the vertex cover problem
and hence it is not so interesting.

We define a variant of the Eternal Vertex Cover problem that we call _New
Eternal Vertex Cover_. Again we have a two player game with one player as “the
attacker” and the other player as “the defender”. Just like the Eternal Vertex
Cover problem, the defender initially places the guards on some of the
vertices of the graph (of his choice). The attacker attacks an edge. In
response to the attack, the defender can move each guards for at most _two_
steps without retracing. The constraint is however that the defense of the
attacked edge must happen in the first move itself, i.e., after the attack, at
least one guard who was present on one of the endpoints of the graph must move
across the attacked edge. If such a movement is not possible after a finite
sequence of attacks, the attacker wins; otherwise, if the defender has a
strategy to defend the graph $G$ against an infinite sequence of attacks, the
defender wins. There can only be one guard per vertex in the configuration
before the attack and the configuration after the attack is defended. However,
more than one guard can cross a vertex during the reconfiguration.

We define the _New Eternal Vertex Cover Number_ of a graph $G$ as the smallest
number of guards required in this new setting such that the defender has a
winning strategy. We denote this number by $nevc(G)$. It is clear that since
the defense must happen in the first step of a guard, if the vertices occupied
by guards do not form a vertex cover, the attacker wins. Therefore, we have
$mvc(G)\leq nevc(G)$ for any graph $G$. Also, since $evc(G)$ many guards can
defend an infinite sequence of attacks on a graph $G$ with each guard moving
just one step after each attack, it can be seen that for any graph $G$, we
have $nevc(G)\leq evc(G)$.

_Remark:_ These two inequalities imply that for any Spartan graph $G$, we have
$mvc(G)=nevc(G)=evc(G)$. However, there are graph classes where these
inequalities are not strict.

We show that computing the _New Eternal Vertex Cover_ number for a given graph
$G$ is $\mathsf{NP}$-hard in the next lemma. We use a reduction from the
_Vertex Cover_ problem. Given an input instance $(G,k)$ (where $|V(G)|=n$ and
$k<n-1$) of the _Vertex Cover_ problem, we construct an equivalent instance of
the _New Eternal Vertex Cover_ problem by adding a global vertex $\star$ to
the graph $G$, i.e., make the new vertex $\star$ adjacent to every other
vertex in $G$. It turns out that $G$ has a vertex cover of size $k$ if and
only if the defender has a winning strategy in the new setting using $k+1$
guards.

######  Lemma 3.1.

The _New Eternal Vertex Cover_ problem is $\mathsf{NP}$-hard.

######  Proof 3.2.

Given an input instance $(G,k)$ (where $|V(G)|=n$ and $k<n-1$) of the _Vertex
Cover_ problem, we construct an equivalent instance of the _New Eternal Vertex
Cover_ problem in polynomial time.

Construct a graph $H$ by adding a global vertex $\star$ to the graph $G$,
i.e., make the new vertex $\star$ adjacent to every other vertex in $G$. We
show that $G$ has a vertex cover of size $k$ if and only if the defender has a
winning strategy in the new setting using $k+1$ guards.

$\star$ Figure 10: Construction of the reduced instance from Vertex Cover to
the New Eternal Vertex Cover Problem. Graph $G$ is given in the blue box and
the new graph $H$ is obtained by adding a global vertex $\star$ to $G$.

Suppose $G$ has a vertex cover of size $k$, then consider the following
arrangement of $k+1$ guards: Place one guard on each vertex of a vertex cover
(of size $k$) and one guard on the global vertex $\star$. Now if the attacker
attacks an edge which has guards on both of its endpoints, the guards exchange
their positions and the configuration is restored.

Suppose an edge $uv$ is attacked such that $u$ belongs to the vertex cover and
$v$ does not, i.e., $u$ has a guard and $v$ does not, then the guard from $u$
goes to $v$ and the guard from $\star$ comes to $u$. The guard which is now on
$u$ can move one more step and thus moves to $\star$. Thus the initial
configuration is restored. This proves the forward direction.

$\star$ Figure 11: Suppose any edge in $G$ with exactly one endpoint in the
vertex cover is attacked, the guard from this vertex moves outside the vertex
cover along the attacked edge. The guard on the global vertex comes to the
vertex which was just vacated and the vertex cover is now restored. The guard
who had come just outside the vertex cover will now move to the global vertex.
Thus the configuration is restored.

For the reverse direction, consider an initial configuration of guards on $H$
in a winning strategy with $k+1$ guards. The vertices occupied by guards must
form a vertex cover of $H$ otherwise the attacker wins in the first move
itself. Any vertex cover of $H$ with $k+1$ guards must contain $\star$ because
$k+1<n$. Therefore, there must be $k$ guards on the vertices of $G$. If their
positions do not form a vertex cover, the attacker can attack an edge with
both the endpoints unoccupied and win. Thus $G$ has a vertex cover of size
$k$.

######  Lemma 3.3.

For any connected graph $G$, the defender has a winning strategy using
$mvc(G)+1$ guards, i.e., $nevc(G)\leq mvc(G)+1$ for any graph $G$.

######  Proof 3.4.

For any graph $G$, we give a winning strategy for the defender in the new
setting using $mvc(G)+1$ guards. We also refer the reader to Figure 12.

(a) An example graph.

(b) The edge AB is attacked.

(c) The guard on B moves to A.

(d) The guard on F moves to G…

(e) …and then to B.

(f) The guard on D moves to E…

(g) …and then to F.

(h) The (originallyextra) guard on C moves to D.

Figure 12: Demonstrating a defense with $mvc(G)+1$ many guards on a graph.

Let $mvc(G)=k$ and let $C_{1},C_{2},\ldots,C_{q}$ be the connected components
of the subgraph induced by the vertices of a $k$-sized vertex cover of $G$.
Place one guard on each of these vertices of this vertex cover (say $S$) and
one guard in the independent set (say on the vertex $w$).

Now suppose some edge is attacked such that both its endpoints have guards,
then the guards can exchange places and the configuration is restored.

Suppose some edge $uv$ is attacked such that $u\in S$ and $v\in V(G)\setminus
S$. Then the guard on $u$ moves to $v$. Suppose $w$ is adjacent to some vertex
which lies in the same connected component of $S$ as $w$, then the guards can
each move one step along a path from $w$ to $u$ such that there is a guard on
$u$ and all the vertices of $S$ at the end of this movement and now no guard
on $w$. But we still have all the vertices of $S$ with one guard each and one
guard in the independent set (now on $v$). Thus we have a configuration just
like the initial configuration and each strategy can be implemented here
accordingly.

Suppose $u$ and any neighbour of $w$ do not lie in the same connected
component of $S$. As $G$ is connected, there is a path from $w$ to $u$ in $G$
and this path contains some vertices of $V(G)\setminus S$. Let this path be
$w=u_{1}u_{2}\ldots u_{\ell}=u$. We trigger a movement of guards along this
path as follows: If $u_{\ell-1}$ has a guard, this guard moves to $u$,
otherwise $u_{\ell-2}$ must have a guard because $S$ is a vertex cover. This
guard moves to $u_{\ell-1}$ and then to $u$. Similarly for each $u_{i}\in S$
where $i\in\\{\ell-2,\ell-3,\ldots,2\\}$, if $u_{i-1}$ has a guard, the guard
on $u_{i-1}$ moves to $u_{i}$. Otherwise $u_{i-2}$ must have a guard (because
$S$ is a vertex cover) which moves to $u_{i-1}$ and then to $u_{i}$. It can be
observed that at the end of this movement, all vertices in $S$ have a guard
and $v$ has a guard and $w$ does not have a guard. Therefore, we have the same
situation as before where all the vertices in the vertex cover have a guard
and one guard outside the vertex cover. Thus we have shown that $mvc(G)+1$
many guards are sufficient to defend $G$ against any sequence of attacks in
this new setting.

######  Lemma 3.5.

If $G$ is any graph without a degree-$1$ vertex, then $nevc(G)=mvc(G)$.

######  Proof 3.6.

It is sufficient to show that $nevc(G)\leq mvc(G)$, i.e., the defender has a
winning strategy using $mvc(G)$ many guards. Also it is sufficient to only
look at connected graphs.

Let $mvc(G)=k$ and let $S$ be a minimum sized vertex cover of $G$. The
defender places one guard on each vertex of $S$. If any edge with both
endpoints in $S$ is attacked, then the guards exchange their positions and we
are back to the same configuration.

Suppose any edge $uv$ such that $u\in S$ and $v\notin S$ is attacked. The
guard on $u$ moves to $v$. Since $v$ is not a degree $1$ vertex, it must have
a neighbour $w$ other than $u$. Depending on whether $w$ and $u$ lie in the
same connected component in $G[S]$ or not, we can trigger a movement of guards
just like the proof of Lemma 3.3 such that each guard moves at most two steps
and there is no guard on $v$ at the end of this movement and there is a guard
on $u$. Thus the vertex cover $S$ is restored and we have a winning strategy
using $mvc(G)$ many guards.

######  Lemma 3.7.

For any graph $G$, $nevc(G)=mvc(G)$ if and only if for each degree-$1$ vertex
$v$ of $G$, there exists a minimum sized vertex cover $S_{v}$ of $G$ which
contains $v$.

######  Proof 3.8.

Let $G$ be a graph such that $mvc(G)=k$ and there exists a degree-$1$ vertex
$v$ such that no $k-$sized vertex cover of $G$ contains $v$. Let $u$ be the
neighbour of $v$, then any minimum sized vertex cover of $G$ must contain $u$.
Therefore, in the initial configuration there must be a guard on $u$ and no
guard on $v$. If the attacker attacks the edge $uv$, then the defender must
move the guard on $u$ to $v$. Since $v$ has no other neighbour than $u$ and
retracing is not allowed, the guard on $v$ cannot move anywhere else. Now
since there is no vertex cover of size $k$ which contains $v$, the guards
cannot reconfigure to form a vertex cover, no matter how the other guards
arrange themselves. Thus $mvc(G)$ many guards are not sufficient to protect
$G$ and thus $nevc(G)\neq mvc(G)$.

Now suppose that for every degree-$1$ vertex $v$ of $G$, there exists a
minimum sized vertex cover $S_{v}$ of $G$ which contains $v$. Let the size of
the minimum sized vertex cover of $G$ be $k$. We now describe a strategy to
defend an attack on $G$ with $k$ guards. Place each guard on a vertex of a
minimum sized vertex cover (say $S$) of $G$. Without loss of generality, we
assume that some edge $uv$ such that $u\in S$ and $v\notin S$ is attacked. The
guard on $u$ is forced to move to $v$. If $v$ is a vertex with degree $2$ or
more, then we mimic the strategy in Lemma 3.3 to get all the guards back on
$S$. If $v$ is a degree-$1$ vertex, we show that it is possible to transfer
the guards from $S$ to $S_{v}$ (where $S_{v}$ is the minimum sized vertex
cover containing $v$).

Denote $S\cap S_{v}$ by $P$ and $(V(G)\setminus S\cap S_{v})\setminus\\{v\\}$
by $Q$. Here $P$ are the vertices which need to retain a guard and $Q$ are the
vertices which need to gain a guard in order to reconfigure from $S$ to
$S_{v}$. Let $|P|=p$ and $|Q|=q$. Clearly $p+q+1=k$, i.e., $k-p=q+1$.
Therefore $|S\setminus P|=|Q\cup\\{v\\}|$. We show that there is a perfect
matching between these two sets. Notice that there cannot be an edge with both
endpoints in $S\setminus P$ because these vertices are not in $S_{v}$ and
$S_{v}$ is a vertex cover. Suppose there is no perfect matching between
$S\setminus P$ and $Q\cup\\{v\\}$, then there exists a set $A\in S\setminus P$
such that $|N(A)\cap(Q\cup\\{v\\})|<|A|$. But this is not possible as
$(S\setminus P)\setminus A\cup N(A)$ will be a vertex cover of $G$ of size
less than $k$. Thus there exists a perfect matching between $S\setminus P$ and
$Q\cup\\{v\\}$ which can be used to reconfigure the guards from $S$ to
$S_{v}$.

######  Corollary 3.9.

There exists a polynomial time algorithm for finding the _New Eternal Vertex
Cover_ number on bipartite graphs.

######  Proof 3.10.

Suppose we have a bipartite graph $G$ with $mvc(G)=k$. Any minimum sized
vertex cover cannot contain both the degree-$1$ vertex and its neighbour. As
shown in Lemma 3.7, we need to check if for each degree-$1$ vertex $v$ of $G$,
whether there exists a vertex cover of size $k$ of $G$ which contains $v$,
i.e., whether there exists a vertex cover of size $k-1$ of $G[V(G)\setminus
N[v]]$.

Since the number of degree-$1$ vertices is bounded by the total number of
vertices and the subgraph of a bipartite graph is bipartite and vertex cover
is polynomial time solvable on bipartite graphs, we have a polynomial time
algorithm for checking if $nevc(G)=mvc(G)$ or not if $G$ is bipartite.

Since $nevc(G)\leq mvc(G)$ for all graphs $G$, if for some bipartite graph
$nevc(G)\neq mvc(G)$, then we have $nevc(G)=mvc(G)+1$. Thus we can determine
the _New Eternal Vertex Cover_ number of a graph in polynomial time.

Note that if we allow the guards to move for an arbitrary number of steps
without retracing after each attack, Lemma 3.7 still holds, i.e., there are
families of graphs (for instance, star graphs) such that even allowing the
guards to move for an arbitrary number of steps does not make them “Spartan”
in the new setting. Thus the power of one extra step subsumes the power of any
number of additional steps.

##  4 Concluding Remarks

We showed that a natural sufficient condition for when a graph is Spartan
(i.e, when $evc(G)=mvc(G)$) is also necessary in the context of bipartite
graphs. Motivated by our proof we extend the notion of eternal vertex cover to
a variant where the guards are allowed to move more than one step on their
turn, and completely characterize the number of guards needed in terms of mvc:
indeed, we show that one extra guard suffices, and is needed only if the graph
has a degree one vertex that is not contained in any minimum vertex cover.

It would be interesting to see what happens if the defense can happen in the
second step of a guard. We also showed that while the new variant remains
computationally hard, unlike the original problem, it is in fact solvable in
polynomial time on bipartite graphs. Generalizing our structural results
beyond bipartite graphs is an interesting direction for future work.

## References

  * [1] Hisashi Araki, Toshihiro Fujito, and Shota Inoue.  On the eternal vertex cover numbers of generalized trees.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 98-A(6):1153–1160, 2015.
  * [2] Jasine Babu, L. Sunil Chandran, Mathew C. Francis, Veena Prabhakaran, Deepak Rajendraprasad, and J. Nandini Warrier.  On graphs with minimal eternal vertex cover number.  In Sudebkumar Prasant Pal and Ambat Vijayakumar, editors, Proceedings of the 5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM, volume 11394 of Lecture Notes in Computer Science, pages 263–273. Springer, 2019.
  * [3] Jasine Babu, L. Sunil Chandran, Mathew C. Francis, Veena Prabhakaran, Deepak Rajendraprasad, and Nandini J Warrier.  On graphs whose eternal vertex cover number and vertex cover number coincide.  Discrete Applied Mathematics (in press), 2021.
  * [4] Reinhard Diestel.  Graph theory.  Springer, 2017.
  * [5] Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Dieter Kratsch, and Saket Saurabh.  Parameterized algorithm for eternal vertex cover.  Information Processing Letters, 110(16):702–706, 2010.
  * [6] Gábor Hetyei.  Rectangular configurations which can be covered by 2$\times$ 1 rectangles.  Pécsi Tan. Foisk. Közl, 8:351–367, 1964.
  * [7] William Klostermeyer and Christina M. Mynhardt.  Graphs with equal eternal vertex cover and eternal domination numbers.  Discrete Mathematics, 311(14):1371–1379, 2011.
  * [8] William F. Klostermeyer and Christina M. Mynhardt.  Edge protection in graphs.  Australas. J Comb., 45:235–250, 2009.
  * [9] László Lovász and Michael D Plummer.  Matching theory, volume 367.  American Mathematical Soc., 2009.


# An integrated recurrent neural network and regression model with spatial and
climatic couplings for vector-borne disease dynamics

Zhijian Li 1, Jack Xin1 and Guofa Zhou2
1 Department of Mathematics, UC Irvine, Irvine, CA 92617, USA
2Program in Public Health, School of Medicine, UC Irvine, Irvine, CA 92617,
USA.
{zhijil2,jack.xin<EMAIL_ADDRESS>

###### Abstract

We developed an integrated recurrent neural network and nonlinear regression
spatio-temporal model for vector-borne disease evolution. We take into account
climate data and seasonality as external factors that correlate with disease
transmitting insects (e.g. flies), also spill-over infections from neighboring
regions surrounding a region of interest. The climate data is encoded to the
model through a quadratic embedding scheme motivated by recommendation
systems. The neighboring regions’ influence is modeled by a long short-term
memory neural network. The integrated model is trained by stochastic gradient
descent and tested on leishmaniasis data in Sri Lanka from 2013-2018 where
infection outbreaks occurred. Our model out-performed ARIMA models across a
number of regions with high infections, and an associated ablation study
renders support to our modeling hypothesis and ideas.

Figure 1: Sri Lanka regional map and mean incidence rate over the last two
decades.

##  1 Introduction

Leishmaniases are tropical diseases caused by leishmania parasites and
transmitted through the bites of vector sand flies. The cutaneous
leishmaniasis (CL) is the most common threat and health risk in developing
countries in the tropical regions. In this paper, we study data from Sri Lanka
that has reported a substantial surge in clinical leishmaniasis cases in the
past 20 years (Fig.1, a)). Previous studies Siriwardana et al. [2010],
Karunaweera et al. [2018] found that (1) leishmaniasis epidemics in Sri Lanka
had two transmission hot spots, one on the south coast and another in the
north central region of the country (Fig.1,b)), with a biannual seasonal
variation; (2) outdoor activities, including occupational exposure and living
near a vector breeding area, are some of the key risk factors of infection. An
important scientific task for public health is to model the spatio-temporal
dynamics in leishmaniasis transmission and the driving forces behind it,
thereby help predict future infections and outbreaks.

In this paper, we aim to generalize and advance existing geo-statistical and
ecological models Kyriakidis and Journel [1999], Elith and Leathwick [2009] by
incorporating spatio-temporal transmission factors such as climate effects and
local carryover of infections from neighboring regions. Our main contributions
are:

(1) modeling leishmaniasis spread between neighboring areas by a recurrent
neural network with input data from up to three most infected neighbors;

(2) including climate data input as an external factor, since the development
of both the sand flies and the parasites inside their guts are affected by
climatic conditions;

(3) hybridizing (1) and (2) with regression to form an integrated nonlinear
space-time model trained by stochastic gradient descent on 51 months (2013-03
to 2017-08) and tested on 18 months (2017-09 to 2018-12) in 5 highly infected
regions of Sri Lanka.

The rest of the paper is organized as follows. In section 2, we review related
prior work on infectious disease modeling where climate and geo-neighbor
factors have been separately modeled. In section 3, we outline pre-processing
of raw data to remove trend, and introduce our integrated model structure with
embedding operations of climate and time stamps (monthly) motivated by design
of recommender systems. In section 4, we go over training and test data, and
compare prediction results with ARIMA as baseline. In terms of both root mean
squares error and maximum absolute error, our integrated model, when applied
on the difference input data, out-performed ARIMA significantly in 5 Sri Lanka
regions with high infections. Moreover, adding climate data consistently
improves prediction, which supports climate as a strong correlate to fly and
parasite mediated transmissions.

(a)

(b)

Figure 2: An example of data pre-processing for region Kurunegala: a) raw and
transformed (differenced) data; (b) transformed (differenced) and normalized
data.

##  2 Related Prior Works

Forecasting of disease time series has gone far beyond the traditional
regression approach. External information has been widely used in models; for
example, Yang et al. [2015] proposed Auto-Regression method with GOogle search
data (ARGO) that used google search information as additional regressors. The
intuition of ARGO is that the amount of searches of influenza and related key
words indicate the outbreak of influenza. Utilizing this external internet
search information, ARGO outperforms auto-regressive model and its variant
ARIMA on CDC influenza data. Unfortunately, Google Correlate, the website
where Google provided the internet search data, has been shut down for many
years. Motivated by the infectious nature of the influenza, Li et al. [2019]
proposed graph-structured recurrent neural networks (SRNN) to learn the
interaction of geographical spread of influenza. As a result, SRNN further
improves ARGO’s accuracy on CDC data. Recently, spatio-temporal models
combining epidemic differential equations and RNNs Li et al. [2020], Zheng et
al. [2020] have been proposed for one to seven day ahead forecasting of
Covid-19 cases in Italy and the US. For vector-borne diseases, due to the
difficulty of tracking fly populations and evolution, mixed linear regression-
autoregression models with near-neighbor spatial coupling has been commonly
used for prediction and risk analysis Kyriakidis and Journel [1999], Elith and
Leathwick [2009].

##  3 Our Approach

###  3.1 Transformation of Raw Data

Since the original leishmaniasis data is highly non-stationary Chaves and
Pascual [2006], we first transform (pre-process) it to be approximately
stationary. There are several popular techniques to stationarize data. We
found that taking the first order difference along time is effective to
improve the stationarity of the raw data here. In Fig. 2, panel (a) shows how
the original case data of Kurunegala region is transformed by the difference
method. As is well-known that RNN is sensitive to normalization, panel (b)
shows the normalized-transformed data that will be fed into our model. We
remark that normalization is a stationary-invariant process.

###  3.2 Basic Space-Time Model

In classical space-time geological and ecological statistical modeling
(Kyriakidis and Journel [1999], Elith and Leathwick [2009] among others), the
cases of neighbors are summed as a single regressor. To learn the impact of
neighbors more at depth, we use RNN to process such information and extract
(“edge”) features as in Li et al. [2020], Zheng et al. [2020]. Let
$\mathbf{y}_{e,t}=(y^{1}_{t-1},y^{2}_{t-1},y^{3}_{t-1})$ be a vector of
observations from the three neighbors that have the highest cases at $t-1$.
Define:

$h_{t}=LSTM(\mathbf{y}_{e,t})$ $f_{t}=w^{T}h_{t}$

where LSTM is a standard long short-term memory network Hochreiter and
Schmidhuber [1997]. If a region has less than three neighbors, we pad zero
into $\mathbf{y}_{e}$. Let $I$ be the set of neighbors, then the model output
(an estimated case number for a region of interest at time $t$) is:

$\hat{y}_{t}=\sigma\big{(}\alpha y_{t-1}+\beta\sum_{i\in
I}y^{i}_{t-1}+f_{t}+b\big{)},$ (1)

where $\sigma:=\max(x,0)$ is the rectified linear unit (ReLu) activation
function.

Figure 3: Normalized data of cases vs. mean temperature and precipitation in
Kurunegala region of Sri Lanka. Figure 4: Illustration of our model
architecture (viz. equation (2)).

###  3.3 Integrated Model

According to previous studies ( Zhou et al. [2004], Chaves and Pascual [2006]
among others), leishmaniasis outbreak is highly correlated to climate
conditions such as temperature, rainfalls and seasonality, see Fig. 3 and Fig.
5 for illustrations. Hence, we adopt climate data as an external feature to
further improve our model performance. The climate data, denoted as
$\mathbf{v}_{t}\in\mathbb{R}^{4}$ being part of our model input, contains the
maximum temperature, minimum temperature, mean temperature, and precipitation
during month $t$. Unfortunately, RNN is not good at directly learning the
impact of external feature $\mathbf{v}_{t}$ based on our experiments. The
temperature effect turns out to be highly non-linear. Hence, we set out to
learn the order-2 interactions of the climate features. The complete order-2
interactions of $n$ features involve ${n\choose 2}+n$ additional features,
which are expensive to compute and can easily lead to over-fitting. Similar
problem arises in capturing high-order interactions of user-item features in
recommendation systems where the so-called cross layer method Wang et al.
[2017] is proposed through Hadamard product and a weight matrix and the
interaction is encoded into a vector of length $n$. As in Wang et al. [2017],
we compute the order 2 interaction of climate features as follows:

$(W\mathbf{v})\odot\mathbf{v}=\begin{bmatrix}w_{11}v_{1}^{2}+w_{12}v_{1}v_{2}+w_{13}v_{1}v_{3}+w_{14}v_{1}v_{4}\\\
w_{21}v_{1}v_{2}+w_{22}v_{2}^{2}+w_{23}v_{1}v_{3}+w_{24}v_{2}v_{4}\\\
w_{31}v_{1}v_{3}+w_{32}v_{2}v_{3}+w_{33}v_{3}^{2}+w_{34}v_{3}v_{4}\\\
w_{41}v_{1}v_{4}+w_{42}v_{2}v_{4}+w_{43}v_{3}v_{4}+w_{44}v_{4}^{2}\end{bmatrix}$

Once the order interaction of climate features has been encoded in
$(W\mathbf{v}\odot\mathbf{v})$, we use a dense layer to map the interaction of
climate data into the final prediction:

$\psi(\mathbf{v})=\tilde{w}^{T}[(W\mathbf{v}\odot\mathbf{v})].$

In addition to external features, capturing seasonality has drawn much
attention in recent literature Taylor and Letham [2018], Zhou et al. [2004] of
time-series forecasting. A classical analytical approach is to use partial
sums of Fourier series to represent seasonality. However, the performance
relies on fine tuning a non-trainable integer parameter (the number of terms).
Instead, in view of the personalization technique of recommendation system He
et al. [2017], we employ an embedding layer to map the month ID, 0 to 11, to a
higher dimension to learn seasonality of the data. Then, we use a dense layer
to map it into the output:

$g(t)=\hat{w}^{T}(\text{embed(t)}).$

Integrated with the climate features and seasonality, our model is formulated
as:

$\hat{y}_{t}=\sigma\big{(}\alpha y_{t-1}+\beta\sum_{i\in
I}y^{i}_{t-1}+f_{t}+g(t)+\psi(\mathbf{v_{t}})+b\big{)}.$ (2)

The architecture of our model is illustrated in Fig. 6. As shown in equation
(2), the final prediction model is written as the sum of all learned
information followed by ReLu activation function. The training loss function
is

$\mathcal{L}(\Theta)=\sum_{t=1}^{N}(\hat{y}_{t}-y_{t})^{2}$

which is minimized by an adaptive Adam optimizer to arrive at an optimal value
$\Theta^{*}$.

##  4 Experimental Results

Our clinically confirmed leishmaniasis case data came from from the national
diagnostic and research laboratory at the University of Colombo, Sri Lanka;
the epidemiology unit of the Sri Lanka Ministry of Health and through
communication with medical health officers. The climatic data came from
meteorological stations in Sri Lanka in the format of maximum/minimum/mean
temperature and precipitation. We use 51 months (2013-03 to 2017-08) for
training and 18 months (2017-09 to 2018-12) for testing, with ARIMA as our
baseline model. We set the standard parameters of ARIMA as $(p,q,d)=(2,1,1)$
after optimizing. Note that with $d=1$, ARIME also applied difference
transform to the original data. Meanwhile, we compare the performance of our
base model equation (1) and the integrated model equation (2). The results are
shown in Table 1 and Table 2. We evaluate the models using both MAE and RMSE
metrics. Let $\mathbf{e}=\\{e_{i}|e_{i}=|\hat{y}_{t}-y_{t}|,i\leq n\\}$, where
$n$ is the number of data points in testing set. Then,

$\text{MAE}=\sum_{i=1}^{n}\frac{|e_{i}|}{n}$
$\text{RMSE}=\sqrt{\sum_{i=1}^{n}\frac{e_{i}^{2}}{n}}$

We note that RMSE $\geq$ MAE, and it can be shown that RMSE$-$MAE
$=\text{Var}(\mathbf{e})$. We observe that equation (1) outperforms ARIMA
model in both MAE and RMSE prediction errors.

Figure 5: Seasonality component $g(t)$ of Polonnaruwa Region | (1) | (2) | ARIMA
---|---|---|---
Matara | 11.38 | 11.36 | 11.92
Anuradhapura | 14.70 | 12.81 | 14.70
Polonnaruwa | 8.65 | 8.04 | 8.65
Kurunegala | 14.70 | 10.08 | 10.35
Hambantota | 32.76 | 32.12 | 34.63
Table 1: RMSE prediction errors of different models Region | (1) | (2) | ARIMA
---|---|---|---
Matara | 9.33 | 8.62 | 9.54
Anuradhapura | 10.25 | 9.88 | 12.2
Polonnaruwa | 7.20 | 6.08 | 7.57
Kurunegala | 17.50 | 16.80 | 17.50
Hambantota | 41.28 | 39.77 | 41.28
Table 2: MAE errors of different models

Equation (2) performs the best among the three models. Hence, the edge
features in cases of neighboring regions helped model (1) to outperform ARIMA,
which is only based on historical observations of the region of interest. The
external climate (see Fig. 5 for a seasonality illustration) information helps
model (2) to further improve prediction.

##  5 Conclusion

In this study, we integrated components of geographical spatial information,
temperature, and seasonality to build a spatio-temporal network model for
predicting vector-borne disease cases. We employ the cross layer from
recommendation system to compute the order-2 interaction of climate data, and
utilize embedding layer to map month ID to higher dimensions to learn
seasonality. The model is successfully trained on leishmaniasis data of
several regions in Sri Lanka with high infections (see Fig. 6).

In future work, we plan to study other vector-borne disease data with our
model (2), and also generalize RNN to an efficient transformer model to
explore additional non-local temporal information for improving prediction.

As suggested in Fig. 3, the effects of climatic data may have a latent period
to induce vector growth and subsequent case upswing. In future work, we plan
to introduce a time delay in the climate term of our model and learn it from
the data for another improvement.

##  6 Acknowledgements

This work was partially supported by NSF grants DMS-1924548 and DMS-1952644.

Figure 6: Training and prediction (separated by dashed line) of models (1) and
(2) vs. ARIMA in 4 regions of Sri Lanka.

## REFERENCES

  * Chaves and Pascual [2006] L. Chaves and M. Pascual.  Climate cycles and forecasts of Cutaneous Leishmaniasis, a nonstationary vector-borne disease.  _PLoS Med. 3(8):e295_ , 2006.
  * Elith and Leathwick [2009] J. Elith and J. Leathwick.  Species distribution models: ecological explanation and prediction across space and time.  _Ann. Rev. Ecol. Evol. Syst._ , 40:677–97, 2009.
  * He et al. [2017] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T.-S. Chua.  Neural collaborative filtering.  In _Proceedings of the 26th International Conference on World Wide Web_ , pages 173–182, 2017.
  * Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Karunaweera et al. [2018] N. Karunaweera, S. Ginige, S. Senanayake, H. Silva, N. Manamperi, N. Samaranayake, and et al.  Spatial epidemiologic trends and hotspots of Leishmaniasis in Sri Lanka (2001-2018).  _Emerg. Infect. Disease 26(1):1–10_ , 2018.
  * Kyriakidis and Journel [1999] P. Kyriakidis and A. Journel.  Geostatistical space–time models: a review.  _Math Geol._ , 31:651–84, 1999.
  * Li et al. [2019] Z. Li, X. Luo, B. Wang, A. L. Bertozzi, and J. Xin.  A study on graph-structured recurrent neural networks and sparsification with application to epidemic forecasting.  In _World Congress on Global Optimization_ , pages 730–739. Springer, 2019.
  * Li et al. [2020] Z. Li, Y. Zheng, J. Xin, and G. Zhou.  A recurrent neural network and differential equation based spatiotemporal infectious disease model with application to Covid-19.  _Proceedings of KDIR 2020; arXiv preprint arXiv:2007.10929_ , 2020\.
  * Siriwardana et al. [2010] H. Siriwardana, N. Thalagala, and N. Karunaweera.  Clinical and epidemiological studies on the cutaneous leishmaniasis caused by Leishmania Donovani in Sri Lanka.  _Ann. Trop. Med. Parasitol. 104(3):213–223_ , 2010.
  * Taylor and Letham [2018] S. J. Taylor and B. Letham.  Forecasting at scale.  _The American Statistician_ , 72(1):37–45, 2018\.
  * Wang et al. [2017] R. Wang, B. Fu, G. Fu, and M. Wang.  Deep & cross network for ad click predictions.  In _Proceedings of the ADKDD’17_ , pages 1–7. 2017.
  * Yang et al. [2015] S. Yang, M. Santillana, and S. C. Kou.  Accurate estimation of influenza epidemics using google search data via argo.  _Proceedings of the National Academy of Sciences_ , 112(47):14473–14478, 2015.
  * Zheng et al. [2020] Y. Zheng, Z. Li, J. Xin, and G. Zhou.  A spatial-temporal graph based hybrid infectious disease model with application to COVID-19.  _Proceedings of ICPRAM 2021; arXiv preprint arXiv:2010.09077_ , 2020\.
  * Zhou et al. [2004] G. Zhou, N. Minakawa, A. K. Githeko, and G. Yan.  Association between climate variability and malaria epidemics in the east African highlands.  _Proceedings of the National Academy of Sciences_ , 101(8):2375–2380, 2004.