1 Introduction
Eternal vertex cover problem can be described in terms of a two player game played on any given graph between an attacker who attacks the edges of and a defender who controls the placement of a fixed number of guards (say ) on a subset of vertices of to defend the attack Klostermeyer2009 . In the beginning of the game, the defender chooses a placement of guards on a subset of vertices of , defining an initial configuration. Subsequently, in each round of the game, the attacker attacks an edge of her choice. In response, the defender has to reconfigure the guards. The guards move in parallel. Each guard may be retained in its position or moved to a neighboring vertex, ensuring that at least one guard from an endpoint of the attacked edge moves to its other endpoint. If the defender is able to do this, then the attack is said to be successfully defended and the game proceeds to the next round with the attacker choosing the next edge to attack^{1}^{1}1There are two popular versions of the problem: one as described here and the second with an additional constraint that not more than one guard can be on any vertex in any configuration. The number of guards required to protect the graph may differ between these two versions. However, the results derived in this paper and those cited here hold in both the versions.. Otherwise, the attacker wins. If the defender is able to keep defending against any infinite sequence of attacks on with guards, then we say that there is a defense strategy on with guards. In this case, the positions of guards in any round of the game defines a configuration, referred to as an eternal vertex cover of of size . The set of all configurations encountered in the game defines an eternal vertex cover class of . The eternal vertex cover number of a graph , denoted by is the minimum integer such that there is a defense strategy on using guards. It is clear from the description of the game that in any configuration, at least one of the endpoints of each edge must have a guard for defending attacks successfully. Hence, it is clear that each eternal vertex cover of is a vertex cover of and , the vertex cover number of .
The decision version of the eternal vertex cover problem takes a graph and an integer as inputs and asks whether has an eternal vertex cover of size at most . Fomin et al. Fomin2010 showed that this problem is NPhard and is in PSPACE. The problem was recently shown to be NPComplete for internally triangulated planar graphs evc_lb_Arxiv . It is not yet known whether the problem is in NP for bipartite graphs Fomin2010 . Similarly, it is an open question whether computing the eternal vertex cover number of bounded treewidth graphs is NPHard or not Fomin2010 . The problem remains open even for graphs of treewidth two.
Dynamic variants of other classical graph parameters like dominating set GOLDWASSER2008 ; KLOSTERMEYER2012 ; rinemberg2019 ; goddard2005 and independent set Hartnell2014 ; Caro2016EternalIS are also well studied in literature. Rinemberg et al. rinemberg2019 recently showed that eternal domination number of interval graphs can be computed in polynomial time. The relationship between eternal vertex cover number and other dynamic graph parameters was explored by Klostermeyer and Mynhardt Klostermeyer2011 and Anderson et al. Anderson2014 . It is known that , where is the minimum cardinality of a connected vertex cover of Klostermeyer2009 ; Fomin2010 . Fomin et al. Fomin2010 showed that is at most twice the size of a maximum matching in . It is also known that for any connected graph , , where is the minimum cardinality of a vertex cover of that contains all cut vertices of evc_lb_Arxiv .
Precise formulae or algorithms for computing eternal vertex cover number are known for only a few classes of graphs. The initial work by Klostermeyer and Mynhardt gave explicit formulae for the eternal vertex cover number of trees, cycles and grids Klostermeyer2009 . The eternal vertex cover number of a tree is known to be , where is the number of leaves of . The eternal vertex cover number of a cycle on vertices is , which is equal to its vertex cover number. A polynomial time algorithm for computing eternal vertex cover number of chordal graphs has been obtained recently evc_lb_Arxiv . Parameterized algorithms for the problem are discussed by Fomin et al. Fomin2010 . Araki et al. Hisashi_Gen_Trees discusses a polynomial time algorithm to compute eternal vertex cover number of a simple generalization of trees.
All the graph classes for which polynomial time algorithms for eternal vertex cover are known so far exhibit a common property. Recall that , which is the minimum cardinality of a vertex cover of that contains all cut vertices of is a lower bound to . For any graph that belong to the classes given above, this lower bound is polynomial time computable and . However, this is not true for cactus graphs, as shown in Section 6. Hence, we formulate a new lower bounding technique based on the substructure property (Definition 4) to handle cactus graphs.
A cactus is a connected graph in which any two simple cycles have at most one vertex in common. A cactus is a generalization of cycles and trees in the following sense: if we contract every cycle in a cactus to a single vertex, the resultant graph is a tree. Cactus graphs have treewidth at most two. Many important NPhard combinatorial problems are polynomial time solvable on cactus graphs HARE1987437 . Since trees and cycles are examples of cactus graphs, we know that there exist cactus graphs for which lower bound is close to . However, there are cactus graphs for which the eternal vertex cover number is more than times (Section 6). Thus, the reason for efficient computability of eternal vertex cover number for this graph class is not just related to the lower bound .
The lower bound argument for eternal vertex cover number of trees was obtained using a recursive procedure Klostermeyer2009 . We show that by using a more sophisticated recursive method based on the substructure property of cactus graphs, we can device a new lower bounding strategy applicable for cactus graphs. From this, we derive a formula for computing the eternal vertex cover number of a cactus , in terms of eternal vertex cover number and some related parameters of certain edge disjoint subgraphs of . The algorithm for computing eternal vertex cover number and the other required parameters is a recursive procedure based on this formula and it runs in time linear in the size of the input graph. Finally, we present an extension of the result to graphs in which each block is an edge, a cycle or a biconnected chordal graph. It is shown that for graphs of this class, eternal vertex cover number can be computed in quadratic time. In particular, this method implies a quadratic time algorithm for the computation of eternal vertex cover number of chordal graphs, which is different from the algorithm given in evc_lb_Arxiv .
2 Some Basic Observations
Definition 1.
Let be a graph and . The minimum cardinality of a vertex cover of that contains all vertices of is denoted by . The minimum integer such that there is a defense strategy on using guards with all vertices of being occupied in each configuration is denoted by .
When , we use and respectively instead of and . From the above definition, it is clear that .
Definition 2.
If is a graph and , we use to denote the graph obtained by adding an additional vertex which is made adjacent only to .
Observation 1.
.
Proof.
Suppose . Let be the vertex in . There is a defense strategy on using guards, by using guards to move exactly the same way as they would have been moved for defending attacks on and an additional guard to protect against attacks on the edge . If the edge is attacked when is not occupied, then the additional guard will move from to . In the very next round, this guard moves back to , irrespective of the edge attacked. It is easy to check that using this strategy, any attack on can be defended. ∎
Definition 3 (xcomponents and xextensions).
Let be a cut vertex in a connected graph and be a component of . Let be the induced subgraph of on the vertex set . Then, is called an component of and is called an extension of .
Definition 4 (Substructure property).
Let be an arbitrary noncut vertex of a graph . If the following is true for any arbitrary extension of , then satisfies substructure property:

