Eternal Vertex Cover on Bipartite Graphs

Abstract

The Eternal Vertex Cover problem is a dynamic variant of the vertex cover problem. We have a two player game in which guards are placed on some vertices of a graph. In every move, one player (the attacker) attacks an edge. In response to the attack, the second player (the defender) moves some of the guards along the edges of the graph in such a manner that at least one guard moves along the attacked 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.

The minimum number of guards with which the defender has a winning strategy is called the eternal vertex cover number of the graph G. On general graphs, the computational problem of determining the minimum eternal vertex cover number is $\mathsf {NP}$-hard and admits a 2-approximation algorithm and an exponential kernel. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel.

We settle both these questions by showing that Eternal Vertex Cover is $\mathsf {NP}$-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.

Dedicated to the memory of Professor Rolf Niedermeier.

The second author acknowledges support from the SERB-MATRICS grant MTR/2017/001033 and IIT Gandhinagar. The third author acknowledges support from CSIR.

1 Introduction

The Eternal Vertex Cover problem is a dynamic variant of the vertex cover problem introduced by Klostermeyer and Mynhardt (2009). The setting is the following. We have a two player game—between players whom we will refer to as the attacker and defender—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 involve 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 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 Fig. 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).

Fig. 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. Therefore, it is clear that $evc(G)\ge mvc(G)$, where mvc(G) denotes the minimum size of a vertex cover of G. It also turns out that twice as many vertices as the mvc(G) also suffice the defend against any sequence of attacks. This might be achieved, for example, 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 $\textsc {Eternal Vertex Cover}$ was obtained by Fomin et al. (2010). This also implies $mvc(G)\le evc(G) \le 2mvc(G)$.

Klostermeyer and Mynhardt (2009) gave a characterization of the graphs for which the upper bound is achieved. A characterization for graphs for which lower bound is achieved remains open, but several special cases have been addressed in the literature (see, for instance Babu et al. 2021a). Also, Klostermeyer and Mynhardt (2011) study graphs with equal eternal vertex cover and eternal domination numbers, which is a closely related dynamic variant of the dominating set problem.

The natural computational question associated with this parameter is the following: given a graph G and a positive integer k, determine if $evc(G) \le k$. The problem is only known to be in PSPACE in general. Fomin et al. (2010) show that this problem is NP-hard by a reduction from vertex cover, and admits a 2-approximation algorithm based on both endpoints of a maximum matching. They also study the problem from a parameterized perspective. In parameterized complexity, one asks if for an instance of size n and a parameter k, a problem can be solved in time $f(k) n^{\mathcal {O}(1)}$ where f is an arbitrary computable function independent of n. Problems that can be solved in that time are said to be fixed parameter tractable, and the corresponding complexity class is called FPT. They show that the problem is fixed parameter tractable when parameterized by the number of available guards k, by demonstrating an algorithm with running time $\mathcal {O}\left( 2^{O\left( k^{2}\right) }+n m\right)$ for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. This work leaves open the question of whether Eternal Vertex Cover admits a polynomial kernel¹.

The computational question of Eternal Vertex Cover is also well studied on special classes of graphs. For instance, it is known to be NP-complete when restricted to locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs (Babu et al. 2021a). It can also be solved in linear time on the class of cactus graphs (Babu et al. 2021b), quadratic time on chordal graphs (Babu and Prabhakaran 2021; Babu et al. 2021b) and in polynomial time on “generalized” trees (Araki et al. 2015). However, the complexity of the problem on biparitite graphs remains open, and is an intriguing question especially considering that the vertex cover problem is tractable on biparitite graphs.

1.1 Our Contributions

We resolve the question of the complexity of Eternal Vertex Cover on bipartite graphs by showing NP-hardness even on bipartite graphs of constant diameter. It turns out that the same result can also be used to argue the likely non-existence of a polynomial compression, which resolves the question of whether Eternal Vertex Cover has a polynomial kernel in the negative. Finally, we also observe that the hardness results carry over to the related problem of Eternal Connected Vertex Cover (Fujito and Nakamura 2020), where we would like the vertex covers at every step to induce connected subgraphs.

Summarizing, our main result is the following:

Theorem 1 (EVC on Bipartite Graphs)

