Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs

Abstract

Eternal vertex cover problem is a variant of the vertex cover problem. It is a two player (attacker and defender) game in which given a graph $G=(V,E)$, the defender needs to allocate guards at some vertices so that the allocated vertices form a vertex cover. Attacker can attack one edge at a time and the defender needs to move the guards along the edges such that at least one guard moves through the attacked edge and the new configuration still remains a vertex cover. The attacker wins if no such move exists for the defender. The defender wins if there exists a strategy to defend the graph against infinite sequence of attacks. The minimum number of guards with which the defender can form a winning strategy is called the eternal vertex cover number of G, and is denoted by evc(G). Given a graph G, the problem of finding the eternal vertex cover number is NP-hard for general graphs, and remains NP-hard even for bipartite graphs. We have given a polynomial time algorithm to find the Eternal vertex cover number in chain graphs and cographs. We have also given a linear-time algorithm to find the eternal vertex cover number for split graphs, an important subclass of chordal graphs.

1 Introduction

In 2009, Klostermeyer and Mynhardt introduced the Eternal vertex cover problem [8], which is a dynamic variant of the vertex cover problem. The problem is a two player (attacker and defender) game such that given a graph $G=(V,E)$, the defender is permitted to allocate guards in some vertices of G so that the vertices, where guards are allocated form a vertex cover. The attacker can attack one edge at a time. Now for each guard, the defender can either move the guard to one of its neighbour or can keep it untouched, such that at least one guard from any of the endpoint of the attacked edge move through the edge to settle at the other end point. So, the new allocation should also remain a vertex cover to defend the next attack. If no such configuration exists then the attacker wins. If the allocation can defend infinite sequence of attacks, then the defender wins. The minimum number of guards with which a winning strategy for the defender can be formed is known as the eternal vertex cover number of G, and is denoted by evc(G). In this paper, we are assuming that at most one guard can be allocated to each vertex. If $C_{i}$ be the allocation of the guards before the i-th attack, then after defending the i-th attack by moving the guards to configuration $C_{i+1}$, $C_{i+1}$ needs to be a vertex cover (for each $i\in \mathbb {N}$), to form a winning strategy for the defender. If it is not then the $(i+1)$-th attack will be on the edge which is not covered by $C_{i+1}$ and the attacker will win. So after reconfiguring at each step, the vertices where the guards are allocated should form a vertex cover. This implies $evc(G)\ge mvc(G)$, where mvc(G) denotes the size of the minimum vertex cover of G. It is also known that twice as many guards as mvc(G) can form an eternal vertex cover by placing the guards at both end points of a maximum matching. So, for any graph G, we have

$$mvc(G)\le evc(G)\le 2mvc(G)$$

Klostermeyer and Mynhardt have also given a characterization of the graphs for which $evc(G)=2mvc(G)$ is attained [8]. Babu et al. have given some special graph classes for which it attains the lower bound [2].

Fomin et al. have shown that the problem is NP-hard [6]. Fomin et al. have also presented a 2-approximation algorithm based on the endpoints of the matching [6]. Babu et al. proved that the problem remains NP-hard even for locally connected graphs which includes all biconnected internally triangulated planar graphs [2]. Babu et al. recently proved that the problem remains NP-hard for bipartite graphs [3]. Babu et al. proposed polynomial-time algorithms for cactus graphs and chordal graphs [4, 5]. Babu et al. proved that the problem can also be solved in polynomial time for co-bipartite graphs [3]. In this paper, we further extend the algorithmic study of the problem by proposing polynomial-time algorithms for some special graph classes. Araki et al. have given the evc(G) for generalized trees where each edge of the tree is replaced by some elementary bipartite graphs [1].

The rest of the paper is organized as follows: In Sect. 2.1, all notations and definitions used in the paper are presented. In Sect. 2.2, some theorems from existing literature are stated, which are used in the proofs presented in this paper. In Sect. 2.3, eternal vertex cover number is provided for some special subclasses of bipartite graphs. In Sect. 3, a linear-time algorithm is given to compute evc(G) in chain graphs. In Sect. 4, a linear-time algorithm to compute evc(G) in split graphs is presented. In Sect. 5, a polynomial time algorithm to compute evc(G) in cographs is presented. Finally, Sect. 6 concludes the paper.

2 Preliminaries

2.1 Definitions and Notations