if , then in every eternal vertex cover of , the number of guards on is at least and

if , then in every eternal vertex cover of , the number of guards on is at least .
Observation 2.
If a graph satisfies substructure property and is a noncut vertex of , then .
Proof.
Suppose satisfies substructure property and is a noncut vertex of . Let be the vertex in . In any eternal vertex cover class of , there must be a configuration in which there is a guard on . By substructure property, in this configuration, the number of guards in must be at least . Hence, the number of guards required on is at least . Consequently, . Further, by Observation 1, it follows that . ∎
Definition 5.
Let be a graph and be a vertex of .

is Type 1 with respect to if and

is Type 2 with respect to if .
Remark 1.
From the above definition, a tree is Type 1 with respect to any of its vertices. An even cycle is Type 1 with respect to any of its vertices. An odd cycle is Type 2 with respect to any of its vertices. A complete graph on
or more vertices is Type 2 with respect to any of its vertices.Remark 2.
By Observation 2, if satisfies substructure property and is a noncut vertex of , then is either Type 1 or Type 2 with respect to .
Definition 6 (evc_lb_Arxiv ).
Let be a cut vertex of a connected graph . The set of components of will be denoted as . For , we define to be the set of all components of that are Type with respect to .
Lemma 1.
Let be a connected graph and be a cutvertex of such that each component of satisfies the substructure property.

If all components of are Type 2, then .