Both the Eternal Vertex Cover and Eternal Connected Vertex Cover problems are $\mathsf {NP}$-hard and do not admit a polynomial compression parameterized by the number of guards (unless $\mathrm {NP} \subseteq {\text {coNP}}/\text {poly}$), even on bipartite graphs of diameter six.

We also show that Eternal Vertex Cover is tractable on the class of cobipartite graphs.

Theorem 2 (EVC on Co-Bipartite Graphs)

There is a quadratic-time algorithm for Eternal Vertex Cover on the class of cobipartite graphs.

Organization. We establish notation and provide relevant definitions in Sect. 2. The proof of Theorem 1 follows from the construction described in Lemma 1, and is the main focus of Sect. 3, while the proof of Theorem 2 can be found in Sect. 4. In Sect. 5, we suggest some directions for further work.

2 Preliminaries and Notations

All graphs in this paper are finite, undirected and without multiple edges and loops. For terminology not defined in this paper we refer to Diestel (2017).

Let $G=(V,E)$ be a graph. We will typically use n and m to denote |V| and |E|, respectively. The set of neighbours of a vertex v in G is denoted by $N_{G}(v)$, or briefly by N(v)². More generally, for $U \subseteq V$, the neighbours in $V \backslash U$ of vertices in U are called neighbours of U; their set is denoted by N(U). A subset $S \subseteq V$ is said to be independent if for all $u, v \in S$, $(u,v) \notin E$.

A path is a non-empty graph $P=(V,E)$ of the form $V=\left\{ x_{0}, x_{1}, \ldots , x_{k}\right\}$ and $E=\left\{ x_{0} x_{1}, x_{1} x_{2}, \ldots , x_{k-1} x_{k}\right\}$, where the $x_{i}$’s are all distinct. The number of edges of a path is its length, and the path of length k is denoted by $P^{k}$. The distance $d_{G}(x, y)$ in G of two vertices x, y is the length of a shortest $x-y$ path in G; if no such path exists, we set $d(x, y):=\infty$. The greatest distance between any two vertices in G is the diameter of G, denoted by ${\text {diam}}(G)$.

A vertex cover of a graph $G = (V,E)$ is a subset S of the vertex set such that every edge has at least one of its endpoints in S. Note that $V \setminus S$ is an independent set. We use ${\text {mvc}}(G)$ to denote the size of a minimum vertex cover of G. A dominating set of a graph G is a subset X of the vertex set such that every vertex of G either belongs to X or has a neighbor in X.

Consider a graph $G=(V, E)$ on n vertices and m edges. Guards are placed on the vertices of the graph in order to protect it from an infinite sequence (which is not known to the guards in advance) of attacks on the edges of the graph. In each round, one edge $u v \in E$ is attacked, and each guard either stays on the vertex it is occupying or moves to a neighboring vertex.

Moreover, the guards are bound to move in such a way that at least one guard moves from u to v or from v to u. The minimum number of guards which can protect all the edges of G is called the eternal vertex cover number of G and is denoted by ${\text {evc}}(G)$.

A bipartite graph is a graph whose vertex set can be partitioned into at most two independent sets. A co-bipartite graph is a graph which is the complement of a bipartite graph. In other words, a co-bipartite graph is a graph whose vertex set can be partitioned into at most two cliques.

Parameterized Complexity. A parameterized problem L is a subset of $\Sigma ^{*} \times \mathbb {N}$ for some finite alphabet $\Sigma$. An instance of a parameterized problem consists of (x, k), where k is called the parameter. A central notion in parameterized complexity is fixed parameter tractability (FPT), which means for a given instance (x, k) solvability in time $f(k) \cdot p(|x|)$, where f is an arbitrary function of k and p is a polynomial in the input size. The notions of kernelization and compression are defined as follows.

Definition 1

A kernelization algorithm, or in short, a kernel for a parameterized problem $Q \subseteq \Sigma ^{*} \times \mathbb {N}$ is an algorithm that, given $(x, k) \in \Sigma ^{*} \times \mathbb {N}$, outputs in time polynomial in $|x|+k$ a pair $\left( x^{\prime }, k^{\prime }\right) \in \Sigma ^{*} \times \mathbb {N}$ such that (a) $(x, k) \in Q$ if and only if $\left( x^{\prime }, k^{\prime }\right) \in Q$ and (b) $\left| x^{\prime }\right| +k^{\prime } \le g(k)$, where g is an arbitrary computable function. The function g is referred to as the size of the kernel. If g is a polynomial function then we say that Q admits a polynomial kernel.