All graphs considered in this paper are finite, undirected and simple. Let $G=(V,E)$ is a graph. The set of neighbours of a vertex v in G is denoted by N(v). A set $I\subseteq V$ is called an independent set of G if for all $u,v\in I$, $\{u,v\}\notin E$. Degree of a vertex $v\in V$ is the number of neighbours of v in G and it is denoted as deg(v). Given a subset $V'$ of V, the number of neighbours of v in $V'$ is denoted by $deg_{V'}(v)$. A vertex $v\in V$ is said to be a cut vertex if $G[V\setminus \{v\}]$ is not connected. The join of two graphs $H_{1}$ and $H_{2}$ is a graph formed from disjoint copies of $H_{1}$ and $H_{2}$ by connecting each vertex of $V(H_{1})$ to each vertex of $V(H_{2})$.

A vertex cover S of $G=(V,E)$ is subset of V, which contains at least one end point from each edge in E. If S is a vertex cover then $V\setminus S$ is an independent set. A vertex cover of minimum cardinality is called a minimum vertex cover. Cardinality of minimum vertex cover is denoted as minimum vertex cover number or mvc(G). Given $B\subseteq V$, the cardinality of the minimum vertex cover containing B is denoted as $mvc_{B}(G)$. If the induced graph on S, i.e. G[S] is connected, S is called a connected vertex cover. The cardinality of minimum vertex cover is denoted as cvc(G). The independent set of maximum cardinality is called maximum independent set of G and its cardinality is denoted as mis(G).

Consider a graph $G=(V,E)$ with $\vert V \vert =n$ and $\vert E \vert =m$. The guards are needed to be allocated in order to protect against infinite sequence of attacks. One edge can be attacked at a time and each guard either moves to a neighbour vertex or stays on the same vertex.

A hamiltonian cycle of a graph $G=(V,E)$ is a cycle in G, that visits each $v\in V$ exactly once. A graph possessing a hamiltonian cycle is known as hamiltonian graph. A graph $G=(V,E)$ is said to be k-regular if $deg(v)=k$, for each $v\in V$.

Let $G=(X\cup Y,E)$ be a bipartite graph. G is said to be a chain graph if vertices in X can be ordered $\{x_{1},x_{2},\ldots ,x_{\vert X\vert }\}$, such that $N(x_{1})\subseteq N(x_{2})\subseteq \ldots \subseteq N(x_{\vert X\vert })$. Similarly vertices of Y can be ordered $\{y_{1},y_{2},\ldots ,y_{\vert Y\vert }\}$, such that $N(y_{1})\supseteq N(y_{2})\supseteq \ldots \supseteq N(y_{\vert Y\vert })$. The cardinality of X and Y are denoted by p and q respectively, in this paper.

A graph $G=(V,E)$ is called a split graph if V can be partitioned in K and I, such that K is clique and I is an independent set. The class of split graphs is an important subclass of chordal graphs.

A graph $G=(V,E)$ is called a cograph if it can be generated from $K_{1}$ by complementation and disjoint union. Recursively, the class of cographs can be defined as follows

• 1. $K_{1}$ is a cograph.

• 2. Complement of a cograph is a cograph.

• 3. $G_{1}$ and $G_{2}$ are cographs, then $G_{1}\cup G_{2}$ is a cograph.

Cographs can be represented as join of k graphs, $G_{1},G_{2},\ldots ,G_{k}$ where $G_{i}$ is either $K_{1}$ or disconnected graph.

2.2 Existing Results Used in This Paper

For the sake of convenience, we are stating some important theorems, which will be used in the proofs presented in our paper.

Theorem 1

[2] Let $G=(V,E)$ be a graph with no isolated vertex for which every minimum vertex cover is connected. If for every vertex $v\in V$, there exists a minimum vertex cover $S_{v}$ of G such that $v\in S_{v}$, then $evc(G)=mvc(G)$. Otherwise, $evc(G)=mvc(G)+1$.

Theorem 2

[8] Let $G=(V,E)$ be a nontrivial, connected graph and let D be a minimum connected vertex cover of G. Then $evc(G)\le \vert D\vert +1$.

Theorem 3

[2] Let $G=(V,E)$ be a graph with at least 2 vertices and X be the set of cut vertices of G. If every minimum vertex cover S of G with $X\subseteq S$ is connected, then the following characterization holds: $evc(G)=mvc(G)$ if and only if for every vertex $v\in V\setminus X$, there exists a minimum vertex cover $S_{v}$ of G such that $X\cup \{v\}\subseteq S_{v}$.

Theorem 4

[2] Let $G=(V,E)$ be a graph with no isolated vertices. If $evc(G)=mvc(G)$, then for every vertex $v\in V$, there is some minimum vertex cover of G containing v.

2.3 Eternal Vertex Cover Number for Some Subclasses of Bipartite Graph

For a k-regular bipartite graph, the following observation can be made.

Observation 1

Given a k-regular bipartite graph $G=(X\cup Y,E)$, for each $e\in E$, there exists a perfect matching that contains e.

Note that, if the initial guard allocation is X (or Y), then attack on any edge e can be defended by moving the guards to Y (or X) through the perfect matching that contains e. So, from the Observation 1 it can be concluded that for a k-regular bipartite graph G, $evc(G)=mvc(G)=\vert X\vert =\vert Y\vert$.

For a hamiltonian bipartite graph $G=(X\cup Y,E)$ (with $\vert X\vert =\vert Y\vert =n$), suppose a hamiltonian cycle of G is $v_{1}v_{2}\cdots v_{2n}v_{1}$, where $X=\{v_{1},v_{3},\ldots ,v_{2n-1}\}$ and $Y=\{v_{2},v_{4},\ldots ,v_{2n}\}$. Then, we have the following observation.

Observation 2

Given a hamiltonian bipartite graph $G=(X\cup Y,E)$ and a hamiltonian cycle $v_{1}v_{2}\cdots v_{2n}v_{1}$ of G, X and Y are the only two possible minimum vertex covers of G.

From Observation 2, it can be concluded that for each $e\in E$, there exists a perfect matching that contains e, implying $evc(G)=mvc(G)=\vert X\vert =\vert Y\vert$.

3 A Polynomial Time Algorithm for Chain Graphs

In this section, we present a linear-time algorithm to compute the evc(G) of a given chain graph G. We also show that for a chain graph G, $evc(G)\in \{mvc(G),mvc(G)+1,mvc(G)+2\}$.

For a chain graph $G=(X\cup Y,E)$, we assume that it is connected and $\vert X\vert \le \vert Y\vert$. The eternal vertex cover problem in the class of chain graphs are studied in 2 exhaustive cases: (i) chain graphs having pendent vertices only in Y, and (ii) chain graphs having pendant vertices both in X and Y or only in X.

3.1 For Chain Graphs Where only Y Can Have Pendant Vertices

In this section we will assume that either there exists no pendant vertex in the graph or only Y contains pendant vertices. Note that a minimum vertex cover of a chain graph can be computed in linear time [9]. Let S be a minimum vertex cover G. If $\vert S\vert < min\{\vert X\vert ,\vert Y \vert \}$, then $\vert X \cap S\vert \ne \phi$ and $\vert Y \cap S\vert \ne \phi$. First, we state the following observation.

Observation 3

Given a chain graph $G=(X\cup Y,E)$ and a minimum vertex cover S of G; if $x_{i} \in S$, then $x_{j}\in S$, for each $i\le j \le p$ and if $y_{i} \in S$, then $y_{j}\in S$, for each $1\le j \le i$.

Lemma 1

For a chain graph $G=(X\cup Y,E)$, if $mvc(G)<min\{\vert X\vert ,\vert Y \vert \}$, then $evc(G)= mvc(G)+1$.

Proof

From Observation 3, if $\vert S\vert < min\{\vert X\vert ,\vert Y \vert \}$, then $y_{1},x_{p} \in S$. This implies that S is a connected vertex cover, and hence $mvc(G)=cvc(G)$. Also, each vertex cover of size mvc(G) is connected, as it always contain $y_{1}$ and $x_{p}$. But there does not exist any minimum vertex cover $S'$ that contains $x_{1}$ (If $x_{1}\in S'$, then by Observation 3, $X\subseteq S'$, which implies that $mvc(G)\ge \vert X\vert > \vert S\vert$, a contradiction). So, by Theorem 1, if for a chain graph G, $mvc(G)< min\{\vert X\vert ,\vert Y \vert \}$, then $evc(G)=mvc(G)+1$ and the initial configuration of guards is $\{x_{1}\}\cup S$.    $\square$

Now we consider the case when $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$. Again two cases may arise, one is $\vert X\vert <\vert Y \vert$ and the another is $\vert X\vert =\vert Y \vert$.

Claim 1

For a chain graph $G=(X\cup Y,E)$, if $\vert X\vert <\vert Y \vert$ and $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$, then $mvc(G)\ne evc(G)$.

Proof

Let $evc(G)=mvc(G)$, then $x_{p}\in S$, for any minimum vertex cover S of G (by Observation 3). If the attacker attacks $\{x_{p},y_{q}\}$, then the guard at $x_{p}$ moves to $y_{q}$ and rest of the guards are adjusted so that the new configuration remains a vertex cover. Since in the new configuration, $y_{q}\in S'$, (where $S'$ is a minimum vertex cover), by Observation 3, $Y\subseteq S'$. Which leads to a contradiction since $mvc(G)<\vert Y \vert$. Hence $mvc(G)\ne evc(G)$.   $\square$