Otherwise, .
Proof.
The first part is easy to see from the definition of the substructure property.
To prove the second part, suppose is an component of which is Type 1 with respect to . Let . By a direct application of the substructure property, it follows that cannot be less than . Now, for contradiction, suppose . Let be a minimum eternal vertex cover class . Since there are only guards on and each component of satisfies the substructure property, it can only be the case that in every configuration of the number of guards on an component is exactly if is Type 1 with respect to and it is exactly if is Type 2 with respect to . Further, must also be occupied in every configuration. However, to defend repeated attacks on edges of which is a Type 1 component with respect to , guards have to be on in some configuration, if is to be always occupied. Then, the total number of guards on must be more than , a contradiction. Hence, .
It is not difficult to show that . In every configuration, we will maintain the following invariants.

A guard will be kept on .

There will be exactly guards on each component of that is Type 2 with respect to such that the guards on form an eternal vertex cover of .

In one of the Type 1 components of (if exists), exactly guards will be kept and in every other Type 1 component of , guards will be kept. This will be done in such a way that the induced configuration on , for each component forms an induced configuration of an eternal vertex cover of .
To defend an attack on an edge in a Type 2 component maintaining the invariants, it will be enough to move guards only on . To defend an attack on an edge in a Type 1 component, it will be enough to move guards in at most two components. If the edge attacked is in a Type 1 component with guards on , then there is another Type 1 component with guards on . Since and satisfy substructure property, it is not difficult to rearrange guards in and such that the number of guards on becomes and that on becomes and the invariants are maintained. ∎
3 Computation of the Type of vertices
Lemma 1 indicates the possibility of a recursive method to compute eternal vertex cover number of graphs whose components satisfy the substructure property. However, this makes it necessary to also compute and the type of each component of , with respect to . Since a cut vertex of is not a cutvertex in its components, a general method to find the type of a graph with respect to any arbitrary vertex of the graph (including noncut vertices) is necessary. This section addresses this issue systematically.
Observation 3 (Type with respect to a cut vertex).
Let be a connected graph and be a cutvertex of such that each component of satisfies the substructure property. Then, is Type 1 with respect to if at least one of the components of is Type 1 with respect to . Otherwise, is Type 2 with respect to .
Proof.
Note that when a pendent edge is added to , that edge is a Type 1 component with respect to . Further, of this component is . Using these facts in the expressions given in Lemma 1 immediately yields the observation. ∎
Observation 4.
Let be a graph that satisfies substructure property and be any vertex of . If , then is Type 1 with respect to .
Proof.
The following observation is useful for deciding the type of a graph with respect to a pendent vertex.
Lemma 2 (Type with respect to a pendent vertex).
Let be a graph and . Let with being the vertex in . Suppose each component of satisfies substructure property. Then, is Type 1 with respect to if and only if is Type 1 with respect to .
Proof.
In any eternal vertex cover class of with guards in which is occupied in every configuration^{2}^{2}2In the version of the problem where more than one guard is allowed on a vertex, we still can assume without loss of generality that has only one guard in any configuration. This is because instead of placing more than one guard on , it is possible to place all but one of those guards on ., must also be occupied in every configuration (otherwise, an attack on the edge cannot be defended maintaining a guard on ). Hence, the induced configurations on define an eternal vertex cover class of in which is occupied in every configuration. It follows that . Moreover, from an eternal vertex cover class of with always occupied, we can get an eternal vertex cover class of with always occupied by placing an additional guard at . Hence, . Thus, . Note that, by Observation 1, .
First, suppose is Type 1 with respect to . Then, and we get , which means that is Type 1 with respect to .
Now, suppose is Type 2 with respect to . Then, . Further, by Observation 3, if is a cut vertex in , then all the components of are Type 2 with respect to . Irrespective of whether is a cutvertex of or not, by Lemma 1, . Hence, . Thus, if is Type 2 with respect to , then is Type 2 with respect to . ∎
Now we give some observations that are useful for deciding the type of a graph with respect to a degree vertex.
Lemma 3.
Let be any graph and suppose is a degree vertex in such that its neighbors , are not adjacent. Let be the graph obtained by deleting and adding an edge between and . Then, .
Proof.
We first give a proof for the version of the problem where at most one guard is allowed on a vertex.
Consider a minimum eternal vertex cover class of . Note that, at least one among and is occupied in each configuration of . Let . It is easy to see that each is a valid vertex cover of . If , are configurations in obtainable from each other by a single step of valid movement of guards, it is also easy to verify that the corresponding configurations and of are obtainable from each other by a single step of valid movement of guards. From this, it follows easily that is an eternal vertex cover class of with always occupied. Hence, .
The correspondence between configurations of and works in the reverse direction as well. Let be an eternal vertex cover class of in which is permanently occupied. Let . Any configuration in must contain at least one of and . Therefore, the corresponding configuration is a vertex cover of . Moreover, whenever the guards in move from a configuration to in via a reconfiguration of guards which involves moving the guard from to and to , we can simulate the behavior in by assuming that the guard on is moving to (similarly while moving from to and to ). This corresponds to a valid movement of guards in from configuration to . From this, it follows easily that is an eternal vertex cover class of . Thus, .
Now, let us consider the version of the problem where more than one guard is allowed on a vertex. It is easy to modify the first part of the proof and show that . In the second part of the proof, if is a configuration in such that for each there are exactly guards on , then define the corresponding configuration of to have guards on and for each , guards on . This modification is sufficient to prove . ∎
Definition 7.
Let be the set of cut vertices of a graph . If is a block of , the set of components of is defined as
.
If is a path in , then the set of components of is defined as
.
Definition 8.
For a block (respectively, a path ) of connected graph , the type of a component (respectively, component) is its type with respect to the common vertex it has with (respectively, ). For , we define (respectively, ) to be the set of all components (respectively, components) of that are Type .
If is a block (respectively, is a path) of a connected graph , such that all components (respectively, components) of satisfy substructure property, then we can easily obtain a lower bound on the total number of guards on (respectively, on ) in any eternal vertex cover of or its extensions. The notation introduced below is to abstract this lower bound.
Definition 9.
For a block of connected graph , we define
Similarly, for a path of connected graph , we define
.
Remark 3.
If is a block (respectively, is a path) of a connected graph , such that all components (respectively, components) of satisfy substructure property, then the total number of guards on
(respectively, on ) in any eternal vertex cover of or its extensions is at least (respectively, ).
Definition 10 (Vertex bunch of a path).
Let be a path in a connected graph . The vertex set is the vertex bunch of in , denoted by .
Definition 11 (Eventful path).
Let be a connected graph and be the set of cut vertices of . A path in a graph is an eventful path if