Definition 2

A polynomial compression of a parameterized language $Q \subseteq \Sigma ^{*} \times \mathbb {N}$ into a language $R \subseteq \Sigma ^{*}$ is an algorithm that takes as input an instance $(x, k) \in \Sigma ^{*} \times \mathbb {N}$, works in time polynomial in $|x|+k$, and returns a string y such that:

• 1. $|y| \le p(k)$ for some polynomial $p(\cdot )$, and

• 2. $y \in R$ if and only if $(x, k) \in Q$.

Our focus in this paper is the Eternal Vertex Cover problem, in which we are interested in computing ${\text {evc}}(G)$ for a graph G, and its parameterized complexity with respect to the number of guards:

Eternal Vertex Cover is known to admit an exponential kernel of size $4^{k}(k+1)+2 k$ (Fomin et al. 2010). We use the following standard framework to show that it is unlikely to admit a polynomial compression.

Definition 3

Let P and Q be parameterized problems. We say that P is polynomial parameter reducible to Q, written $P \le _{p p t} Q$, if there exists a polynomial time computable function $f: \Sigma ^{*} \times \mathbb {N} \rightarrow \Sigma ^{*} \times \mathbb {N}$ and a polynomial p, such that for all $(x, k) \in \Sigma ^{*} \times \mathbb {N}$ (a) $(x, k) \in P$ if and only $\left( x^{\prime }, k^{\prime }\right) =f(x, k) \in Q$ and (b) $k^{\prime } \le p(k)$. The function f is called polynomial parameter transformation.

Proposition 1

Let P and Q be parameterized problems such that there is a polynomial parameter transformation from P to Q. If Q has a polynomial compression, then P also has a polynomial compression.

In the Red Blue Dominating Set problem, we are given a bipartite graph $G=(B \cup R, E)$ and an integer k and asked whether there exists a vertex set $S \subseteq R$ of size at most k such that every vertex in B has at least one neighbor in S. In the literature, the sets B and R are called “blue vertices” and “red vertices”, respectively. It is known (see Dom et al. 2014, Theorem 4.1) that RBDS parameterized by (|B|, k) does not have a polynomial kernel, and more generally, a polynomial compression (see Fomin et al. 2019, Corollary 19.6):

Proposition 2

(Corollary 19.6 Fomin et al. (2019)). The Red Blue Dominating Set problem, parameterized by $|B|+k$, does not admit a polynomial compression unless $\mathrm {coNP} \subseteq \mathrm {NP}/$poly.

Note that based on Propositions 1 and 2, to show that a polynomial compression for Eternal Vertex Cover parameterized by the number of guards implies $\mathrm {coNP} \subseteq \mathrm {NP}/$poly, it suffices to show a polynomial parameter transformation from Red Blue Dominating Set to Eternal Vertex Cover.

For more background on parameterized complexity and algorithms, the reader is referred to the books Cygan et al. (2015); Fomin et al. (2019); Niedermeier (2006); Flum and Grohe (2006); Downey and Fellows (2013).

3 Hardness on Bipartite Graphs

In this section we demonstrate the intractability of Eternal Vertex Cover on the class of bipartite graphs of diameter six. Our key tool is a reduction from Red Blue Dominating Set which also happens to be a polynomial parameter transformation.

Lemma 1

There is a polynomial parameter transformation from Red Blue Dominating Set parameterized by $|B|+k$ to Eternal Vertex Cover parameterized by solution size.

Proof

Let $\langle G = (V,E),b+k \rangle$ be an instance of Red Blue Dominating Set. We have $V= R\cup B$. We denote the vertices in R by $\{v_1, \ldots , v_r\}$, the vertices in B by $\{u_1, \ldots , u_b\}$ and use m to denote |E|. We assume that G is connected, since Red Blue Dominating Set does not have a polynomial sized kernel even for connected graphs.

We assume that every blue vertex has at least one red neighbour and by returning a trivial No-instance of Eternal Vertex Cover if some blue vertex has no red neighbour. The correctness of this follows from the fact that if some blue vertex does not have a red neighbour then it cannot be dominated by any subset of R.