Lemma 2

For a chain graph $G=(X\cup Y,E)$, if $\vert X\vert <\vert Y \vert$, $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$, and there exists a minimum vertex cover containing $x_{p},y_{1}$, then $mvc(G)= evc(G)+1$.

Proof

If for a given chain graph G, there exists a minimum vertex cover that contains $x_{p},y_{1}$, then $cvc(G)=mvc(G)$. Since $evc(G)\ne mvc(G)$ and by Theorem 2, $evc(G)\le cvc(G)+1$, we may conclude that $evc(G)=mvc(G)+1$.    $\square$

Now let us consider the case when there does not exist any minimum vertex cover that contains $x_{p},y_{1}$, $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$ and $\vert X\vert <\vert Y \vert$. In this case, X is the only minimum vertex cover.

Lemma 3

For a given chain graph $G=(X\cup Y,E)$, if $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$ and $\vert Y\vert =\vert X \vert +1$, and X is the only minimum vertex cover of G, then $evc(G)=mvc(G)+1$.

Proof

Let $\vert N(x_{1})\vert > 2$ or $y_{q-1}\notin N(x_{1})$. If the initial configuration is $\{x_{1},x_{2},\ldots ., x_{p},y_{q}\}$, attack any edge $\{x_{i},y_{j}\}~(y_{j}\ne y_{q})$; by Hall’s Theorem there exists a perfect matching from $X\setminus \{x_{i}\}$ to $Y\setminus \{y_{j},y_{q}\}$, since $\mid \cup _{j=1}^{k} N(x_{j})\mid \ge k+1$, for each $k\in [p]$. So all the guards can be moved from $X\cup \{y_{q}\}$ to Y.