is either an induced path in or a path obtained by removing an edge from an induced cycle in .

the endpoints of are in and

any subpath of with both endpoints in has even.
Lemma 4.
Let be a connected graph and let be an eventful path in . Let be the set of cut vertices of . If each component in satisfies the substructure property, then in any eternal vertex cover configuration of , the total number of guards on is at least . Moreover, if and the number of guards on is exactly equal to the above expression, then at least one of the neighbors of the endpoints of outside has a guard on it.
Proof.
Consider any subpath of such that both endpoints of are in and none of its intermediate vertices are from . Let be an eternal vertex cover configuration of . Since is eventful, is even and in any vertex cover of , at least internal vertices of must be present. Using this along with the substructure property of components proves the first part of the lemma.
Now, suppose and the number of guards in the configuration on is exactly equal to the expression given in the lemma. Now, for contradiction, let us assume that none of the neighbors of the endpoints of outside has a guard in . Consider an attack on an edge , where is an endpoint of and is a neighbor of outside . To defend this attack, a guard must move from to . Note that, no guards can move to from outside . Hence, while defending the attack, the number of guards on decreases at least by one. But, then the new configuration will violate the first part of the lemma. Hence, it must be the case that at least one of the neighbors of the endpoints of outside has a guard in . ∎
Definition 12 (Maximal uneventful path).
Let be a connected graph and let be the set of cut vertices of . A path in is a maximal uneventful path in if


is odd and

