Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is known to be NP-hard in general and even for bipartite graphs. There is a quadratic complexity algorithm known for this problem for chordal graphs. Maximal outerplanar graphs forms a subclass of chordal graphs, for which no algorithm of sub-quadratic time complexity is known. In this paper, we obtain a linear time recursive algorithm for computing eternal vertex cover number of maximal outerplanar graphs.
Suppose at instant , guards are placed in a configuration and an attack occurs on an arbitrary edge ∈ (), then a guard at either or (or both) must move across the edge. Other guards may or not move across one of their neighboring edges simultaneously. At the end of these movements, the next configuration +1 is reached. To ensure that all edges remain guarded at the instant + 1, we require +1 to be a vertex cover of . The minimum number of guards necessary for a graph to be protected against any infinite sequence of single edge attacks is called the eternal vertex cover number of , denoted by evc(). The eternal vertex cover problem has two models. The first one allows only at most one guard on a vertex in any configuration, while in the second model this constraint is absent. The results in this paper work in both the models.
Computing evc() for an arbitrary graph is NP-hard, though in PSPACE [
An outerplanar graph is a planar graph that admits a planar embedding with all its vertices
lying on the exterior face and it is maximal outerplanar if addition of any more edges between
existing vertices will make the graph not outerplanar. Since maximal outerplanar graphs are
chordal, it follows from [
Our algorithm takes a maximal outerplanar graph on at least three vertices and an edge on the outer face of and recursively computes evc(), mvc() along with some related parameters. If both and are of degree greater than two, then the recursion is applied on the two induced subgraphs and of as shown in Figure 1. Otherwise, the recursion works on the graph obtained by deleting the degree two end point of the edge from . Since evc() happens to be not merely a function of the eternal vertex cover number and vertex cover number of these associated subgraphs, the algorithm has to recursively compute this larger set of parameters. The linear time complexity of the algorithm is derived from Theorems 1 to 4, which assert that evc() can be determined in constant time from this larger set of parameters of the associated subgraphs. Apart from the algorithmic result, these theorems serve to demonstrate the structural connection between the minimum vertex cover problem and the eternal vertex cover problem for maximal outerplanar graphs.
such that is -defendable with all vertices of occupied in all configurations. Similarly, Gu
Gv w mvc () denote the size of the smallest cardinality vertex cover of containing all vertices of . When = {1 . . . } for 1 ≤ ≤ 3, we shorten the notation evc{1...}() and mvc{1...}() as evc1... () and mvc1... () respectively.
Proofs omitted from the main content due to space constraints are available in the arXiv
preprint [
The following proposition is a direct consequence of Proposition 1.
Proposition 2. Let be a maximal outerplanar graph with an edge . Then, evc() ≤ evc() ≤ evc() + 1.
From now on, whenever we say a graph is maximal outerplanar, we assume a fixed outerplanar embedding of the graph. For a maximal outerplanar graph on at least three vertices and any edge on the outer face of , we use the notation ∆( ) to denote the unique common neighbor of and .
Definition 1 (-segments). Let be a maximal outerplanar graph with at least three vertices. Let be an edge on the outer face of . Let = ∆( ). We define the graph () (respectively, ()) to be the maximal biconnected outerplanar subgraph of that satisfies the following two properties (see Figure 1): 1. The edge (respectively, ) is on the outer face of () (respectively, ()). 2. () (respectively, ()) does not contain the vertex (respectively ). () and () will be called the segments of .
Note 1. We will write and instead of () and () when there is no scope for confusion. Observe that and will be single edge graphs if is a triangle. Definition 2 (mvc and evc parameters). For a maximal outerplanar graph and an edge , the set of parameters M (, ) = {mvc(), mvc(), mvc(), mvc()} is called the (set of) mvc parameters of with respect to and the set E (, ) = {evc(), evc(), evc(), evc()} is called the (set of) evc parameters of with respect to .
The following proposition that gives the mvc and evc parameters of a triangle is the base case of the recursive computation of these parameters for larger graphs described in subsequent sections.
Proposition 3. Suppose is a triangle and an edge of it. Then, 1. mvc() = mvc() = mvc() = mvc() = 2 2. evc() = evc() = evc() = 2 and evc() = 3
Throughout this section, we assume that is a maximal outerplanar graph of at least four vertices, is an edge on the outer face of and = ∆( ). The results in this section show that the mvc parameters of with respect to the edge - viz., M (, ), can be computed in constant time if the mvc parameters of with respect to - viz., M (, ) and the mvc parameters of with respect to - viz., M (, ) are given.
The following observation is easy to see.
Observation 1. If () = 2 and () > 2, then, 1. mvc() = mvc( ∖ ) 2. mvc() = mvc( ∖ ) + 1 3. mvc() = mvc() 4. mvc() = mvc( ∖ ) + 1
The following theorem is a consequence of Observation 1.
Theorem 1. Let be a maximal outerplanar graph and be an edge on the outer face of such that () = 2. Let = ∆( ).
1. Given M ( ∖ , ), it is possible to compute mvc() in constant time. 2. Given mvc() and M ( ∖ , ), it is possible to compute the remaining mvc parameters of with respect to in constant time.
Now, we look at the computation of M (, ) when () > 2 and () > 2. The following proposition is easy to obtain.
Proposition 4. If () > 2 and () > 2, then mvc() ∈ {mvc() + mvc() − 1, mvc() + mvc()}.
The following lemma gives a method to compute mvc() using M (, ) and M (, ). Lemma 1. If () > 2 and () > 2, then mvc() = min{mvc() + mvc() − 1, mvc() + mvc() − 1, mvc() + mvc()}.
The next lemma shows that given mvc(), M (, ) and M (, ), the values of mvc(), mvc() and mvc() are computable in constant time.
Lemma 2. If () > 2 and () > 2, then: 1. If mvc() = mvc() + mvc() − 1, then mvc() = mvc() + mvc() − 1, mvc() = mvc() + mvc() − 1 and mvc() = mvc() + mvc() − 1. 2. If mvc() = mvc() + mvc(), then mvc() = min{mvc() + mvc(), mvc() + mvc(), mvc() + 1}, mvc() = min{mvc() + mvc(), mvc() + mvc(), mvc() + 1} and mvc() = min{mvc() + mvc(), mvc() + 1}.
From Lemma 1 and Lemma 2, the following theorem is immediate.
Theorem 2. Let be a maximal outerplanar graph and be an edge on the outer face of such that () > 2 and () > 2. Let = ∆( ).
1. Given M (, ) and M (, ), it is possible to compute mvc() in constant time. 2. Given mvc(), M (, ) and M (, ), it is possible to compute the remaining mvc parameters of with respect to in constant time.
In this section, we will derive some bounds on the evc parameters of a maximal outerplanar graph. These bounds will be used in the next section for the recursive computation of the evc parameters. Throughout this section, we consider to be a maximal outerplanar graph on at least four vertices, an edge on its outer face and = ∆( ). First, we derive some bounds for E (, ) when () = 2.
The proof of the lemma below is easy to obtain by repeated applications of Proposition 1. Lemma 3. If is a degree-2 vertex in , then: 1. evc() ≤ evc() = evc( ∖ ) + 1 2. evc() = evc( ∖ ) + 1 3. evc() ≥ {mvc( ∖ ) + 1, evc( ∖ )} 4. evc() = max{mvc(), evc()}
Now, we derive some upper bounds for E (, ) when () > 2 and () > 2. The following proposition is a direct consequence of Proposition 1.
Proposition 5.
1. max∈ () mvc() ≤ min{mvc() + evc() − 1,
mvc() + evc() − 1, mvc() + evc()} 2. max∈ () mvc() ≤ min{evc() + mvc() − 1,
evc() + mvc() − 1, evc() + mvc()}
The proof of Lemma 4 follows easily from propositions 1 and 5.
Lemma 4. If () > 2 and () > 2, then: 1. evc() ≤ min{mvc() + 1, evc() + evc() − 1} 2. evc() ≤ max{, }, where = min{evc() + mvc() − 1, evc() + mvc() − 1, evc() + mvc()} and = min{mvc() + evc() − 1, mvc() + evc() − 1, mvc() + evc()}
In a similar way, we can also prove Lemma 5 and Lemma 6, which give upper bounds on evc() and evc() respectively.
Lemma 5. If () > 2 and () > 2, then: 1. evc() ≤ min{evc() + 1, mvc() + 1, evc() + evc() − 1} 2. evc() ≤ max{, }, where = min{evc() + mvc(), evc() + mvc() − 1} and = min{mvc() + evc(), mvc() + evc() − 1} Lemma 6. If () > 2 and () > 2, then: 1. evc() ≤ min{evc() + 1, mvc() + 1, max{1, 2}}, where 1 = {evc() + mvc() − 1, evc() + mvc()} and 2 = {mvc() + evc() − 1, mvc() + evc()} 2. evc() ≤ min{, evc() + evc() − 1, evc() + evc(), evc() + evc()}, where = max{evc() + evc() − 1, evc() + mvc()} The next lemma gives some lower bounds for E (, ) when () > 2 and () > 2. Lemma 7. If () > 2 and () > 2, then: 1. evc() ≥ max{evc() + mvc() − 1, mvc() + evc() − 1} 2. evc() ≥ max{evc(), mvc() + evc() − 1, evc() + mvc() − 1, evc() + mvc() − 1} 3. evc() ≥ max{evc(), evc(), evc(), mvc() + evc() − 1, evc() + mvc() − 1, evc() + mvc() − 1, mvc() + evc() − 1}
Let be a maximal outerplanar graph with at least four vertices, be an edge on its outer face and = ∆( ). In this section, we describe the method of computing E (, ) using the bounds obtained in Section 4. 5.1. Computing E (, ) when () = 2 In this subsection, we consider the case when is a degree-2 vertex in . Bounds obtained in Proposition 2 and Lemma 3 together with Proposition 1 give the following.
Lemma 8. evc() = max{mvc( ∖ ) + 1, evc( ∖ )}.
From Lemma 3 and Lemma 8, the following theorem is immediate.
Theorem 3. Let be a maximal outerplanar graph and be a degree-2 vertex in with neighbors and .
1. Given mvc( ∖ ) and E ( ∖ , ), it is possible to compute evc() in constant time. 2. Given evc(), M (, ) and E ( ∖ , ), it is possible to compute the remaining evc parameters of with respect to in constant time. 5.2. Computing E (, ) when () > 2 and () > 2 Now, we will see how E (, ) can be computed when () > 2 and () > 2 using mvc(), M (, ), M (, ), E (, ) and E (, ). For this subsection, we will assume that () > 2 and () > 2. We will also assume that mvc() = and mvc() = .
Lemma 9 handles the computation of evc(). The proof of this lemma uses the bounds obtained in Lemma 4 and Lemma 7.
Lemma 9.
1. If evc() = and evc() = , then 2. If evc() = and evc() = + 1, then • evc() = max{evc() + mvc() − 1, mvc() + evc() − 1}.
• evc() = min{mvc()+1, evc()+evc()− 1, mvc()+evc()− 1}. 3. If evc() = + 1 and evc() = + 1, then • evc() = min{mvc() + 1, max{evc() + mvc() − 1, mvc() + evc() − 1}}.
Lemmas 10-12 deal with the computation of the remaining parameters in E (, ) using evc(), M (, ), M (, ), M (, ), E (, ) and E (, ). The proofs of these lemmas critically use the bounds stated in lemmas 5-7.
Lemma 10. Suppose evc() = and evc() = .
1. If evc() = + − 1, then 2. If evc() = + , then • evc() = evc() + mvc() − 1. • evc() = evc() + mvc() − 1. • evc() = {mvc() + 1, evc() + evc() − 1}. • evc() = evc() = evc().
• evc() = min{evc() + mvc(), evc() + mvc(), mvc() + 1}. Lemma 11. Suppose evc() = and evc() = + 1.
1. If mvc() = + − 1, then • evc() = mvc() + evc() − 1. • evc() = min{mvc() + 1, evc() + evc() − 1, max{mvc() + evc() − 1, evc() + mvc()}}. • evc() = min{mvc() + 1, evc() + evc() − 1, evc() + max{evc() − 1, mvc()}}. 2. If mvc() = () = + , then • evc() = evc() + evc() − 1 • evc() = min{mvc() + 1, evc() + evc() − 1, max{mvc() + evc() − 1, evc() + mvc()}} • evc() = min{evc() + 1, max{evc() + mvc(), evc() + evc() − 1}}. 3. If evc() = + + 1, then • evc() = evc() = evc() • evc() = min{mvc() + 1, evc() + evc()}.
Lemma 12. Suppose evc() = + 1 and evc() = + 1. Then, 1. evc() = min{mvc() + 1, evc() + evc() − 1} 2. evc() = min{mvc() + 1, evc() + evc() − 1} 3. • If mvc() ≤ + then evc() = mvc() + 1.
• Otherwise, evc() = (mvc() + 1, (1, 2)), where 1 = (evc() + mvc() − 1, evc() + mvc()) and 2 = (evc() + mvc() − 1, evc() + mvc()).
From Lemma 9-12, the following theorem is immediate.
Theorem 4. Let be a maximal outerplanar graph and be an edge on the outer face of such that () > 2 and () > 2. Let = ∆( ).
1. Given M (, ), E (, ), M (, ) and E (, ), it is possible to compute evc() in constant time. 2. Given evc(), M (, ), M (, ), E (, ), M (, ) and E (, ), it is possible to compute the remaining evc parameters of with respect to in constant time.
In this section, we formulate a divide and conquer algorithm that takes a pair (, ) as input, where is a maximal outerplanar graph and is an edge on its outer face, and recursively computes M (, ) and E (, ). The case when is a triangle forms the base case of the recursion and it is handled using Proposition 3. Let = ∆( ). If () > 2 and () > 2, then the recursion works on (, ) and (, ) using Theorem 2 and Theorem 4. Otherwise, suppose ′ is the degree-2 vertex among and and ′ is the other one.
A high level overview of our method is given in Algorithm 1. To obtain the linear time guarantee, we need to ensure that the time spent in steps other than the recursive calls is (1).
most crucial part of our algorithm. However, we will have to avoid the explicit computation of the subgraphs and passing them as explicit parameters in the recursive calls using a refinement of Algorithm 1.
Algorithm 1 To compute M (, ) and E (, ) of a maximal outerplanar graph with an edge on its outer face. [A high level overview] Inputs: A maximal outerplanar graph with at least three vertices, an edge on the outer face of .
Outputs: M (, ) and E (, ).
1: procedure EVC_Parameters(, ) 2: ← ∆( ). 3: if is a triangle then 4: mvc()=evc()=mvc()=mvc()=mvc()=2, evc()=evc()=2, evc()=3.
else if One end point of is degree-2 then ′=degree-2 end point of , ′=higher degree end point of .
Compute mvc() using Theorem 1 (Part 1).
Compute mvc(), mvc() and mvc() using Theorem 1 (Part 2).
Compute evc() using Theorem 3 (Part 1).
Compute evc() in constant using Theorem 3 (Part 2).
For the purpose of a refined algorithm, we maintain a Vertex Edge Face Adjacency List data structure using which the following operations are possible: • For any edge , in constant time we can traverse through the internal faces on which the edge lies. • For any internal face , in constant time we can traverse through the edges on the boundary of .
The details of the data structure is given in Figure 2. For any edge , there are links between the edge node and the edge node . For each face in , the face node representing contains links to the edge nodes corresponding to the bounding edges of and vice versa. Remember that each edge of has two edge nodes corresponding to it. Hence, for each face node , there are six pointers to edge nodes. For each face node, there is a visit field which is initialized to unvisited. Each vertex node has a mark field, which is initialized to unmarked, the cur-edge field which is initialized to null and a pointer to the beginning of the adjacency list of that vertex. struct vertex f int vnum; int degree boolean mark; edgenode*head; edgenode *cur-edge; g struct vertex Varray[size] struct edgenode f int vertex1; int vertex2; facenode f1; facenode f2 ; edgenode *pair; edgenode *next; g struct facenode f edgenode e1; edgenode pair-e1; edgenode e2; edgenode pair-e2; edgenode e3; edgenode pair-e3; boolean visit; g
Algorithm 2 gives a linear time refinement of Algorithm 1. To compute the evc number
of a maximal outerplanar graph, we pass an edge on the outer face of the graph as input
parameter to the algorithm. We assume that the vertex face adjacency list of this graph is
maintained as a global data structure. It may be noted that the Vertex Edge Face Adjacency List
of a maximal outerplanar graph can be produced in linear time by modifying the algorithm
suggested by N. Chiba and T. Nishizeki [
Using the visit field of faces in the data structure, we avoid passing the subgraph as an explicit parameter in recursive calls. Initially, the visit field of all (internal) faces are set to unvisited. Note that, the edge is present in exactly one unvisited face initially. In subsequent recursive calls, the following invariants will be maintained: • the edge passed as parameter to the recursion is present in exactly one unvisited face . • The -segment of that contains the unvisited face containing is precisely the subgraph on which the recursive call in Algorithm 1 would have been made. Now we explain how the correspondence between the computational steps of Algorithm 1 and Algorithm 2 are maintained.
In line number 2 of Algorithm 1, we find the unique common neighbor of and in the input graph. Instead of this step, line number 2 of Algorithm 2 identifies as the third vertex in the unique unvisited face containing the edge . After this, the face is marked as visited in line number 4 of Algorithm 2 and subsequently the edges and are in at most one unvisited face each.
Algorithm 1 is divided into following three cases: 1. The input graph is a triangle (degrees of both the end vertices of the edge are 2). Refer to line number 3 of Algorithm 1. 2. The input graph is not a triangle and exactly one end vertex of the input edge is of degree 2. Refer to line number 5 of Algorithm 1. 3. The input graph is not a triangle and both the end vertices of the input edge has degree greater than 2. Refer to line number 12 of Algorithm 1.
The three cases of Algorithm 2 corresponding to the three cases of Algorithm 1 are as follows: 1. Both edges and lie in no unvisited face and thereby is a triangle. Refer to line number 5 of Algorithm 2. 2. Exactly one among the edges and lie in an unvisited face. Refer to line number 8 of Algorithm 2.
3. Both and lie in one unvisited face each. Refer to line number 16 of Algorithm 2. Algorithm 2 For computing M (, ) and E (, ) of a maximal outerplanar graph with an edge on its outer face in linear time Inputs: An edge on the outer face of the maximal outerplanar graph that has at least three vertices.
Output: M (, ) and E (, ).
Assumption: The vertex edge face adjacency list is maintained globally.
1: procedure EVC_Parameters 2: Identify the unvisited face in which the edge lie. 3: ◁ Possible in constant time by vertex edge face adjacency list 4: Set the visit field of the face to visited. 5: if neither edge nor edge is in any unvisited faces then 6: ◁ Possible to check in constant time using vertex edge face adjacency list 7: mvc()=evc()=mvc()=mvc()=mvc()=2, evc()=evc()=2, evc()=3. 8: else if exactly one among and lie in an unvisited face then 9: ◁ Possible to check in constant time using the vertex edge face adjacency list 10: be the edge among and that lie in an unvisited face. 11: − ← EVC_Parameters(). 12: Compute mvc() in constant time using Theorem 1 (part 1). 13: Compute mvc(), mvc() and mvc() in constant time using Theorem 1 (part 2). 14: Compute evc() in constant time using Theorem 3 (part 1). 15: Compute evc() in constant using Theorem 3 (part 2). 16: else 17: 1 − ← EVC_Parameters(). 18: 2 − ← EVC_Parameters(). 19: Compute mvc() in constant time using Theorem 2 (part 1). 20: Compute mvc(), mvc(), mvc() in constant time using Theorem 2 (part 2). 21: Compute evc() in constant time using Theorem 4 (part 1). 22: Compute evc(), evc(), evc() in constant time using Theorem 4 (part 2). 23: end if 24: return (M (, ) and E (, )) 25: end procedure
Now, we show that line number 3 of Algorithm 1 is equivalent to line number 5 of Algorithm 2. In line number 3 of Algorithm 1, we check whether the input graph is a triangle, which is the base case. Equivalently, by the invariants stated above, in Algorithm 2, it is enough to check if the -segment of containing the face is a triangle. In line 5 of Algorithm 2, we do the following in constant time using vertex edge face adjacency list: We check if or lie in any unvisited face. If neither nor lie in an unvisited face, then we can infer that -segment of containing the face is a triangle.
In line 5 of Algorithm 1, we check whether exactly one end vertex of the edge is of degree 2. In line number 8 of Algorithm 2, if (respectively, ) is in any univisited face, then we can infer that the degree of the vertex (respectively, ) is greater than 2 in the -segment of that contains the face . Otherwise, the degree of (respectively, ) in the -segment of that contains the face is equal to 2.
In line number 7 of Algorithm 1, we recursively call the function EVC_Parameters with two input parameters: (1) the graph obtained by deleting the degree-2 endpoint ′ of the edge from the input graph and (2) the edge ′ bounding the face , where degree of ′ is greater than 2 in the input graph. Since in Algorithm 2, is already marked as visited in line number 4, it is enough to invoke the recursive call with the edge as parameter, where is the bounding edge of the face with one unvisited face adjacent to it. This is achieved in line number 12 of Algorithm 2, in which we recursively call the function EVC_Parameters with the edge as input, where is that edge among the edges and which lies in an unvisited face. Note that the invariants of the Algorithm 2 are maintained.
The equivalence between line number 12 of Algorithm 1 and line number 16 of Algorithm 2 follows from our arguments so far. In line number 15 (respectively, 16) of Algorithm 1, a recursive call to the algorithm is made with input parameters: (1) (respectively, ), the -segment (respectively, -segment) of that does not contain the edge (respectively, ) and (2) the edge (respectively, ). Note that the edges bounding the face , other than , are used as parameters in these two calls. Equivalently, in line number 17 and 18 of Algorithm 2, recursive calls are made respectively with the edges and as input parameters. Since the face is marked as visited already, the invariants of the algorithm are maintained here as well.
Thus, we can see that Algorithm 2 is a linear time implementation of Algorithm 1.
This paper presents a linear time algorithm for computing the eternal vertex cover number
of maximal outerplanar graphs, lowering the best known upper bound to the complexity of
the problem from quadratic [