Now if Y is the guard allocation configuration and $\{y_{j},x_{i}\}(y_{j}\ne y_{q})$ is attacked then the next configuration will be $X\cup \{y_{q}\}$. If $y_{j}=y_{q}$ then the configuration will be $X\cup \{y_{q-1}\}$. Thus any infinite sequence of attack can be defended using $mvc(G)+1$ guards. So $evc(G)=mvc(G)+1$. If $\vert N(x_{1})\vert \le 2$ and $y_{q-1}\in N(x_{1})$, then it is easy to observe $evc(G)=mvc(G)+1$.   $\square$

Observation 4

Let $G=(X\cup Y,E)$ is a chain graph with $\vert Y\vert >\vert X\vert +1$ for which the only minimum vertex cover is X and S be a vertex cover of size $mvc(G)+1$. If $\mid S \cap Y\mid \ge 2$ and $y_{i}\in S$, then $y_{j}\in S$, for each $j\in [i]$. We may also conclude that there exists two kinds of vertex covers of size $mvc(G)+1$

• i. $X\cup \{ y_{i}\}$; $i\in [q]$.

• ii. $\{y_{1},\ldots ,y_{i+1},x_{i+1},\ldots ,x_{p}\}$; $i\in [p-2]$.

Let $k=min\{i \mid \{x_{i},y_{q}\}\in E\}$.

Lemma 4

For a given chain graph $G=(X\cup Y,E)$ with $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$ and $\vert Y\vert >\vert X \vert +1$, if X is the only minimum vertex cover of G and $\mid \cup _{j=1}^{k-1} N(x_{j})\mid = k$, then $evc(G)=mvc(G)+1$.

Proof

By above definition $k=min\{i \mid \{x_{i},y_{q}\}\in E\}$, if $|\cup _{j=1}^{k-1} N(x_{j})| = k$. Then any attack can be defended by moving the guards from the configuration $X\cup \{ y_{q}\}$ to configuration $\{y_{1},\ldots ,y_{k},x_{k},\ldots ,x_{p}\}$ (or from $\{y_{1},\ldots ,y_{k},x_{k},\ldots ,x_{p}\}$ to $X\cup \{ y_{q}\}$). So, in this case $evc(G)=mvc(G)+1$.    $\square$

Let $V'=\{i \mid |\cup _{j=1}^{i} N(x_{j})|= i+1\}$.

Lemma 5

For a given chain graph $G=(X\cup Y,E)$ with $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$ and $\vert Y\vert >\vert X \vert +1$, if X is the only minimum vertex cover of G and $\vert \cup _{j=1}^{k-1} N(x_{j})\vert > k$, then $evc(G)=mvc(G)+2$.

Proof

If $|\cup _{j=1}^{k-1} N(x_{j})| > k$ and $V'\ne \phi$, then let $l=max\{i \mid i\in V'\}$. If the initial configuration is of type-ii, then attack $\{x_{p},y_{q}\}$ and make the configuration $X\cup \{y_{q}\}$, if possible. Then attack $\{x_{l+1},y_{l+1}\}$, the guard at $x_{l+1}$ moves to $y_{l+1}$ and since $\{y_{q},x_{l+1}\} \notin E$, so there does not exist any guard which can move to $x_{l+1}$, hence no defending move exists, hence $evc(G)=mvc(G)+2$.

If the set $V'=\phi$, then $\mid \cup _{j=1}^{i} N(x_{j})\mid >i+2$, which implies all vertex covers of size $mvc(G)+1$ are of type-i. Now whatever the initial configuration be attack $\{x_{p},y_{q}\}$. The configuration after defending this should be $X\cup \{y_{q}\}$. Now attack $\{x_{k-1},y_{k-1}\}$, the guard at $x_{k-1}$ moves to $y_{k-1}$ now there is no guard which can move to $x_{k-1}$ and form a vertex cover. So $evc(G)=mvc(G)+2$.   $\square$

Now, consider the case when $\vert X \vert =\vert Y \vert$.

Lemma 6