Further, we assume that $k < b$ by returning a trivial Yes-instance of Eternal Vertex Cover if $k \ge b$. Also we assume $b>1$, since when $b=1$, the instance is easily resolved and we may return an appropriate instance of Eternal Vertex Cover (a trivial Yes instance if $k \ge 1$ and a trivial No instance otherwise).

The Construction. We will develop an instance of Eternal Vertex Cover which we denote by $\langle H, \ell \rangle$ based on $\langle G,k \rangle$ as follows (see also Fig. 2). First, we introduce r red vertices, denoted by $A := \{v_i~|~1 \le i \le r\}$ and b blue vertices, denoted by $B := \{u_i~|~1 \le i \le b\}$. Next, for all $i \in [b]$, we add $b^2+3$ dependent vertices of type i, denoted by $C_i := \{w^i_j~|~1\le j \le b^2+3\}$. Now, we add $b^2+3$ dependent vertices of type $\star$, denoted by $D := \{w^i_j~|~1\le j \le b^2+3\}$. Finally, we add two special vertices denoted by $\star$ and $\dagger$, which we will refer to as the universal and backup vertices respectively. To summarize, the vertex set consists of the following $r+(b^3+b^2+4b+5)$ vertices:

$$ V(H) := A \cup B \cup C_1 \cup \cdots \cup C_b \cup D \cup \{\star ,\dagger \}.$$

We now describe the edges in H:

• There are m structural edges given by $(v_p,u_q)$ for every pair (p, q) such that $(v_p,u_q) \in E(G)$. In other words, for every edge $(v_p,u_q)$ in the graph G, the original vertex $v_p$ is adjacent to the partner vertex $u_q$.

• The dependent vertices of type i are adjacent to the $i^{th}$ blue vertex, i.e., for every $i \in [b]$, we have a sliding edge $(u_i,w)$ for each $w \in C_i$.

• The dependent vertices of type $\star$ are adjacent to the universal vertex, i.e., we have a sliding edge $(\star ,w)$ for each $w \in D$.

• The universal vertex $\star$ is adjacent to every red vertex via a supplier edge. For every $i \in [r]$, we have the edge $(v_i,\star )$.

• Finally, we have the edge $(\star ,\dagger )$, indicating that the backup vertex $\dagger$ is adjacent to the universal vertex. We call this edge a bridge.

To summarize, we have the following edges in H:

$$\begin{aligned} \begin{aligned} E(H)&= \{(v_p,u_q)~|~ 1 \le p \le r; 1 \le q \le b; \text{ and } (v_p,u_q) \in E(H)\}~\longleftarrow \text{ the } \text{ structural } \text{ edges }\\&\cup \{(u_1,w)~|~ w \in C_1)\} \longleftarrow \text{ the } \text{ type } 1 \text{ sliding } \text{ edges }\\&\cup \vdots \\&\cup \{(u_i,w)~|~ w \in C_i)\} \longleftarrow \text{ the } \text{ type } i \text{ sliding } \text{ edges }\\&\cup \vdots \\&\cup \{(u_b,w)~|~ w \in C_b)\}~\longleftarrow \text{ the } \text{ type } b \text{ sliding } \text{ edges }\\&\cup \{(\star ,w)~|~ w \in D)\}~\longleftarrow \text{ the } \text{ type } \star \text{ sliding } \text{ edges }\\&\cup \{(v_i,\star )~|~ 1 \le i \le r\} ~\longleftarrow \text{ the } \text{ supplier } \text{ edges } \\&\cup \{(\star ,\dagger )\}~\longleftarrow \text{ the } \text{ bridge } \text{ edge }. \end{aligned} \end{aligned}$$

(1)

We now let $\ell := b+k+2$, and this completes the description of the reduced instance $\langle H, \ell \rangle$.

Fig. 2.

A schematic depicting the construction of $(H,\ell )$ starting with an instance (G, k) of Red Blue Dominating Set. The red vertices from G instance are shown in the red rectangle on the top while the blue vertices are in the blue rectangle positioned at the bottom. The solid green lines correspond to edges in E(G). The small orange vertices are the dependent vertices (some of them are omitted for clarity), while the global and backup vertices are shown by nodes labeled $\star$ and $\dagger$ respectively. The wavy line shows the bridge, the dotted lines shows the supplier edges while the dashed lines show the sliding edges.

