A set π of vertices in a graph πΊ forms a vertex cover of πΊ if every edge in πΊ has at least one end point in π. The size of a minimum vertex cover in πΊ, called the vertex cover number of πΊ, will be denoted by mvc(πΊ). The eternal vertex cover problem of graphs is motivated by the following dynamic network security / fault-tolerance model. A network can be modeled by a graph πΊ(π, πΈ), where the nodes of the network are represented by the vertices of πΊ and the links by the edges of πΊ. The problem is to deploy a minimum set of guards at the nodes, so that if there is an attack (or fault) on a single link at any time, a guard is available at the end of the link, who can move across the link to defend (or repair) the attack (or fault). Simultaneously, the remaining guards need to reconfigure themselves, possibly by repositioning themselves to one of their adjacent nodes, so that any attack (or fault) on a single edge at any future instant of time can also be protected in the same manner. Thus, the model requires guaranteeing protection against single link attacks/failures ad-infinitum. It is immediate that lowest number of guards needed to achieve this goal in a graph πΊ is at least mvc(πΊ). If π guards are sufficient to achieve the goal, then we say that πΊ is π-defendable.
Formally, guards are initially placed on a vertex cover πΆ 0 of πΊ, forming an initial configuration.
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 [1], and is fixed parameter tractable with evc(πΊ) as parameter [1]. Recently, it was shown that the problem is NP-hard even for bipartite graphs [2]. It is also known that the problem is NP-complete for biconnected internally triangulated planar graphs [3]. Polynomial time algorithms for computing evc(πΊ) exactly were known only for very elementary graph classes such as an π(π) algorithm for trees [4], a polynomial time algorithm for a tree-like graph class [5] and a linear time algorithm for cactus graphs [6]. A recent structure theorem developed in [7] has resulted in a quadratic time algorithm for chordal graphs.
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 [7] that its evc number can be computed in quadratic time. We improve the complexity and show that the evc number of maximal outerplanar graphs can be computed in linear time. The techniques used here are fundamentally different from that used in the algorithm known for cactus graphs [6], which is based on the fact that no edge of a cactus graph lies on more than one cycle.
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.
Let πΊ(π, πΈ) be a graph with π β π . The parameter evc π (πΊ) denotes the minimum number π such that πΊ is π-defendable with all vertices of π occupied in all configurations. Similarly, Proofs omitted from the main content due to space constraints are available in the arXiv preprint [8]. Proposition 1 given below is an easy adaptation of a result given in [3]. Proposition 1. [3] Let πΊ(π, πΈ) be a maximal outerplanar graph with at least two vertices and π β π . If for every vertex π£ β π β π, mvc πβͺ{π£} (πΊ) = mvc π (πΊ), then evc π (πΊ) = mvc π (πΊ). Otherwise, evc π (πΊ) = mvc π (πΊ) + 1. Hence, evc π (πΊ) = max π£βπ (πΊ) mvc πβͺ{π£} (πΊ).
The following proposition is a direct consequence of Proposition 1.
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,
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.
The following theorem is a consequence of Observation 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.
The following lemma gives a method to compute mvc(πΊ) using M (πΊ π’ , π’π€) and M (πΊ π£ , π£π€).
The next lemma shows that given mvc(πΊ), M (πΊ π’ , π’π€) and M (πΊ π£ , π£π€), the values of mvc π’ (πΊ), mvc π£ (πΊ) and mvc π’π£ (πΊ) are computable 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.
If π’ is a degree-2 vertex in πΊ, then:
Now, we derive some upper bounds for E (πΊ, π’π£) when πππ πΊ (π’) > 2 and πππ πΊ (π£) > 2. The following proposition is a direct consequence of Proposition 1. Proposition 5.
The proof of Lemma 4 follows easily from propositions 1 and 5. 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.
1. If evc(πΊ π’ ) = π π’ and evc(πΊ π£ ) = π π£ , then
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(πΊ π£ ) = π π£ .
β’ 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. 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. In this case, the recursion works on (πΊ β π’ β² , π£ β² π€) using Theorem 1 and Theorem 3.
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). Theorems 1-4 guarantee that lines 8 β 11 and lines 17 β 20 work in constant time, forming the 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.
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 (πΊ, π’π£). π’ β² =degree-2 end point of π’π£, π£ β² =higher degree end point of π’π£.
Recursively call EVC_Parameters(πΊ β π’ β² , π£ β² π€).
Compute mvc(πΊ) using Theorem 1 (Part 1). 9:
Compute mvc π’ (πΊ), mvc π£ (πΊ) and mvc π’π£ (πΊ) using Theorem 1 (Part 2). Recursively call EVC_Parameters(πΊ π’ , π’π€).
Recursively call EVC_Parameters(πΊ π£ , π£π€). return (M (πΊ, π’π£) and E (πΊ, π’π£))
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. 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 [9] for listing all the triangles of a planar graph.
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: Identify the unvisited face π’π£π€ in which the edge π’π£ lie. Compute mvc(πΊ) in constant time using Theorem 1 (part 1).
Compute mvc π’ (πΊ), mvc π£ (πΊ) and mvc π’π£ (πΊ) in constant time using Theorem 1 (part 2). Compute mvc(πΊ) in constant time using Theorem 2 (part 1).
Compute mvc π’ (πΊ), mvc π£ (πΊ), mvc π’π£ (πΊ) in constant time using Theorem 2 (part 2).
Compute evc(πΊ) in constant time using Theorem 4 (part 1).
Compute evc π’ (πΊ), evc π£ (πΊ), evc π’π£ (πΊ) in constant time using Theorem 4 (part 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 [7] time to linear. The techniques presented in the paper make crucial use of the planarity of the underlying graph to yield a divide and conquer algorithm for computing the evc number of a maximal outerplanar graph. Attempts to generalize our techniques to maximal planar graphs may not be successful due to the known NP-hardness result on the evc computation of biconnected internally triangulated planar graphs [3]. The complexity status of the problem of computing the evc number of outerplanar graphs is open, and may be attempted using some techniques developed in this work. However, the observation that for a chordal graph, any vertex cover containing all its cut vertices is connected [3], which yields Proposition 1 that is extensively used in this work, does not hold for outerplanar graphs.