For a given chain graph $G=(X\cup Y,E)$, if $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$, $\vert X\vert =\vert Y \vert$ and there exists a minimum vertex cover containing $y_{1}$ and $x_{p}$, then $evc(G)=mvc(G)+1$.

Proof

There exists a minimum vertex cover of G that contains both $y_{1}$ and $x_{p}$. This implies there exists $i\in [p]$, such that $\cup _{j=1}^{i} N(x_{j})=\cup _{j=1}^{i} \{y_{j}\}$ and $evc(G)\in \{mvc(G),mvc(G)+1\}$. If $evc(G)=mvc(G)$, then the initial configuration can be of 3 types: (i) X, (ii) Y and (iii) $\{y_{1},\ldots ,y_{i},x_{i+1},\ldots ,x_{p}\}$, $i\in [p]$.

If the initial configuration is of type-iii, then attack $\{x_{1},y_{1}\}$ and change it to X if possible. Then attack $\{y_{i},x_{i+1}\}$, so the guard at $x_{i+1}$ moves to $y_{i}$ and i guards at $x_{1},x_{2},\ldots ,x_{i}$ have $i-1$ places, i.e. $y_{1},y_{2},\ldots ,y_{i-1}$ to move. Hence no new configuration can be made which will form a vertex cover.

If the initial configuration is Y, then attack $\{y_{i},x_{i+1}\}$. The guard at $y_{i}$ moves to $x_{i+1}$ and $p-i$ guards at $y_{i+1},\ldots ,y_{p}$ have $p-i-1$ places, i.e. $x_{i+2},\ldots ,x_{p}$ to move. Hence no new configuration can be made which will form a vertex cover.

This implies G can not be defended with mvc(G) guards. So, $evc(G)=mvc(G)+1$.   $\square$

Lemma 7

For a given chain graph $G=(X\cup Y,E)$, with $mvc(G)=min\{\vert X\vert ,\vert Y \vert \}$ and $\vert Y\vert =\vert X \vert$, if the only minimum vertex covers are X and Y, then $evc(G)=mvc(G)$.

Proof

The only type of minimum vertex covers are X and Y. This implies $\mid \cup _{j=1}^{l} N(x_{j})\mid \ge l+1$, for all $l\in [p-1]$. Now if the initial configuration is X, then attack on any edge $\{x_{i},y_{j}\}$ can be defended by moving all the guards to Y, this can be done since by Hall’s Theorem there exists a perfect matching in $(X\setminus \{x_{i}\},Y\setminus \{y_{j}\})$. Similarly, if the initial configuration is Y, then attack on any edge $\{x_{i},y_{j}\}$ can be defended by moving all the guards to X, this can also be done since by Hall’s Theorem there exists a perfect matching in $(X\setminus \{x_{i}\},Y\setminus \{y_{j}\})$. So, $evc(G)=mvc(G)$.   $\square$

3.2 For Chain Graphs with Pendant Vertices in X or in X, Y both

If $y_{1}$ and $x_{p}$ both have pendant vertices attached (consider that the graph is not $K_{2}$; for $K_{2}$, $evc(G)=mvc(G)=1$), then there exists a minimum vertex cover that contains $x_{p}$ and $y_{1}$, which implies $evc(G)\in \{mvc(G),mvc(G)+1\}$. Now if $evc(G)=mvc(G)$, then there exists a configuration such that a guard is allocated at the pendant vertex $x_{1}$ (if not then we can attack the edge $\{y_{1},x_{1}\}$ and shift the guard at $y_{1}$ to $x_{1}$). This implies that there is no guard in $y_{1}$. Now attack $\{x_{p},y_{1}\}$, then the guard at $x_{p}$ moves to $y_{1}$ and the guard at $x_{1}$ has to stay at $x_{1}$. So in this new configuration, $x_{1}$ and $y_{1}$ both have guards allocated, a contradiction since no minimum vertex cover can contain the pendant vertex and its respective stem. So, $evc(G)=mvc(G)+1$.

Now consider the case when only X has pendant vertices, that is, only $y_{1}$ is the stem. If $mvc(G)<min\{\vert X \vert , \vert Y \vert \}$, then $evc(G)=mvc(G)+1$. If $mvc(G)=\vert X \vert$, then $y_1$ has only one pendant neighbour (otherwise $mvc(G) < \vert X\vert$, leading to a contradiction). Since $\{y_{1},x_{2},\ldots ,x_{p}\}$ forms a minimum vertex cover and it is connected, $mvc(G)=cvc(G)$. This implies that $evc(G)\in \{mvc(G),mvc(G)+1\}$ Further, two cases may arise.

Case 1: $\vert X \vert < \vert Y \vert$

If $evc(G)=mvc(G)$, the initial guard allocation can be of 2 types; X and $\{y_{1},\ldots ,y_{i},x_{i+1},\ldots ,x_{p}\}$.

If the initial configuration is X, then if $\{x_{p},y_{1}\}$ is attacked then the guard at $x_{1}$ can not move anywhere, failing to produce a valid defending move.