Claim

The vertex cover number of H is $b+1$.

Proof

This follows from the fact that there is a matching of size $b+1$ in H, consisting of edges joining each blue vertex and $\star$ to one of their adjacent dependent vertices. (showing the lower bound), and that $B \cup \{\star \}$ is a vertex cover in H (which implies the upper bound).

Proposition 3

Any vertex cover of H that has at most $\ell$ vertices must contain $B \cup \{\star \}$.

Proof

Consider a vertex cover $S \subseteq V(H)$ that does not contain some blue vertex $u_i \in B$. Then S must contain all the dependent vertices in $C_i$, but since $|C_i| = b^2+3$, this contradicts our assumption that $|S| \le \ell$. Consider a vertex cover $S \subseteq V(H)$ that does not contain the universal vertex $\star$. Then S must contain all the dependent vertices in D, but since $|D| = b^2+3$, this contradicts our assumption that $|S| \le \ell$.

Proposition 4

If G has a red blue dominating set of size k, then the connected vertex cover number of H is at most $b+k+1$.

Proof

Let S be a Red Blue Dominating Set of size k in G. Consider the set $T=B\cup \{\star \}\cup S$. First we show that H[T] is connected. It is sufficient to show that each vertex has a path joining it to the universal vertex. Clearly the universal vertex is a neighbour of all the red vertices and hence it is connected to them. Any blue vertex has a neighbour in the dominating set and this red neighbour is adjacent to the universal vertex. So all the blue vertices are connected to the universal vertex.

Next we show that T is a vertex cover of H. Any structural edge has both its endpoints in T. Since $B\cup \{\star \}\subset T$, any sliding edge has one endpoint in T. All the supplier edges and the bridge edge have one endpoint in T which is the universal vertex $\star$. Thus $cvc(H)\le b+k+1$.

The Forward Direction. Suppose $\langle G = (V,E),k \rangle$ is a Yes-instance of Red Blue Dominating Set. We argue that $\langle H, \ell \rangle$ is a Yes-instance of Eternal Vertex Cover. From Klostermeyer and Mynhardt (2009), we have $evc(H)\le cvc(H)+1$. Further, Proposition 4 implies that $evc(H)\le b+k+2$ i.e. $evc(H)\le \ell$. Thus $\langle H, \ell \rangle$ is a Yes-instance of Eternal Vertex Cover.

The Backward Direction. Suppose $\langle H, \ell \rangle$ is a Yes-instance of Eternal Vertex Cover. We argue that $\langle G = (V,E),k \rangle$ is a Yes-instance of Red Blue Dominating Set.

We know that any sequence of edge attacks in H can be defended by deploying at most $\ell = b + k + 2$ guards. Let $\mathcal {S}$ denote the initial placement of guards.

We now consider two cases:

Case 1. $\mathcal {S}$ contains the backup vertex. We already know that $\mathcal {S}$ contains all the blue vertices and the universal vertex by Proposition 3. This accounts for the positions of $(b+1)$ guards. Additionally, because of the case we are in, we have one guard on the backup vertex. So the remaining k guards occupy either red or dependent vertices. We will define a corresponding dominating set of size at most k in G.

Specifically, let $A^\prime := \{j ~|~ 1 \le j \le r \text{ and } v_i \in \mathcal {S}\}$ and $B^\prime := \{j ~|~ 1 \le j \le b \text{ and } C_j \cap \mathcal {S} \ne \emptyset \}.$ For each $j \in B^\prime$, let $\ell _j$ be such that $v_{\ell _j}$ is an arbitrarily chosen neighbor of $u_j$ in G. Note that it is possible that $j_1 \ne j_2$ in $B^\prime$ but $\ell _{j_1} = \ell _{j_2}$. We now define $C^\prime := \{\ell _j ~|~ j\in B^\prime \}$. We claim that $S := \{v_i ~|~ i \in A^\prime \cup C^\prime \}$ is a dominating set for the blue vertices in G.

Intuitively speaking, our choice of dominating set is made by choosing all red vertices in G for whom the corresponding vertices in H have a guard on them, and additionally, for all blue vertices who have a guard on a dependent neighbor vertex in H, we choose an arbitrary red neighbor in G—while this choice may coincide for some blue vertices, we note that the total number of chosen vertices is no more than the number of guards who are positioned on dependent and red vertices, i.e., k. In other words, we have that $|A^\prime \cup C^\prime | \le k$.

