=Paper=
{{Paper
|id=Vol-3284/4871
|storemode=property
|title=Computing Eternal Vertex Cover Number on Maximal Outerplanar Graphs in Linear Time
|pdfUrl=https://ceur-ws.org/Vol-3284/4871.pdf
|volume=Vol-3284
|authors=Jasine Babu,Karunakaran Murali Krishnan,Veena Prabhakaran,Nandini J. Warrier
|dblpUrl=https://dblp.org/rec/conf/ictcs/BabuKPW22
}}
==Computing Eternal Vertex Cover Number on Maximal Outerplanar Graphs in Linear Time==
https://ceur-ws.org/Vol-3284/4871.pdf
Computing Eternal Vertex Cover Number of Maximal
Outerplanar Graphs in Linear Time
Jasine Babu1,β‘ , K. Murali Krishnan2,β , Veena Prabhakaran1,*,β and Nandini J. Warrier2,β
1
Indian Institute of Technology Palakkad, India
2
National Institute of Technology Calicut, India
Abstract
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.
Keywords
Eternal Vertex Cover, Maximal Outerplanar Graph, Linear Time Algorithm
1. Introduction
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.
Proceedings of the 23rd Italian Conference on Theoretical Computer Science, Rome, Italy, September 7-9, 2022
*
Corresponding author.
β
These authors contributed equally.
β‘
Jasine Babu acknowledges support from SERB Power Grant SPG/2021/003250
" jasine@iitpkd.ac.in (J. Babu); kmurali@nitc.ac.in (K. Murali Krishnan); veenaprabhakaran7@gmail.com
(V. Prabhakaran); nandini.wj@gmail.com (N. J. Warrier)
Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
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.
2. Preliminaries
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,
u v
Gu Gv
w
Figure 1: πΊπ’ is the π’π£ segment of this graph that contains π’ and πΊπ£ is the π’π£ segment that contains π£.
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 evcπ£1 ...π£π (πΊ) and mvcπ£1 ...π£π (πΊ) respectively.
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.
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
3. Computation of the mvc Parameters
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.
4. Bounds on the evc Parameters
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}
5. Computation of the evc Parameters
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
β’ evc(πΊ) = max{evcπ€ (πΊπ’ ) + mvc(πΊπ£ ) β 1, mvc(πΊπ’ ) + evcπ€ (πΊπ£ ) β 1}.
2. If evc(πΊπ’ ) = ππ’ and evc(πΊπ£ ) = ππ£ + 1, then
β’ 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
β’ evcπ’ (πΊ) = evcπ’π€ (πΊπ’ ) + mvc(πΊπ£ ) β 1.
β’ evcπ£ (πΊ) = evcπ£π€ (πΊπ£ ) + mvc(πΊπ’ ) β 1.
β’ evcπ’π£ (πΊ) = πππ{mvcπ’π£ (πΊ) + 1, evcπ’π€ (πΊπ’ ) + evcπ£π€ (πΊπ£ ) β 1}.
2. If evc(πΊ) = ππ’ + ππ£ , then
β’ 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.
6. A Linear Time Algorithm to Compute evc Number
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.
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.
5: else if One end point of π’π£ is degree-2 then
6: π’β² =degree-2 end point of π’π£, π£ β² =higher degree end point of π’π£.
7: Recursively call EVC_Parameters(πΊ β π’β² , π£ β² π€).
8: Compute mvc(πΊ) using Theorem 1 (Part 1).
9: Compute mvcπ’ (πΊ), mvcπ£ (πΊ) and mvcπ’π£ (πΊ) using Theorem 1 (Part 2).
10: Compute evc(πΊ) using Theorem 3 (Part 1).
11: Compute evcπ’π£ (πΊ) in constant using Theorem 3 (Part 2).
12: else
13: πΊπ’ β π’π£-segment of πΊ containing the vertex π’
14: πΊπ£ β π’π£-segment of πΊ containing the vertex π£
15: Recursively call EVC_Parameters(πΊπ’ , π’π€).
16: Recursively call EVC_Parameters(πΊπ£ , π£π€).
17: Compute mvc(πΊ) using Theorem 2 (Part 1).
18: Compute mvcπ’ (πΊ), mvcπ£ (πΊ), mvcπ’π£ (πΊ) using Theorem 2 (Part 2).
19: Compute evc(πΊ) using Theorem 4 (Part 1).
20: Compute evcπ’ (πΊ), evcπ£ (πΊ), evcπ’π£ (πΊ) using Theorem 4 (Part 2).
21: end if
22: return (M (πΊ, π’π£) and E (πΊ, π’π£))
23: end procedure
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 struct edgenode struct facenode
{ { {
int vnum; int vertex1 ; edgenode βe1 ;
int degree int vertex2 ; edgenode βpair-e1 ;
boolean mark; facenode βf1 ; edgenode βe2 ;
facenode βf2 ;
edgenode*head; edgenode βpair-e2 ;
edgenode *pair;
edgenode *cur-edge; edgenode *next; edgenode βe3 ;
} edgenode βpair-e3 ;
}
struct vertex Varray[size] boolean visit;
}
Figure 2: Details of the vertex edge face adjacency list data structure.
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:
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.
7. Conclusion
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.
References
[1] F. V. Fomin, S. Gaspers, P. A. Golovach, D. Kratsch, S. Saurabh, Parameterized algorithm for
eternal vertex cover, Information Processing Letters 110 (2010) 702 β 706.
[2] N. Misra, S. Nanoti, Eternal vertex cover on bipartite and co-bipartite graphs, CoRR
abs/2201.03820 (2022). URL: https://arxiv.org/abs/2201.03820. arXiv:2201.03820.
[3] J. Babu, L. S. Chandran, M. Francis, V. Prabhakaran, D. Rajendraprasad, N. J. Warrier, On
graphs whose eternal vertex cover number and vertex cover number coincide, Discrete
Applied Mathematics 319 (2022) 171β182. doi:https://doi.org/10.1016/j.dam.2021.
02.004.
[4] W. Klostermeyer, C. Mynhardt, Edge protection in graphs, Australasian Journal of Combi-
natorics 45 (2009) 235 β 250.
[5] H. Araki, T. Fujito, S. Inoue, On the eternal vertex cover numbers of generalized trees, IEICE
Transactions on Fundamentals of Electronics, Communications and Computer Sciences
E98.A (2015) 1153β1160. doi:10.1587/transfun.E98.A.1153.
[6] J. Babu, V. Prabhakaran, A. Sharma, A substructure based lower bound for eternal vertex
cover number, Theoretical Computer Science (2021). doi:https://doi.org/10.1016/j.
tcs.2021.08.018.
[7] J. Babu, V. Prabhakaran, A new lower bound for the eternal vertex cover number of graphs,
Journal of Combinatorial Optimization (2021) 1β17.
[8] J. Babu, K. M. Krishnan, V. Prabhakaran, N. J. Warrier, Eternal vertex cover number of
maximal outerplanar graphs, 2022. URL: https://arxiv.org/abs/2201.06577.
[9] N. Chiba, T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on
computing 14 (1985) 210β223.