If the initial configuration is $\{y_{1},\ldots ,y_{i},x_{i+1},\ldots ,x_{p}\}$ then attack $\{x_{1},y_{1}\}$, the only configuration it can form is X. But then, attacking $\{x_{p},y_{1}\}$ will lead to a win for the attacker.

So, $evc(G)\ne mvc(G)$. This implies $evc(G)=mvc(G)+1$.

Case 2: $\vert X \vert = \vert Y \vert$

If the initial guard allocation is X or Y, then attacking $\{x_{p},y_{1}\}$ will lead to a win for the attacker.

If the initial configuration is $\{y_{1},\ldots ,y_{i},x_{i+1},\ldots ,x_{p}\}$ then attack $\{x_{1},y_{1}\}$, the only configuration it can form is X. But then, attacking $\{x_{p},y_{1}\}$ will lead to a win for the attacker.

So, $evc(G)\ne mvc(G)$. This implies that $evc(G)=mvc(G)+1$.

The above characterization is done by observing a property that for a given chain graph $G=(X\cup Y, E)$, whether there exists a minimum vertex cover S that contains both $x_{p}$ and $y_{1}$ or not. This property can be checked in polynomial time for a given chain graph. Before starting the process of the algorithm, by preprocessing, an array $A[1,2,\ldots ,p]$ can be formed, where $i^{th}$ cell contains the degree of $x_{i}$. If there exists a $j\in [p-1]$, such that $A[j]\le j$, then there exists a minimum vertex cover of G that contains both $x_{p}$ and $y_{1}$. If there does not exist such j, then the only vertex covers are of the form X or Y.

From the above lemmas and results, we can conclude the following theorem.

Theorem 5

Given a connected chain graph $G=(V,E)$, evc(G) can be computed in $O(n+m)$ time.

4 A Linear Time Algorithm for Split Graphs

In this section, we present a linear-time algorithm to compute the eternal vertex cover number for split graphs. Note that, there already exists a quadratic time algorithm to compute evc(G) for chordal graphs. Since the class of split graphs is a subclass of chordal graphs, we also have a quadratic time algorithm to compute evc(G) for split graphs. But, in this section, we present a linear-time algorithm to compute evc(G) for any split graph G.

The following result is already known regarding the eternal vertex cover number of chordal graphs.

Theorem 6

[4] Given a connected chordal graph $G=(V,E)$ and the set of all cut vertices X of G, $evc(G) = mvc_{X}(G)$ if and only if for every vertex $v \in V(G)\setminus X$, we have $mvc_{X\cup \{v\}}(G) = mvc_{X} (G)$; otherwise $evc(G) = mvc_{X}(G)+1$.

Since split graphs are chordal graphs, for any split graph G we have $evc(G)\in \{mvc_{X}(G),mvc_{X}(G)+1\}$.

Let $G=(K\cup I,E)$ be a connected split graph, where K is a clique and I is an independent set. Without loss of generality, we may assume that K is a maximal clique of G. Let X denote the set of cut vertices of G. Now, we first prove the following lemmas.

Lemma 8

If for each $x\in K$, $\vert N(x)\vert > \vert K\vert -1$, then $mvc(G)=mvc_{X}(G)=\vert K\vert$. Otherwise $mvc(G)=mvc_{X}(G)=\vert K\vert -1$.

Proof

If for each $x\in K$, $\vert N(x)\vert > \vert K\vert -1$, then each $x\in K$ has at least one neighbour in I. Note that any minimum vertex cover must contain at least $|K|-1$ vertices from K. If there exists a minimum vertex cover S that contains only $\vert K\vert -1$ vertices from K. Then there exists a vertex $v\in K$, such that v does not belong to S. So, S must contain all neighbours of v from I, implying that $\vert S\vert \ge \vert K\vert$. Since K is itself a vertex cover of size $\vert K\vert$, if v has more than one neighbour in I, then $\vert S\vert > \vert K\vert$, a contradiction. So, K always form a minimum vertex cover in this case. Since $X\subseteq K$, it can be concluded that $mvc(G)=mvc_{X}(G)=\vert K\vert$.

Now if there exists $x\in K$, such that $\vert N(x)\vert = \vert K\vert -1$, then $K\setminus \{x\}$ forms a minimum vertex cover of cardinality $\vert K\vert -1$. Note that x cannot be a cut vertex (as it has no neighbour in I). So, $X\subseteq K\setminus \{x\}$ and $K\setminus \{x\}$ forms a minimum vertex cover, implying that $mvc(G)=mvc_{X}(G)=\vert K\vert -1$.   $\square$

Lemma 9

$evc(G)\in \{mvc(G), mvc(G)+1\}$.

Proof

The proof follows from the fact that $evc(G)\in \{mvc_{X}(G), mvc_{X}(G)+1\}$ and $mvc(G)=mvc_{X}(G)$.    $\square$