Suppose S is not a dominating set for the blue vertices in G. Then, let $u_t \in B$ be a vertex that is not dominated by S. Let us attack a structural edge $(u_t,v_q)$. Note that $v_q$ is not occupied by a guard, and the guard on $u_t$ is forced to move to $v_q$ to defend this attack. However, observe that our assumption that $u_t$ is not dominated in G implies that no neighbor of $u_t$ has a guard in $\mathcal {S}$. Therefore, there is no guard that can move to $u_t$ now. But, by Proposition 3, the new configuration must contain a guard on $u_t$, because it is a vertex cover of H of size at most l. This is a contradiction. Therefore, S is indeed a dominating set in G of size at most k.

Case 2. $\mathcal {S}$ does not contain the backup vertex. In this case, we attack the bridge. Let $\mathcal {S}^\prime$ denote the placement of the guards obtained by defending this attack. Note that $\mathcal {S}^\prime$ must contain the backup vertex. Now we argue as we did in the previous case. This concludes the proof in the reverse direction.

Observe that the instance that we construct in the proof of Lemma 1 is both bipartite and has diameter at most six.

Recall that any vertex cover of H that has at most $\ell$ vertices must contain $B \cup \{\star \}$. It is easy to verify that all the vertex covers used by the defense in the forward direction induced connected subgraphs, since every vertex cover contains all the blue vertices, a dominating set for the blue vertices, and a universal vertex that is adjacent to all the vertices in the dominating set; and any other vertex is adjacent to one of the blue vertices (or the universal vertex). Therefore, the reduction above also serves to demonstrate the hardness of Eternal Connected Vertex Cover on bipartite graphs—note that the argument for the reverse direction is exactly the same since every connected vertex cover is also a vertex cover.

Overall, Lemma 1 along with Proposition 2 and the remarks above lead to our main result.

Theorem 1 (EVC on Bipartite Graphs)

Both the Eternal Vertex Cover and Eternal Connected Vertex Cover problems are $\mathsf {NP}$-hard and do not admit a polynomial compression parameterized by the number of guards (unless $\mathrm {NP} \subseteq {\text {coNP}}/\text {poly}$), even on bipartite graphs of diameter six.

4 A Polynomial-Time Algorithm for Co-bipartite Graphs

In this section, we focus on a proof of Theorem 2.

Theorem 2 (EVC on Co-Bipartite Graphs)

There is a quadratic-time algorithm for Eternal Vertex Cover on the class of cobipartite graphs.

The proof of this theorem is derived essentially by combining some existing results. To the best of our knowledge, this result has not been stated explicitly elsewhere and is not subsumed by known polynomial-time algorithms for special classes of graphs like chordal graphs, cactus graphs, and generalized trees³.

Let $G = (V = A \uplus B, E)$ be a cobipartite graph with bipartition A, B. Recall that G[A] and G[B] are cliques. Consider that A has p vertices $\{a_1,a_2,\ldots ,a_p\}$ and B has q vertices $\{b_1,b_2,\ldots ,b_q\}$. Without loss of generality we assume that $p\le q$ and that no vertex in A is universal. (If there is some such universal vertex in A, simply shift that vertex to B). We also assume throughout that G is connected and $p \ge 1$: if $p = 0$ then G is a clique and $evc(G) = mvc(G) = |V(G)|-1$.

Since the cliques require $p-1$ and $q-1$ vertices respectively for a vertex cover, we have $mvc(G)\ge p+q-2$. Since $p = |A|\ge 1$, there exists a (non-universal) vertex $a_i$ on the A side and therefore it has at least one non-neighbor (say $b_j$) and thus we have a vertex cover of size $p+q-2$ given by $V(G) \setminus \{a_i,b_j\}$. Therefore, $mvc(G)= p+q-2$. We make a note of this fact in the following claim.

Claim

For any co-bipartite graph G with bipartitions A and B with all the notations as described above, if there are no universal vertices in A and $|A|\ge 1$, $mvc(G)=p+q-2$.

It is easy to see that for any graph G, if the number of guards is one less than the number of vertices, the defender always has a winning strategy. Therefore, in our case, $evc(G)\le p+q-1$.