is a maximal induced path in satisfying the above two conditions.
The next lemma is applicable to any connected graph that contains a block which is a cycle such that all components satisfy the substructure property. Since each block of a cactus is either a cycle or an edge, this lemma will be useful for computing the eternal vertex cover number of cactus graphs. The proof of the lemma makes use of the fact that can be partitioned into a collection of edge disjoint paths which are either eventful paths or maximal uneventful paths.
Lemma 5.
Let be a cycle forming a block of a connected graph and let be the set of cut vertices of . Suppose each component of that belongs to satisfies the substructure property. If , then . Otherwise, .
Proof.
Let and . For each component of that belongs to , let be the vertex that has in common with . Let be a minimum eternal vertex cover of . Note that the condition stated in Lemma 4 has to simultaneously hold for all subpaths of the cycle that are eventful in .
Let be the number of maximal uneventful paths in and let be these listed in the cyclic order along . To protect the edges within each , should contain at least guards. If there are exactly guards on , the end vertices of are not occupied and alternate vertices in are occupied by guards.

Case 1 :

when is odd.
In this case, from Definition 11, it follows that is odd.
Suppose . Let be the subpath obtained from by deleting the edges of . It is easy to see that is an eventful path. If contains only guards, then the end vertices of are not occupied by guards and the condition stated in Lemma 4 cannot hold for . Therefore, the lemma holds when .

Suppose . Then, if and (+ is mod ) respectively contains only and guards and the vertex bunch of the path between the last vertex of and the first vertex of contains exactly as many guards as mentioned in the first part of Lemma 4, the condition stated in the second part of Lemma 4 cannot hold for . Since this is true for all , and the condition stated in Lemma 4 has to simultaneously hold for all subpaths of the cycle that are eventful in , a simple counting argument shows that number of guards in should be at least .
Thus, we know that is at least the expression given above. If , it is easy to show that these many guards are also sufficient. The guards on can defend any attack on edges of while keeping always occupied. Attacks on edges of components can be handled, maintaining always occupied and having exactly guards on each component .


When is even
In this case, is also even. A similar counting argument will show that is given by the expression in the statement of the lemma.


Case 2 :

when is even.
Suppose there are exactly guards on . Then, it is not difficult to see that in order to satisfy the condition stated in Lemma 4 for all eventful subpaths of the cycle, the configuration of guards should be such that
All cut vertices have guards.

while going around the cycle (discarding the cut vertices), noncut vertices are alternately guarded and unguarded.

each contains exactly guards

each contains exactly guards.
Now, consider a Type 1 component . By the conditions listed above, must be occupied in every configuration. Hence, there is a sequence of attacks on that would eventually lead to a configuration with at least guards on to defend the attack. However, in that configuration, the conditions listed above will not be satisfied. Hence, we need at least one more guard. We argue below that with one more guard, we can maintain the following invariants in every configuration:

All cut vertices have guards

while going around the cycle (discarding the cut vertices), noncut vertices are alternately guarded and unguarded

one component contains exactly guards.

all other contain exactly guards each.

each contains exactly guards.
When there is an attack on an edge of a Type 1 component containing only guards, we need to reconfigure guards in such a way that after the reconfiguration, the Type 1 component that presently has guards will have one less guard and gets one more guard. Since and are Type 1, this is always possible by an appropriate shifting of guards through the cycle . In this way, the invariants stated above can be maintained consistently. Hence, is as given in the statement of the lemma.


when is odd.
In this case, note that . As noted earlier, is odd and . Using similar arguments as in the case when there are no Type 1 components, we can show that is at least . With these many guards, it is possible to protect keeping the following invariants in all configurations.
All cut vertices have guards

at most one contains exactly guards

all other contain exactly guards

the maximal uneventful paths and in that are respectively clockwise and anticlockwise nearest to the Type 1 component with guards (if it exists) respectively contain and guards

each contains exactly guards.

Hence, in this case also, the lemma holds.

∎
The following observation gives a method to compute the type of a graph with respect to degreetwo vertices in blocks which are cycles.
Lemma 6.
Let be a cycle of vertices, forming a block of a connected graph . Let be the set of cut vertices of and let . Suppose each component in satisfies the substructure property. Let . The type of with respect to can be computed as follows.

If and is even, then . If and is odd, then . In both cases, is Type 1 with respect to .