Lemma 10

Let $mvc(G)=\vert K \vert -1$. Then $evc(G)=mvc(G)+1$ if $I\ne \phi$ and $evc(G)=mvc(G)$ if $I= \emptyset$.

Proof

If $I\ne \phi$, then consider a vertex $y\in I$. By Theorem 4, if $evc(G)=mvc(G)=\vert K\vert -1$, then there exists a minimum vertex cover S that contains y, which implies $\vert S\cap K\vert \le \vert K\vert -2$, leading to a contradiction. Hence $evc(G)=mvc(G)+1$. If $I=\phi$, then G is a complete graph, implying $evc(G)=mvc(G)$.   $\square$

Lemma 11

Let $mvc(G)=\vert K \vert$ and there exists at least one pendant vertex $y_{i}\in I$, then $evc(G)=mvc(G)+1$.

Proof

Let $x_{j}$ be the only neighbour of the pendant vertex $y_{i}$, then $x_{j}\in X$. On contrary assume that $evc(G)=mvc(G)$, then by Theorem 6 there exists a minimum vertex cover S that contains both X and $y_{i}$. Hence $x_{j}\in S$ as $y_{i}\in S$. Then there must be a vertex $x_{k}\in K$, which does not belong to S. Since $mvc(G)=\vert K \vert$, by Lemma 8, $N(x)\cap I\ne \phi$ for all $x\in K$. Hence, if $x_{k}$ is not in S then all of its neighbours should be in S. Since $y_{i}$ is not a neighbour of $x_{k}$, no neighbour of $x_{k}$ in I belongs to S. Hence contradiction arises. So, $evc(G)=mvc(G)+1$.   $\square$

Lemma 12

Let $mvc(G)=\vert K \vert$, G has no pendant vertices and for each $x\in K$, $deg(x)\ge \vert K\vert +1$. Then, $evc(G)=mvc(G)+1$.

Proof

Note that $mvc_{X}(G)=mvc(G)$. On contrary assume that $evc(G)=mvc(G)$. Then, by Theorem 4, for any $y_{i}\in I$, there exists a minimum vertex cover S that contains $y_{i}$. Then $\vert K\cap S\vert = \vert K\vert -1$. Let $x_{j}\in K$ be the vertex which is not in S. Since $\vert N_{I}(x_{j})\vert \ge 2$, S contains at least 2 vertices from I. But, then $|S|\ge |K|+1$, a contradiction arises. Hence, $evc(G)=mvc(G)+1$.   $\square$

Lemma 13

Let G does not has any pendant vertex with $mvc(G)=\vert K \vert$ and $X_{1}=\{x\in K~:~ deg_{I}(x)=1\}$. If $N(X_{1})\cap I = I$, then $evc(G)=mvc(G)$, otherwise if $N(X_{1})\cap I$ is properly contained in I, then $evc(G)=mvc(G)+1$.

Proof

Proof of the Lemma 13 has been omitted due to space constraint.

So, by the above lemmas we can conclude the following theorem.

Theorem 7

For a connected split graph $G(K\cup I,E)$, evc(G) can be computed in time $O(n+m)$.

Proof

The proof of the theorem is straightforward from the above lemmas. Before starting the algorithm, by preprocessing, an array $A[1,2,\ldots ,n]$ can be formed, such that A[i] stores the degree of the vertex $v_{i}$. By help of this array the algorithm can run in $O(n+m)$ time.   $\square$

5 A Polynomial Time Algorithm for Cographs

As mentioned earlier, any connected cograph can be written as join of k graphs, $G_{1},G_{2},\ldots$,$G_{k}$ where each $G_{i}$ is either $K_{1}$ or a disconnected graph. Note that for a connected cograph $G=(V,E)$, the maximum independent set of G is a subset of $V(G_{i})$, for some $i\in [k]$. So, any minimum vertex cover of G contains vertices from at least $k-1$ number of $G_{i}$’s.

By Theorem 1, given a connected cograph $G=(V,E)$, for which each minimum vertex cover is connected, evc(G) can be calculated by checking $mvc_{v}(G)=mvc(G)$ for each $v\in V$. To check this condition for any $v\in V$, a new graph $G'=(V',E')$ can be formed from G, where $V'=V\cup \{u\}$, $E'=E\cup \{uv\}$; then we can check whether $mvc(G)=mvc(G')$. The class of cographs is not closed under pendant vertex addition. But cographs are also weakly chordal graphs, which are closed under pendant vertex addition. So, we are giving a polynomial time algorithm $EVC\_CHECK(G)$ for connected cographs $G=(V,E)$ for which every minimum vertex cover is connected, to compute evc(G). For this, we are using the algorithm given in [7] to compute minimum vertex cover for weakly chordal graphs. So, for each vertex of the cograph $G=(V,E)$ (for which every minimum vertex cover is connected) we will add a pendent vertex (only one at each step and we will delete the previous pendent vertex while adding pendent to the next vertex) and use the algorithm in [7] to compute whether the mvc is same for the old and new graph. If it is same for each vertex of $G=(V,E)$, then $evc(G)=mvc(G)$; and $evc(G)=mvc(G)+1$ otherwise.