Thus, for all co-bipartite graphs (other than cliques) we have:

$$mvc(G) = p+q-2 \text{ and } p+q-2\le evc(G)\le p+q-1.$$

Now, one easy way to obtain a polynomial time algorithm for co-bipartite graphs is to use the PSPACE algorithm given by Fomin et al. (2010), as follows. When G is a co-bipartite graph on n vertices which is not a clique, the based on the above, we have that mvc(G) is $n-2$ and evc(G) is either $n-2$ or $n-1$. For $k \in \{n-2, n-1\}$, the value of ${n \atopwithdelims ()k}$ is at most $n^2$. This is the number of vertices in the multigraph obtained by Fomin et al. (2010). The number of edges of the multigraph is at most the square of number of vertices, multiplied by the number of edges of G. The construction of this graph can therefore be done in polynomial time, using the procedure given by Fomin et al. (2010). It is also possible to identify whether $evc(G)=k$ where $k \in \{n-2, n-1\}$ in polynomial time using the algorithm given by Fomin et al. (2010).

This running time can be improved to $O(n^2)$ as follows. Since G is not a clique, at least one vertex of A is not a universal vertex. From results in Babu et al. (2020), it follows that for $evc(G)=mvc(G)=n-2$, for each vertex v there must be a vertex cover of G of size $n-2$ that contains v and all cut vertices of G. Note that a cobipartite graph with bipartition (A, B) can have at most one cut vertex in A and at most one B. Further, a vertex $u \in A$ is a cut vertex if and only if $N(B) \cap A = \{u\}$. Likewise, a vertex $u \in B$ is a cut vertex if and only if $N(A) \cap B = \{u\}$. Therefore, we can enumerate the set of cut vertices in linear time, and check if the necessary condition holds in $O(n^2)$ time.

We will also argue that this necessary condition is also sufficient to guarantee $evc(G)=n-2$, thus completing the description of an $O(n^2)$ algorithm to determine evc(G) when G is a cobipartite graph. Suppose that the necessary condition for $evc(G)=mvc(G)=n-2$ holds. Then every minimum vertex cover of G must contain exactly $|A|-1$ vertices of A and exactly $|B|-1$ vertices from B. Therefore, if v is a universal vertex in B, then v must be present in every minimum vertex cover of G. Further, $|A| > 1$ and no vertex of A is a pendant vertex. It also follows from the necessary condition that A must have at least two non-cut, non-universal vertices. Similarly, B must also contain at least two non-universal, non-cut vertices.

Under the necessary condition, we can now show that $evc(G)=n-2$. Each configuration will have the following invariant: all cut vertices occupied by guards, exactly one of the non-cut, non-universal vertex of A and exactly one of the non-cut non-universal vertex of B are unoccupied and all other vertices occupied. If an attack on an edge inside A or B happens, the unguarded endpoint of that edge must be a non-cut, non-universal vertex of G. A rearrangement of guards to achieve a symmetric configuration can be done easily. Consider an attack on an edge $u-v$ with $u \in A$ and $v \in B$, when v is not occupied. Then v is not a cut vertex of G and there is another $v' \in B$ which has a neighbor $u'$ in A and $v'$ has a guard. We can move the guards from u to v, $v'$ to $u'$ and a sequence of other movements inside cliques B and A to maintain our invariant. This concludes our proof.

Remark 1

We note that the problem of determining the EVC of cobipartite graphs can also be reduced the problem to a “reachability game” played on a graph of size poly(n), leading to an $O(n^4)$ algorithm Grädel et al. (2002).

5 Concluding Remarks

We established the hardness of Eternal Vertex Cover on bipartite graphs of constant diameter. We also showed that, under standard complexity-theoretic assumptions, the problem does not admit a polynomial compression on these graph classes when parameterized by the number of guards. Because of the relationship between mvc(G) and evc(G), this also implies hardness when paramterized by the vertex cover number. In the light of these developments, it will be interesting to pursue improved FPT and approximation algorithms for these classes of graphs. It is also unclear if Eternal Vertex Cover is in NP even on these classes of graphs.

Remark 2

The full version of this paper can be found on ArXiV (Babu et al. 2022). The Appendix has a different algorithm with a comparable running time in the context of Theorem 2.