If and is even, then and is Type 1 with respect to . If and is odd, then and is Type 2 with respect to .
Proof.
This can be proved using Lemma 5 and Lemma 3. Let be the graph obtained by deleting the two edges incident on from and adding an edge between its neighbors. Let be the cycle obtained by deleting the two edges incident on from and adding an edge between its neighbors. We have and . Further, if is the set of cut vertices of , then .

If , then using Lemma 5 for and , we can see that when is even, and when is odd, . Therefore, by Lemma 3, when is even, and when is odd, . Further, using Lemma 5 for , we can see that when is even, and when is odd, then . Therefore, when is even, and when is odd, . Hence, when is even, is Type 1 with respect to and when is odd, is Type 2 with respect to .
∎
4 Computing eternal vertex cover number of cactus graphs
Theorem 1.
Every cactus graph satisfies substructure property.
Proof.
Let be a cactus graph. The proof is using an induction on the number of cutvertices in .
In the base case, is a cactus without a cut vertex. Then, is either a single vertex, a single edge or a simple cycle. In all these cases, the lower bound for the number of guards on , specified by substructure property is equal to the vertex cover number of the respective graphs. Hence, the theorem holds in the base case.
Now, let us assume that the theorem holds for any cactus with at most cutvertices. Let be a cactus with cut vertices, for and let be the set of cut vertices of . Let be a noncut vertex of and be an arbitrary extension of . We need to show that in any eternal vertex cover configuration of , the number of guards on is as specified by the substructure property. Since is a noncut vertex of the cactus , either it is a degreeone vertex of or it is a degree vertex of that is in some block of , where is a cycle. We want to compute a lower bound on the number of guards on in an arbitrary eternal vertex cover configuration of .
First, consider the case where is a degreeone vertex of . Let be the neighbor of in and let . Since has at least one cutvertex, must be a cut vertex in .

When is a cutvertex of : Consider any component of . is a cactus and the number of its cut vertices is less than that of . Hence, satisfies the substructure property. Further, is a extension of . In , the number of guards on is at least if and it is if . The total number of guards on is at least . If is occupied in , then the total number of guards on is at least the same as that of as given by Lemma 1. If is not occupied in , then to defend an attack on the edge , a guard from must move to . Hence, in , the number of guards in should have been one more than the minimum mentioned earlier. Hence, in this case also, the number of guards on in would have been at least .
By Lemma 1, . By Lemma 2, the type of with respect to is the same as the type of with respect to . Hence, if is Type 1 with respect to , we have . We have seen that the number of guards on is at least . If is Type 2 with respect to , then we have . Since , in this case we must have . We have seen that the number of guards on is at least . Hence, the substructure property holds in both cases.

When is not a cut vertex of : In this case, is a extension of . By substructure property of , it follows that in configuration , the number of guards on must be at least if is Type 1 with respect to and at least if is Type 2 with respect to . By Lemma 1, when is Type 1 with respect to , and when is Type 2 with respect to , . By Lemma 2, the type of with respect to is the same as the type of with respect to . Hence, if is Type 1 with respect to , we have . The number of guards on is at least . If is Type 2 with respect to , we have . Since , in this case we must have . The number of guards on is at least . Hence, the substructure property holds in both cases.
Now, consider the case when is a degreetwo vertex of that is in some block of , where is a cycle. Suppose . Let be the set of cut vertices of and . As noted earlier, we have to compute a lower bound on the number of guards on in an arbitrary eternal vertex cover configuration of . Let and respectively be the clockwise and anticlockwise nearest vertices to in . Let be the path in between and that does not contain . Note that, every component of satisfies substructure property by our induction hypothesis and is an extension for each of them. Hence, we have a lower bound on the number of guards on , for each . Similarly, the condition stated in Lemma 4 needs to be satisfied for each eventful subpath of .

If : By similar arguments as in the proof of Lemma 5, we can see that the number of guards on in must be at least . By Lemma 6, when is even, is Type 1 with respect to and . Since the number of guards on is at least , we are done. Similarly, when is odd, is Type 2 with respect to and and we are done.
Thus, in all cases, the lower bound on the number of guards on in an arbitrary eternal vertex cover configuration of satisfies the condition stated in substructure property. Hence, satisfies substructure property.
Comments
There are no comments yet.