Since the algorithm to find minimum vertex cover in weakly chordal graphs mentioned in [7] runs in O(nm) time, we may conclude the following theorem from the above discussion.

Theorem 8

Given a connected cograph $G=(V,E)$, for which every minimum vertex cover is connected, evc(G) can be calculated in time O(nm).

The algorithm mentioned in Theorem 8 will be called as $EVC\_CHECK$ from here on.

When $k=2$, the graph G is join of 2 subgraphs $G_{1}$ and $G_{2}$. Here we are assuming $\vert G_{1}\vert \le \vert G_{2}\vert$ and both $G_{1}$ and $G_{2}$ are non-empty. If $mis(G)> min\{\vert G_{1}\vert , \vert G_{2}\vert \}$, then maximum independent set I of G is a subset of $G_{2}$. If $I\subset G_{2}$, then each minimum vertex cover S is connected, since $G_{2}\cap S\ne \phi$ and $G_{1}\cap S\ne \phi$. So evc(G) can be computed by $EVC\_CHECK(G)$. If $I=G_{2}$, then $G_{1}$ is the only minimum vertex cover and there does not exist any minimum vertex cover S that contains any vertex of $G_{2}$, so by Theorem 4, $evc(G)\ne mvc(G)$. In this case, $G_{1}\cup \{u\}$, such that $u\in G_{2}$, forms an initial configuration of guards, as $G_{2}$ is independent, implying $evc(G)=mvc(G)+1$.

So, the case remains to be observed is, when $mis(G)\le min\{\vert G_{1}\vert , \vert G_{2}\vert \}$. If $mis(G)<min\{\vert G_{1}\vert , \vert G_{2}\vert \}$, then any minimum vertex cover S is connected, since $G_{2}\cap S\ne \phi$ and $G_{1}\cap S\ne \phi$. So, evc(G) can be calculated by $EVC\_CHECK(G)$.

Now for the case when $mis(G)=min\{\vert G_{1}\vert , \vert G_{2}\vert \}$ and by previous assumption, $\vert G_{1}\vert = min\{\vert G_{1}\vert , \vert G_{2}\vert \}$. If $\vert G_{1}\vert = \vert G_{2}\vert$, then $G_{1}$ or $G_{2}$ is an independent set.

If both are independent then G is $K_{\vert G_{1}\vert ,\vert G_{1}\vert }$, and $evc(G)=mvc(G)$.

If $G_{2}$ is not independent, then $G_{1}$ is independent. If there exists a minimum vertex cover S that contains at least one vertex of $G_{1}$, then it contains all vertex of $G_{1}$, so it contains no vertex from $G_{2}$. But since $G_{2}$ is not independent, then there exists at least one edge in $E(G_{2})$ for which no endpoint is in S. Hence no minimum vertex cover contains any vertex from $G_{1}$. So, by Theorem 4, $evc(G)\ne mvc(G)$. So, $evc(G)=mvc(G)+1$ and $G_{2}\cup \{u\}$ where $u\in G_{1}$, forms an initial guard allocation configuration.

Lemma 14

Given a connected cograph $G=(V,E)$ which is a join of $G_{1}$ and $G_{2}$. If $mis(G)=min\{\vert G_{1}\vert , \vert G_{2}\vert \}$ and $\vert G_{1}\vert < \vert G_{2}\vert$, then evc(G) can be calculated in polynomial time.

Proof

Proof of Lemma 14 is omitted due to space constraint.

Observation 5

Given a connected cograph $G=(V,E)$ and $k\ge 3$, every minimum vertex cover of G is connected.

Note that, for $k\ge 3$, evc(G) can be computed in O(nm) time using $EVC\_CHECK(G)$. So, from the above observations and lemma the following theorem can be concluded.

Theorem 9

Given a connected cograph $G=(V,E)$, evc(G) can be computed in O(nm)-time.

6 Conclusion and Future Aspects

In this paper we have given polynomial time algorithms for three restricted subclasses of perfect graphs, i.e. chain graphs, split graphs and cographs. For split graphs, running time of our algorithm is linear. The class of split graphs is an important subclass of chordal graphs, for which a quadratic time algorithm was already known in the literature. It will also be interesting to try for linear-time algorithms for eternal vertex cover problem for chordal graphs, or some other important subclasses of chordal graphs. The eternal vertex cover problem is NP-hard for bipartite graphs and the class of chain graphs is the largest class of bipartite graphs for which linear time algorithm has been found. The complexity status of the eternal vertex cover problem is still unknown for other important subclasses of bipartite graphs. Here we have solved the complexity status of eternal vertex cover problem for cographs, but for larger graph classes like distance hereditary graphs, it is yet to be solved.