# s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal
Graphs111 An extended abstract [12] of this paper was presented at WG 2022 and
this version contains all proofs missing from the conference version.

Dibyayan Chakraborty ENS de Lyon, France L. Sunil Chandran Indian Institute of
Science, Bengaluru, India Sajith Padinhatteeri BITS-Pilani, Hyderabad. Raji.
R. Pillai Indian Institute of Science, Bengaluru, India

###### Abstract

In this paper, we study the computational complexity of $s$-Club Cluster
Vertex Deletion. Given a graph, $s$-Club Cluster Vertex Deletion ($s$-CVD)
aims to delete the minimum number of vertices from the graph so that each
connected component of the resulting graph has a diameter at most $s$. When
$s=1$, the corresponding problem is popularly known as Cluster Vertex Deletion
(CVD). We provide a faster algorithm for $s$-CVD on _interval graphs_. For
each $s\geq 1$, we give an $O(n(n+m))$-time algorithm for $s$-CVD on interval
graphs with $n$ vertices and $m$ edges. In the case of $s=1$, our algorithm is
a slight improvement over the $O(n^{3})$-time algorithm of Cao et al.(Theor.
Comput. Sci., 2018) and for $s\geq 2$, it significantly improves the state-of-
the-art running time $\left(O\left(n^{4}\right)\right)$.

We also give a polynomial-time algorithm to solve CVD on _well-partitioned
chordal graphs_ , a graph class introduced by Ahn et al.(WG 2020) as a tool
for narrowing down complexity gaps for problems that are hard on chordal
graphs, and easy on split graphs. Our algorithm relies on a characterisation
of the optimal solution and on solving polynomially many instances of the
Weighted Bipartite Vertex Cover. This generalises a result of Cao et
al.(Theor. Comput. Sci., 2018) on split graphs. We also show that for any even
integer $s\geq 2$, $s$-CVD is NP-hard on well-partitioned chordal graphs.

Keywords: Vertex deletion problem, Cluster Vertex Deletion,$s$-Club Cluster
Vertex Deletion, Well-partitioned chordal graphs, Interval graphs.

##  1 Introduction

Detecting “ _highly-connected_ ” parts or “ _clusters_ ” of a complex system
is a fundamental research topic in network science [39, 29] with numerous
applications in computational biology [13, 31, 7, 35, 36], machine learning
[6], image processing [38], etc. In a graph-theoretic approach, a complex
system or a network is often viewed as an undirected graph $G$ that consists
of a set of _vertices_ $V(G)$ representing the atomic entities of the system
and a set of _edges_ $E(G)$ representing a binary relationship among the
entities. A _cluster_ is often viewed as a dense subgraph (often a _clique_)
and _partitioning_ a graph into such clusters is one of the main objectives of
_graph-based data clustering_ [7, 34, 14].

Ben-Dor et al. [7] and Shamir et al. [34] observed that the clusters of
certain networks may be retrieved by making a small number of modifications in
the network. These modifications may be required to account for the errors
introduced during the construction of the network. In graph-theoretic terms,
the objective is to modify (e.g. edge deletion, edge addition, vertex
deletion) a given input graph as little as possible so that each component of
the resulting graph is a cluster. When deletion of vertices is the only valid
operation on the input graph, the corresponding clustering problem falls in
the category of _vertex deletion_ problems, a core topic in algorithmic graph
theory. Many classic optimization problems like Maximum Clique, Maximum
Independent Set, Vertex cover are examples of vertex deletion problems. In
this paper, we study popular vertex deletion problems called Cluster Vertex
Deletion and its generalisation $s$-Club Cluster Vertex Deletion, both being
important in the context of graph-based data clustering.

Given a graph $G$, the objective of Cluster Vertex Deletion (CVD) is to delete
a minimum number of vertices so that the remaining graph is a set of disjoint
cliques. Below we give a formal definition of CVD.

Cluster Vertex Deletion (CVD) Input: An undirected graph $G$, and an integer
$k$. Output: Yes, if there is a set $S$ of vertices with $|S|\leq k$, such
that each component of the graph induced by $V(G)\setminus S$ is a clique. No,
otherwise.

The term Cluster Vertex Deletion was coined by Gramm et al. [20] in $2004$.
However NP-hardness of CVD, even on planar graphs and bipartite graphs,
follows from the seminal works of Yannakakis [40] and Lewis & Yannakakis [25]
from four decades ago. Since then many researchers have proposed
_parameterized algorithms_ and _approximation algorithms_ for CVD on general
graphs [9, 37, 21, 18, 19, 32, 41, 16, 17, 4]. In this paper, we focus on
polynomial-time solvability of CVD on special classes of graphs.

Cao et al. [10] gave polynomial-time algorithms for CVD on _interval_ graphs
(see Definition 2) and _split_ graphs. Chakraborty et al. [11] gave a
polynomial-time algorithm for CVD on _trapezoid_ graphs. However, much remains
unknown: Chakraborty et al. [11] pointed out that computational complexity of
CVD on _planar bipartite_ graphs and _cocomparability_ graphs is unknown. Cao
et al. [10] asked if CVD can be solved on chordal graphs (graphs with no
induced cycle of length greater than 3) in polynomial-time. Ahn et al. [1]
introduced _well-partitioned chordal_ graphs (see Definition 1) as a tool for
narrowing down complexity gaps for problems that are hard on chordal graphs,
and easy on split graphs. Since several problems (for example: transversal of
longest paths and cycles, tree $3$-spanner problem, geodetic set problem)
which are either hard or open on chordal graphs become polynomial-time
solvable on well-partitioned chordal graphs [2], the computational complexity
of CVD on well-partitioned chordal graphs is a well-motivated open question.

In this paper, we also study a generalisation of CVD known as $s$-Club Cluster
Vertex Deletion ($s$-CVD). In many applications the equivalence of cluster and
clique is too restrictive [5, 30, 3]. For example, in protein networks where
proteins are the vertices and the edges indicate the interaction between the
proteins, a more appropriate notion of clusters may have a diameter of more
than $1$ [5]. Therefore researchers have defined the notion of _$s$ -clubs_
[27, 5]. An $s$-club is a graph with _diameter_ at most $s$. The objective of
$s$-Club Cluster Vertex Deletion ($s$-CVD) is to delete the minimum number of
vertices from the input graph so that all connected components of the
resultant graph is an $s$-club. Below we give a formal definition of $s$-CVD.

$s$-Club Cluster Vertex Deletion ($s$-CVD) Input: An undirected graph $G$, and
integers $k$ and $s$. Output: Yes, if there is a set $S$ of vertices with
$|S|\leq k$, such that each component of the graph induced by $V(G)\setminus
S$ has diameter at most $s$. No, otherwise.

Schäfer [33] introduced the notion of $s$-CVD and gave a polynomial-time
algorithm for $s$-CVD on trees. Researchers have studied the particular case
of $2$-CVD as well [26, 15]. In general, $s$-CVD remains NP-hard on planar
bipartite graphs for each $s\geq 2$, APX-hard on split graphs for $s=2$ [11]
(contrasting the polynomial-time solvability of CVD on split graphs).
Combination of the ideas of Cao et al. [10] and Schäfer [33], provides an
$O(n^{8})$-time algorithm for $s$-CVD on a trapezoid graphs (intersection
graphs of trapezoids between two horizontal lines) with $n$ vertices [11].
This algorithm can be modified to give an $O(n^{4})$-time algorithm for
$s$-CVD on interval graphs with $n$ vertices.

General notations: For a graph $G$, let $V(G)$ and $E(G)$ denote the set of
vertices and edges, respectively. For a vertex $v\in V(G)$, the set of
vertices adjacent to $v$ is denoted by $N(v)$ and $N[v]=N(v)\cup\\{v\\}$. For
$S\subseteq V(G)$, let $G-S$ be an induced graph obtained by deleting the
vertices in $S$ from $G$. For two sets $S_{1},S_{2}$, let $S_{1}-S_{2}$
denotes the set obtained by deleting the elements of $S_{2}$ from $S_{1}$. The
set $S_{1}\Delta S_{2}$ denotes $(S_{1}\cup S_{2})-(S_{1}\cap S_{2})$.

##  2 Our Contributions

In this section, we state our results formally. We start with the definition
of well-partitioned chordal graphs as given in [1].

######  Definition 1 ([1]).

A connected graph $G$ is a well-partitioned chordal graph if there exists a
partition $\mathcal{P}$ of $V(G)$ and a tree $\mathcal{T}$ having
$\mathcal{P}$ as a vertex set such that the following hold.

  1. (a)

Each part $X\in\mathcal{P}$ is a clique in $G$.

  2. (b)

For each edge $XY\in E(\mathcal{T})$, there exist $X^{\prime}\subseteq X$ and
$Y^{\prime}\subseteq Y$ such that edge set of the bipartite graph $G[X,Y]$ is
$X^{\prime}\times Y^{\prime}$.

  3. (c)

For each pair of distinct $X,Y\in V(\mathcal{T})$ with $XY\notin
E(\mathcal{T})$, there is no edge between a vertex in $X$ and a vertex in $Y$.

The tree $\mathcal{T}$ is called a _partition tree_ of $G$, and the elements
of $\mathcal{P}$ are called its _bags_ or _nodes_ of $\mathcal{T}$.

Our first result is on CVD for well-partitioned chordal graphs which
generalises a result of Cao et al. [10] for split graphs. We prove the
following theorem in Section 3.

######  Theorem 1.

Given a well-partitioned chordal graph $G$ and its partition tree, there is an
$O(m^{2}n)$-time algorithm to solve CVD on $G$, where $n$ and $m$ are the
number of vertices and edges.

Since a partition tree of a well-partitioned chordal graph can be obtained in
polynomial time [1], the above theorem adds CVD to the list of problems that
are open on chordal graphs but admits polynomial-time algorithm on well-
partitioned chordal graphs. Our algorithm relies on a characterisation of the
solution set and we show that the optimal solution of a well-partitioned
chordal graph with $m$ edges can be obtained by finding weighted minimum
vertex cover [24] of $m$ many weighted bipartite graphs with weights at most
$n$. Then standard _Max-flow_ based algorithms [24, 28, 23] from the
literature yields Theorem 1. On the negative side, we prove the following
theorem in Section 5.

######  Theorem 2.

Unless the Unique Games Conjecture is false, for any even integer $s\geq 2$,
there is no $(2-\epsilon)$-approximation algorithm for $s$-CVD on well-
partitioned graphs.

Our third result is a faster algorithm for $s$-CVD on _interval graphs_.

######  Definition 2.

A graph $G$ is an interval graph if there is a collection $\mathcal{I}$ of
intervals on the real line such that each vertex of the graph can be mapped to
an interval and two intervals intersect if and only if there is an edge
between the corresponding vertices in $G$. The set $\mathcal{I}$ is an
interval representation of $G$

We prove the following theorem in Section 4.

######  Theorem 3.

For each $s\geq 1$, there is an $O(n(n+m))$-time algorithm to solve $s$-CVD on
interval graphs with $n$ vertices and $m$ edges.

We note that our techniques deviate significantly from the ones in the
previous literature [33, 10, 11]. We show that the optimal solution (for
$s$-CVD on interval graphs) must be one of “four types” and the optimum for
each of the “four types” can be found by solving $s$-CVD on $O(m+n)$ many
induced subgraphs. Furthermore, we exploit the “linear” structure of interval
graphs to ensure that optimal solution in each case can be found in
$O(n)$-time. Our result significantly improves the state-of-the-art running
time $\left(O\left(n^{4}\right)\text{, See
\cite[cite]{[\@@bibref{}{chakraborty2021algorithms}{}{}]}}\right)$ for $s$-CVD
on interval graphs.

##  3 Polynomial time algorithm for CVD on well-partitioned chordal graphs

In this section, we shall give a polynomial-time algorithm to solve CVD on
well-partitioned chordal graphs. In the next section, we present the main
ideas of our algorithm and describe our techniques for proving Theorem 1.

###  3.1 Overview of the algorithm

Let $G$ be a well-partitioned chordal graph with a partition tree
$\mathcal{T}$ rooted at an arbitrary node. For a node $X$, let
$\mathcal{T}_{X}$ be the subtree rooted at $X$ and $G_{X}$ be the subgraph of
$G$ induced by the vertices in the nodes of $\mathcal{T}_{X}$. For two
adjacent nodes $X,Y$ of $\mathcal{T}$, _the boundary of $X$ with respect to
$Y$_ is the set $bd(X,Y)=\\{x\in X\colon N(x)\cap Y\neq\emptyset\\}$. For a
node $X$, $P(X)$ denotes the parent of $X$ in $\mathcal{T}$. We denote minimum
CVD sets of $G_{X}$ and $G_{X}-bd(X,P(X))$ as $OPT(G_{X})$ and
$OPT(G_{X}-bd(X,P(X))$, respectively. We shall use the above notations
extensively in the description of our algorithm and proofs.

Our dynamic programming-based algorithm traverses $\mathcal{T}$ in a post-
order fashion and for each node $X$ of $\mathcal{T}$, computes $OPT(G_{X})$
and $OPT(G_{X}-bd(X,P(X)))$. A set $S$ of vertices is a _CVD set_ of $G$ if
$G-S$ is disjoint union of cliques. At the heart of our algorithm lies a
characterisation of CVD sets of $G_{X}$, showing that any CVD set of $G_{X}$
can be exactly one of two types, namely, _$X$ -CVD set_ or _$(X,Y)$ -CVD set_
where $Y$ is a child of $X$ (See Definitions 4 and 5). Informally, for a node
$X$, a CVD set is an $X$-CVD set if it contains $X$ or removing it from
$G_{X}$ creates a cluster all of whose vertices are from $X$. On the contrary,
a CVD set is an $(X,Y)$-CVD set if its removal creates a cluster intersecting
both $X$ and $Y$, where $Y$ is a child of $X$. In Lemma 4, we formally show
that any CVD set of $G_{X}$ must be one of the above two types.

To compute a minimum $X$-CVD set, first we construct a weighted bipartite
graph $\mathcal{H}$ which is defined in Section 3.3 and show that a minimum
weighted vertex cover of $\mathcal{H}$ can be used to construct a minimum
$X$-CVD set of $G$. (See Equations 3, 4, 5, 6). Then in Section 3.4, we show
that the subroutine for finding minimum $X$-CVD sets can be used to to get a
minimum $(X,Y)$-CVD set for each child $Y$ of $X$. Finally, in Section 3.5 we
combine our tools and give an $O(m^{2}n)$-time algorithm to find a minimum CVD
set of an well-partitioned chordal graph $G$ with $n$ vertices and $m$ edges.

###  3.2 Definitions and lemma

In this section, we introduce some definitions and prove the lemma that
facilitates the construction of a polynomial-time algorithm for finding a
minimum CVD set of well-partitioned graphs.

######  Definition 3.

A _cluster_ $C$ of a graph $G$ is a connected component that is isomorphic to
a complete graph.

######  Definition 4.

Let $G$ be a well-partitioned graph, $\mathcal{T}$ be its partition tree, and
$X$ be the root node of $\mathcal{T}$. A CVD set $S$ of $G$ is an $X$-CVD set
if either $X\subseteq S$ or $G-S$ contains a cluster $C\subseteq X$.

######  Definition 5.

Let $G$ be a well-partitioned graph, $\mathcal{T}$ be its partition tree, $X$
be the root node of $\mathcal{T}$. Let $Y$ be a child of $X$. A CVD set $S$ is
a “$(X,Y)$-CVD set” if $G-S$ has a cluster $C$ such that $C\cap
X\neq\emptyset$ and $C\cap Y\neq\emptyset$.

######  Lemma 4.

Let $S$ be a CVD set of $G$. Then exactly one of the following holds.

  1. (a)

The set $S$ is a $X$-CVD set.

  2. (b)

There is exactly one child $Y$ of $X$ in $\mathcal{T}$ such that $S$ is an
$(X,Y)$-CVD set of $G$.

###### Proof.

If $X\subseteq S$ or if $G-S$ has a cluster which is contained in $X$, then
$S$ is an $X$-CVD set. Otherwise, $X^{*}=(G-S)\cap X\neq\emptyset$ and since
$X^{*}$ is a clique, $G-S$ must contain a cluster $C$ such that $X^{*}\subset
C\not\subseteq X$. Therefore, $C$ should intersect with at least one child of
$X$. Let $Y_{1},Y_{2}$ be children of $X$. If both $C\cap Y_{1}\neq\emptyset$
and $C\cap Y_{2}\neq\emptyset$, then $C$ is not a cluster because $Y_{1}$ and
$Y_{2}$ are non-adjacent nodes of $\mathcal{T}$. Hence $C$ intersects exactly
one child of $X$. ∎

###  3.3 Finding minimum $X$-CVD sets

In this section, we prove the following theorem.

######  Theorem 5.

Let $G$ be a well-partitioned graph rooted at $X$ and $\mathcal{T}$ be a
partition tree of $G$. Assume for each node $Y\in V(\mathcal{T})-\\{X\\}$ both
$OPT(G_{Y})$ and $OPT(G_{Y}-bd(Y,P(Y)))$ are given, where $P(Y)$ is the parent
of $Y$ in $\mathcal{T}$. Then a minimum $X$-CVD set of $G$ can be computed in
$O\left(|E(G)|.|V(G)|\right)$ time.

For the remainder of this section, we denote by $G$ a fixed well-partitioned
graph rooted at $X$ with a partition tree $\mathcal{T}$. Let
$X_{1},X_{2},\ldots,X_{t}$ be the children of $X$. The main idea behind our
algorithm for finding minimum $X$-CVD set of $G$ is to construct an auxiliary
vertex weighted bipartite graph $\mathcal{H}$ with at most $|V(G)|$ vertices
such that the (minimum) vertex covers of $\mathcal{H}$ can be used to
construct (minimum) $X$-CVD-CVD set. Below we describe the construction of
$\mathcal{H}$.

Let $\mathcal{B}=\left\\{bd(X_{i},X)\colon i\in[t]\right\\}$. The vertex set
of $\mathcal{H}$ is $X\cup\mathcal{B}$ and the edge set of $\mathcal{H}$ is
defined as

$\displaystyle E(\mathcal{H})$ $\displaystyle=$ $\displaystyle\\{uB\colon u\in
X,B\in\mathcal{B},\forall v\in B,uv\in E(G)\\}$ (1)

The weight function on the vertices of $\mathcal{H}$ is defined as follows.
For each vertex $u\in X$, define $w(u)=1$ and for each set $B\in\mathcal{B}$
where $B=bd(X_{j},X)$, define

$\displaystyle w(B)$ $\displaystyle=$
$\displaystyle|B|+\left|OPT(G_{X_{j}}-B)\right|-\left|OPT(G_{X_{j}})\right|$
(2)

Remark 1.  Since $B\cup OPT(G_{X_{j}}-B)$ is a CVD set of $G_{X_{j}}$, we have
$|OPT(G_{X_{j}})|\leq|B|+|OPT(G_{X_{j}}-B)|$ and therefore $w(B)\geq 0$. Below
we show how minimum weighted vertex covers of $\mathcal{H}$ can be used to
compute minimum $X$-CVD set of $G$. For an $X$-CVD set $Z$ of $G$, define
$Cov(Z)=(X\cap Z)\cup\left\\{B\in\mathcal{B}\colon B\subseteq Z\right\\}$.

######  Lemma 6.

Let $Z$ be an $X$-CVD set of $G$. Then $Cov(Z)$ is a vertex cover of
$\mathcal{H}$.

###### Proof.

Assume that $Cov(Z)$ is not a vertex cover of $\mathcal{H}$. Then there exists
at least one edge $e=uB$ in $\mathcal{H}-Cov(Z)$. Hence from the definition of
$Cov(Z)$ we infer that $u\in X-Z$ and $B\not\subseteq Z$. Let $C_{u}$ be the
cluster of $G-Z$ that contains the vertex $u$. Since $X$ is a clique,
$X-Z\subseteq C_{u}$. Observe that since $uB$ is an edge of $\mathcal{H}$,
there exists a vertex $w\in B$ such that $uw\in E(G)$. Then the definition of
partition tree $\mathcal{T}$ and $B$ implies that all vertices of $B$ are
contained in $N(u)$. Since $B\not\subseteq Z$ it follows that there exists at
least one vertex $v\in B$ in $G-Z$ such that $uv\in E(G-Z)$ and hence $v\in
C_{u}$. Therefore, the cluster $C_{u}$ intersects the child of $X$ that
contains $B$ which contradicts the assumption that $Z$ is an $X$-CVD set of
$G$ (see definition of $X$-CVD set). ∎

For a vertex cover $D$ of $\mathcal{H}$, define

$\displaystyle S_{1}(D)$ $\displaystyle=$ $\displaystyle D\cap X$ (3)
$\displaystyle S_{2}(D)$ $\displaystyle=$
$\displaystyle\displaystyle\bigcup\limits_{\begin{subarray}{c}B\in
D\cap\mathcal{B}\\\ B=bd(X_{i},X)\end{subarray}}B\cup
OPT(G_{X_{i}}-bd(X_{i},X))$ (4) $\displaystyle S_{3}(D)$ $\displaystyle=$
$\displaystyle\displaystyle\bigcup\limits_{\begin{subarray}{c}B\in\mathcal{B}-D\\\
B=bd(X_{i},X)\end{subarray}}OPT(G_{X_{i}})$ (5) $\displaystyle Sol(D)$
$\displaystyle=$ $\displaystyle S_{1}(D)\cup S_{2}(D)\cup S_{3}(D)$ (6)

Note that, by definition $S_{i}(D)\cap S_{j}(D)=\emptyset,1\leq i<j\leq 3$. We
have the following lemma.

######  Lemma 7.

Let $D$ be a vertex cover of $\mathcal{H}$. Then $Sol(D)$ is an $X$-CVD set of
$G$.

###### Proof.

Suppose for the sake of contradiction that $Sol(D)$ is not an $X$-CVD set of
$G$. First assume $Sol(D)$ is not a CVD set of $G$. Then there exists an
induced path $P=uvw$ in $G-Sol(D)$. Consider the following cases.

  1. 1.

$X\cap\\{u,v,w\\}=\emptyset$. Then there must exist a child $Y$ of $X$ such
that $u,v,w$ are vertices of $G_{Y}$. If $B=bd(Y,X)\in D$, then by Equations 4
and 6, $Sol(D)$ contains $B\cup OPT(G_{Y}-B)$. But then $B\cup OPT(G_{Y}-B)$
is not a CVD set of $G_{Y}$, a contradiction. If $B\not\in D$, then by
Equations 5 and 6, $Sol(D)$ contains $OPT(G_{Y})$. But then $OPT(G_{Y})$ is
not a CVD set of $G_{Y}$, also a contradiction.

  2. 2.

Otherwise, there always exists two adjacent vertices $z_{1},z_{2}$ such that
$\\{z_{1},z_{2}\\}\subset\\{u,v,w\\}$ and $z_{1}\in X$ and $z_{2}\in Y$, where
$Y$ is a child of $X$. Observe that $z_{2}\in B=bd(Y,X)$ and therefore $z_{1}$
is adjacent to $B$ in $\mathcal{H}$. Since $\\{z_{1},z_{2}\\}\cap
Sol(D)=\emptyset$, $\mathcal{H}-D$ contains the edge $z_{1}B$, contradicting
the fact that $D$ is a vertex cover of $\mathcal{H}$.

Now assume that $Sol(D)$ is a CVD set but not an $X$-CVD set. Then there must
exists a cluster $C$ in $G-Sol(D)$ that contains an $(X,Y)$-edge $uv$ where
$u\in X$ and $v\in bd(Y,X)$. Therefore $u\not\in D$ and $B=bd(Y,X)\not\in D$.
Then $\mathcal{H}-D$ contains the edge $uB$, contradicting the fact that $D$
is a vertex cover of $\mathcal{H}$. ∎

A minimum weighted vertex cover $D$ of $\mathcal{H}$ is also _minimal_ if no
proper subset of $D$ is a vertex cover of $\mathcal{H}$. The restriction of
minimality is to avoid the inclusion of redundant vertices with weight $0$ in
the minimum vertex cover.

######  Observation 2.

Let $D$ be a minimal minimum weighted vertex cover of $\mathcal{H}$. For any
$i\in[t]$, either $bd(X,X_{i})\subseteq D$ or $bd(X_{i},X)\in D$, but not
both.

###### Proof.

First assume $bd(X,X_{i})\not\subseteq D$ and $B=bd(X_{i},X)\not\in D$.
Observe that, the neighbourhood of $B$ in $\mathcal{H}$ is $bd(X,X_{i})$.
Since $bd(X,X_{i})\not\subseteq D$, there must exists a vertex
$u\in(bd(x,X_{i})-D)\subseteq X-D$. Then it follows that $uB$ is an edge of
$\mathcal{H}-D$. This contradicts the fact that $D$ is a vertex cover of
$\mathcal{H}$.
Now assume that both $bd(X,X_{i})\subseteq D$ and $B=bd(X_{i},X)\in D$. Since
$\\{x:xB\in E(\mathcal{H}\\}=bd(X,X_{i})$ the set $D-\\{B\\}$ is also a vertex
cover of $\mathcal{H}$, a contradiction. ∎

From now on $D$ denotes a minimal minimum weighted vertex cover of
$\mathcal{H}$ and $Z$ denotes a fixed but arbitrary $X$-CVD set of $G$. Our
goal is to show that $\left|Sol(D)\right|\leq\left|Z\right|$. We need some
more notations and observations.

First we define four sets $I_{1},I_{2},I_{3},I_{4}$ as follows. (Recall that
$X_{1},X_{2},\ldots,X_{t}$ are children of the root $X$ of the partition tree
$\mathcal{T}$ of $G$.)

$\displaystyle I_{1}$ $\displaystyle=$ $\displaystyle\\{i\in[t]\colon
bd(X,X_{i})\subseteq Sol(D)\text{ and }bd(X,X_{i})\subseteq Z\\}$ (7)
$\displaystyle I_{2}$ $\displaystyle=$ $\displaystyle\\{i\in[t]\colon
bd(X,X_{i})\subseteq Sol(D)\text{ and }bd(X,X_{i})\not\subseteq Z\\}$ (8)
$\displaystyle I_{3}$ $\displaystyle=$ $\displaystyle\\{i\in[t]-(I_{1}\cup
I_{2})\colon bd(X_{i},X)\subseteq Sol(D)\text{ and }bd(X_{i},X)\subseteq Z\\}$
(9) $\displaystyle I_{4}$ $\displaystyle=$ $\displaystyle\\{i\in[t]-(I_{1}\cup
I_{2})\colon bd(X_{i},X)\subseteq Sol(D)\text{ and }bd(X_{i},X)\not\subseteq
Z\\}$ (10)

Note that $I_{1}\cup I_{2}\cup I_{3}\cup I_{4}=[t]$ and $(I_{1}\cup
I_{2})\cap(I_{3}\cup I_{4})=\emptyset$. We have the following observations on
the sets $I_{i},1\leq i\leq 4$.

######  Observation 3.

The sets $I_{1},I_{2},I_{3},I_{4}$ form a partition of $[t]$.

###### Proof.

From the definition of $I_{i},1\leq i\leq 4$, it is clear that $I_{i}\cap
I_{j}=\emptyset,i\neq j$. Assume that there exists an $i\in[t]$ such that
$i\notin I_{1}\cup I_{2}$. Hence, $bd(X,X_{i})\not\subseteq Sol(D)\cap X=D\cap
X$. Then by Observation 2, $bd(X_{i},X)\in D$ and by equation 4 the set of
vertices $bd(X_{i},X)\subseteq Sol(D)$. Therefore each $i\in[t]-(I_{1}\cup
I_{2})$ either belongs to the set $I_{3}$ or $I_{4}$. ∎

######  Observation 4.

Let $D$ be a vertex cover of $\mathcal{H}$ and $Sol(D)$ be an $X$-CVD set of
$G$ defined as in equation 6. For the sets $I_{i},1\leq i\leq 4$ defined by
the Equations 7 \- 10, the following holds.

(i) $\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})=S_{1}(D)$

(ii) $\bigcup\limits_{i\in I_{3}\cup I_{4}}bd(X_{i},X)\cup
OPT(G_{X_{i}}-bd(X_{i},X)=S_{2}(D)$

(iii) $\bigcup\limits_{i\in I_{1}\cup I_{2}}OPT(G_{X_{i}})=S_{3}(D)$.

###### Proof.

First note that $S_{1}(D)=D\cap X=Sol(D)\cap X$ (by definition of $Sol(D)$).
On the other hand, by definition of $I_{1}$ and $I_{2}$ we have
$\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})\subseteq Sol(D)$. Moreover,
$\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})\subseteq X$. Therefore,
$\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})\subseteq Sol(D)\cap
X=S_{1}(D)$.
Now to prove the other side, $S_{1}(D)\subseteq\bigcup\limits_{i\in I_{1}\cup
I_{2}}bd(X,X_{i})$, suppose for the sake of contradiction that there exists a
vertex $v\in S_{1}(D)-\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})$. Let
$J=\\{j:v\in bd(X,X_{j})\\}$. Since $J\cap(I_{1}\cup I_{2})=\emptyset$, by
definition of $I_{1}$ and $I_{2}$, for each $j\in J,bd(X,X_{j})\not\subseteq
Sol(D)\cap X=D\cap X$. Hence by Observation 2, $bd(X_{j},X)\in D,\forall$.
Therefore, $D-\\{v\\}$ is also a vertex cover of $\mathcal{H}$, contradicting
the minimality of $D$.

By Observation 3, $I_{3}\cup I_{4}=[t]-I_{1}\cup I_{2}$. Moreover, by the
definition of $I_{1}$ and $I_{2}$, for each $i\in[t]-I_{1}\cup I_{2}$ the set
$bd(X,X_{i})\not\subseteq Sol(D)\cap X=D\cap X$. Hence by Observation 2, we
have $bd(X_{i},X)\in D$ for each $i\in I_{3}\cup I_{4}$ and $bd(X_{i},X)\notin
D,i\in I_{1}\cup I_{2}$. Thus it follows from Observation 3 and the definition
of $S_{2}$ and $S_{3}$ that $\bigcup\limits_{i\in I_{3}\cup
I_{4}}bd(X_{i},X)\cup OPT(G_{X_{i}}-bd(X_{i},X))=S_{2}(D)$ and
$\bigcup\limits_{i\in I_{1}\cup I_{2}}OPT(G_{X_{i}})=S_{3}(D)$.

∎

Based on the set $I_{1}$, we construct two sets $D_{1}$ and $Z_{1}$ from
$Sol(D)$ and $Z$, respectively, which are defined as follows.

$\displaystyle D_{1}$ $\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\cup(Sol(D)\cap G_{X_{i}})$ (11) $\displaystyle Z_{1}$
$\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\cup(Z\cap G_{X_{i}})$ (12)

######  Observation 5.

$\left|D_{1}\right|\leq\left|Z_{1}\right|$.

###### Proof.

From the definition of $Sol(D)$ and equation 3, for $i\in I_{1}$, we infer
that $bd(X,X_{i})\subseteq D$. Hence, by Observation 2, $bd(X_{i},X)\not\in
D,i\in I_{1}$ and from equation 5, $Sol(D)\cap G_{X_{i}}=OPT(G_{X_{i}})$.
Since for each $i,j\in I_{1}$, $G_{X_{i}}\cap G_{X_{j}}=\emptyset$ and $|Z\cap
G_{X_{i}}|\geq|OPT(G_{X_{i}})|$, by the definitions of $D_{1}$ and $Z_{1}$ we
have $|D_{1}|\leq|Z_{1}|$. ∎

Based on the set $I_{2}$, we construct the following two sets $D_{2}\subseteq
Sol(D)$ and $Z_{2}\subseteq Z$.

$\displaystyle D_{2}$ $\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{2}}bd(X,X_{i})\cup(Sol(D)\cap G_{X_{i}})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})$ (13) $\displaystyle Z_{2}$ $\displaystyle=$
$\displaystyle\bigcup\limits_{i\in
I_{2}}bd(X_{i},X)\cup(Z\cap(G_{X_{i}}-bd(X_{i},X)))$ (14)

By the definition of the set $I_{2}$, the set of vertices
$bd(X,X_{i})\not\subseteq Z,i\in I_{2}$. By Lemma 6, recall that there exits a
vertex cover, $Cov(Z)$ of $\mathcal{H}$ corresponding to every $X$-CVD-set
$Z$. Since $bd(X,X_{i})\not\subseteq Z$ and thus $bd(X,X_{i})\not\subseteq
Cov(Z)$, it is implicit in Observation 2 that $bd(X_{i},X)\in Cov(Z)$. Hence
$bd(X_{i},X)\subseteq Z$ and the set $Z_{2}\subseteq Z$.

######  Observation 6.

$|D_{2}|\leq|Z_{2}|$.

###### Proof.

By arguments similar to that in the proof of Observation 5, for $i\in
I_{2},(Sol(D)\cap G_{X_{i}})=OPT(G_{X_{i}})$. Hence,
$D_{2}=\bigcup\limits_{i\in I_{2}}bd(X,X_{i})\cup
OPT(G_{X_{i}})-\bigcup\limits_{i\in I_{1}}bd(X,X_{i})$. Suppose for
contradiction that $|D_{2}|>|Z_{2}|$. Then by the definitions of $D_{2}$ and
$Z_{2}$ we have

$\left|\bigcup\limits_{i\in I_{2}}bd(X,X_{i})\cup
OPT(G_{X_{i}})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\right|>\left|\bigcup\limits_{i\in
I_{2}}bd(X_{i},X)\cup(Z\cap(G_{X_{i}}-bd(X_{i},X)))\right|$

Since $X\cap G_{X_{i}}=\emptyset,1\leq i\leq t$ and
$\left|Z\cap(G_{X_{i}}-bd(X_{i},X))\right|\geq OPT(G_{X_{i}}-bd(X_{i},X))$, we
can rewrite the above inequality as follows.

$\left|\bigcup\limits_{i\in I_{2}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\right|>\left|\bigcup\limits_{i\in
I_{2}}bd(X_{i},X)\right|+\\\ \left|\bigcup\limits_{i\in
I_{2}}OPT(G_{X_{i}}-bd(X_{i},X))\right|-\left|\bigcup\limits_{i\in
I_{2}}OPT(G_{X_{i}})\right|$

That is,

$\left|\bigcup\limits_{i\in I_{2}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\right|>\sum\limits_{i\in
I_{2}}(\left|bd(X_{i},X)\right|+\left|OPT(G_{X_{i}}-bd(X_{i},X)\right|-\left|OPT(G_{X_{i}})\right|)$

By equation 2,
$\left|bd(X_{i},X)\right|+\left|OPT(G_{X_{i}}-bd(X_{i},X))\right|-\left|OPT(G_{X_{i}})\right|=w(bd(X_{i},X))$
and hence,

$\displaystyle\left|\bigcup\limits_{i\in
I_{2}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\right|>\sum\limits_{i\in I_{2}}w(bd(X_{i},X))$ (15)

Recall that $D$ is a minimal minimum weighted vertex cover of $\mathcal{H}$.
By Observation 4 we have $\bigcup\limits_{i\in I_{2}}bd(X,X_{i})\subseteq D$
and hence for each $i\in I_{2}$, the vertex $B=bd(X_{i},X)\notin D$ by
Observation 2. Now we show that if we delete the vertices in
$\bigcup\limits_{i\in I_{2}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})$ from $D$ and add the set of vertices
$\left\\{bd(X_{i},X)\colon i\in I_{2}\right\\}$ then we get a vertex cover of
smaller weight for $\mathcal{H}$ by inequality (15), a contradiction.

######  Claim 1.

Let $D_{1}$ be a set of vertices obtained from $D$ by deleting the vertices in
$\bigcup\limits_{i\in I_{2}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})$ and by adding the set of vertices
$\left\\{bd(X_{i},X)\colon i\in I_{2}\right\\}$. Then, $D_{1}$ is a vertex
cover of $\mathcal{H}$.

###### Proof of claim.

Assume that there exists an edge $uB\in E(\mathcal{H}-D_{1})$ where
$B=bd(X_{j},X),j\in[t]$. Since $bd(X_{j},X)\notin D_{1}$, by the definition of
$D_{1}$ (given above ) observe that $bd(X_{j},X)\notin D$ and $j\notin I_{2}$.
Note that the neighbourhood of $bd(X_{j},X)$ in $\mathcal{H}$ is $bd(X,X_{j})$
and hence $u\in bd(X,X_{j})$. Since $D$ is a vertex cover of $\mathcal{H}$, we
have $bd(X,X_{j})\subseteq D$. Now we show that $j\notin I_{1}$: By definition
of $D_{1}$ we have $\bigcup\limits_{i\in I_{1}}bd(X,X_{i})\cap D\subseteq
D_{1}$. Since $u\in bd(X,X_{j})$ and $bd(X,X_{j})\subseteq D$, if $j\in I_{1}$
then the vertex $u$ remains in $D_{1}$. Thus no such edge $uB$ exists in
$\mathcal{H}-D_{1}$. Therefore, we infer that $j\notin I_{1}$. Since $j\notin
I_{1}\cup I_{2}$, from Observation 4 we have $bd(X,X_{j})\not\subseteq D\cap
X$. Hence there exists a vertex $w\in bd(X,X_{j})$ such that
$w\in\mathcal{H}-D$. Moreover, by the definition of partition tree
$\mathcal{T}$ and $bd(X,X_{j})$ the edge $wB\in E(\mathcal{H}-D)$. This
contradicts the assumption that $D$ is a vertex cover of $\mathcal{H}$. ∎

This completes the proof of the observation. ∎

Based on the set $I_{3}$, we construct the following two sets $D_{3}\subseteq
Sol(D)$ and $Z_{3}\subseteq Z$.

$\displaystyle D_{3}$ $\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{3}}bd(X_{i},X)\cup OPT(G_{X_{i}}-bd(X_{i},X))$ (16) $\displaystyle Z_{3}$
$\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{3}}bd(X_{i},X)\cup(Z\cap(G_{X_{i}}-bd(X_{i},X)))$ (17)

######  Observation 7.

$\left|D_{3}\right|\leq\left|Z_{3}\right|$.

###### Proof.

Since $\left|Z\cap(G_{X_{i}}-bd(X_{i},X))\right|\geq
OPT(G_{X_{i}}-bd(X_{i},X))$, by the definitions of $D_{3}$ and $Z_{3}$ we have
$\left|D_{3}\right|\leq\left|Z_{3}\right|$. ∎

Based on the set $I_{4}$, we construct the following two sets $D_{4}\subseteq
Sol(D)$ and $Z_{4}\subseteq Z$.

$\displaystyle D_{4}$ $\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{4}}bd(X_{i},X)\cup OPT(G_{X_{i}}-bd(X_{i},X))$ (18) $\displaystyle Z_{4}$
$\displaystyle=$ $\displaystyle\bigcup\limits_{i\in
I_{4}}bd(X,X_{i})\cup(Z\cap(G_{X_{i}}))-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})$ (19)

By the definition of the set $I_{4}$, the set of vertices
$bd(X_{i},X)\not\subseteq Z,i\in I_{4}$. By Lemma 6, recall that there exits a
vertex cover, $Cov(Z)$ of $\mathcal{H}$ corresponding to every $X$-CVD-set
$Z$. Since $bd(X_{i},X)\not\subseteq Z,i\in I_{4}$, by definition of $Cov(Z)$
we have $bd(X_{i},X)\notin Cov(Z)$ and hence it is implicit in Observation 2
that $bd(X,X_{i})\subseteq Cov(Z)$. Hence $bd(X,X_{i})\subseteq Z$ and the set
$Z_{4}\subseteq Z$.

######  Observation 8.

$\left|D_{4}\right|\leq\left|Z_{4}\right|$.

###### Proof.

Suppose for contradiction that $\left|D_{4}\right|>\left|Z_{4}\right|$. Then
by the definitions of $D_{4}$ and $Z_{4}$ we have

$\left|\bigcup\limits_{i\in I_{4}}(bd(X_{i},X)\cup
OPT(G_{X_{i}}-bd(X_{i},X)))\right|>\left|\bigcup\limits_{i\in
I_{4}}(bd(X,X_{i})\cup(Z\cap(G_{X_{i}})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})\right|$

Since $G_{X_{i}}\cap G_{X_{j}}=\emptyset$ for $i,j\in I_{4}$ and
$Z\cap(G_{X_{i}})\geq OPT(G_{X_{i}})$, we have

$\left|\bigcup\limits_{i\in
I_{4}}(bd(X_{i},X)\right|+\left|\bigcup\limits_{i\in
I_{4}}OPT(G_{X_{i}}-bd(X_{i},X)))\right|-\left|\bigcup\limits_{i\in
I_{4}}OPT(G_{X_{i}})\right|\\\ >\left|\bigcup\limits_{i\in
I_{4}}(bd(X,X_{i})-\bigcup\limits_{i\in I_{1}}bd(X,X_{i})\right|$

Note that by equation 2,
$\left|bd(X_{i},X)\right|+\left|OPT(G_{X_{i}}-bd(X_{i},X))\right|-\left|OPT(G_{X_{i}})\right|=w(bd(X_{i},X))$
and hence,

$\sum\limits_{i\in I_{4}}w(bd(X_{i},X))>\left|\bigcup\limits_{i\in
I_{4}}(bd(X,X_{i})-\bigcup\limits_{i\in I_{1}}bd(X,X_{i})\right|$ (20)

Recall that $D$ is a minimal minimum weighted vertex cover of $\mathcal{H}$.
Observe that by definition of $I_{1}$ and $Sol(D)$, the set
$\bigcup\limits_{i\in I_{1}}bd(X,X_{i})\subseteq D$. Now we show that if we
delete the vertices in $\left\\{bd(X_{i},X)\colon i\in I_{4}\right\\}$ from
$D$ and adding the set of vertices $\bigcup\limits_{i\in
I_{4}}bd(X,X_{i})-\bigcup\limits_{i\in I_{1}}bd(X,X_{i})$, then we get a
vertex cover of smaller weight for $\mathcal{H}$ by inequality (20), a
contradiction: By definition of $I_{1}$ and $Sol(D)$, the set
$\bigcup\limits_{i\in I_{1}}bd(X,X_{i})\subseteq D$. Hence by the addition of
the vertices $\bigcup\limits_{i\in I_{4}}bd(X,X_{i})-\bigcup\limits_{i\in
I_{1}}bd(X,X_{i})$ to $D$ we have the neighbourhood of each deleted vertex
$bd(X_{i},X)$ in $D$. ∎

######  Lemma 8.

$Sol(D)=\bigsqcup\limits_{i=1}^{4}D_{i}$ and for each $i,j\subset[4]$,
$Z_{i}\cap Z_{j}=\emptyset$.

###### Proof.

By Observation 3 it follows from the definition that for $1\leq i\neq j\leq
4$, the sets $D_{i}\cap D_{j}=\emptyset$ and $Z_{i}\cap Z_{j}=\emptyset$.

Now we show that $Sol(D)=D_{1}\cup D_{2}\cup D_{3}\cup D_{4}$. First consider
the set $D_{1}\cup D_{2}=\bigcup\limits_{i\in I_{1}\cup
I_{2}}(bd(X,X_{i})\cup(Sol(D)\cap G_{X_{i}}))$. By Observation 4,
$\bigcup\limits_{i\in I_{1}\cup I_{2}}bd(X,X_{i})=S_{1}(D)$ and
$\bigcup\limits_{i\in I_{1}\cup I_{2}}(Sol(D)\cap G_{X_{i}})=S_{3}(D)$. Hence
$D_{1}\cup D_{2}=S_{1}(D)\cup S_{3}(D)$
Now consider the set $D_{3}\cup D_{4}=\bigcup\limits_{i\in I_{3}\cup
I_{4}}bd(X_{i},X)\cup OPT(G_{X_{i}}-bd(X_{i},X))$. Hence by Observation 4,
$D_{3}\cup D_{4}=S_{2}(D)$. Therefore, the definition of $Sol(D)$ (Equation 6)
implies $Sol(D)=\bigsqcup\limits_{i=1}^{4}D_{i}$. ∎

Proof of Theorem 5 Using Lemma 8, we have that
$\left|Sol(D)\right|\leq|Z_{1}\cup Z_{2}\cup Z_{3}\cup Z_{4}|\leq|Z|$. Hence,
$Sol(D)$ is a minimum $X$-CVD set of $G$. Furthermore, $\mathcal{H}$ has at
most $|V(G)|$ vertices and $|E(G)|$ edges. Therefore minimum weighted vertex
cover of $\mathcal{H}$ can be found in $O(|V(G)|\cdot|E(G)|)$-time and
$Sol(D)$ can be computed in total of $O(|V(G)|\cdot|E(G)|)$-time. Below we
give a short pseudocode of our algorithm to find a minimum $X$-CVD set of $G$.

Input : A well-partitioned chordal graph $G$, a partition tree $\mathcal{T}$
of $G$ rooted at the node $X$, for each node $Y\in\mathcal{T}-\\{X\\}$ both
$OPT(G_{Y})$ and $OPT(G_{Y}-bd(Y,P(Y)))$ are given as part of input

Output : A minimum $X$-CVD set

1

2Construct a weighted bipartite graph $\mathcal{H}$ as described in Equations
1 and Equations 2;

3Find a minimum weighted vertex cover $D$ of $\mathcal{H}$;

4Construct the sets $S_{1}(D),S_{2}(D),S_{3}(D)$ and $Sol(D)$ as described in
Equations 3, 4, 5 and 6, respectively;

5return $Sol(D)$

Algorithm 1 Pseudocode to find a minimum $X$-CVD set of a well-partitioned
chordal graph

###  3.4 Finding minimum $(X,Y)$-CVD set of well-partitioned chordal graphs

In this section, we prove the following theorem.

######  Theorem 9.

Let $G$ be a well-partitioned graph; $\mathcal{T}$ be a partition tree of $G$
rooted at $X$; $Y$ be a child of $X$. Moreover, for each $Z\in
V(\mathcal{T})-\\{X\\}$, assume both $OPT(G_{Z})$ and $OPT(G_{Z}-bd(Z,P(Z)))$
are given $(P(Z)$ denotes the parent of $Z$ in $\mathcal{T})$. Then a minimum
$(X,Y)$-CVD set of $G$ can be computed in $O\left(|E(G)|^{2}.|V(G)|\right)$
time.

For the remainder of this section, the meaning of $G$, $\mathcal{T}$, $X$ and
$Y$ will be as given in Theorem 9. For an $(X,Y)$-edge $e$, we say that a
minimum $(X,Y)$-CVD set $A$ “preserves" the edge $e$ if $G-A$ contains the
edge $e$. Let $e\in E(X,Y)$ be an $(X,Y)$-edges of $G$. Then to prove Theorem
9, we use Theorem 10. First we show how to construct a minimum $(X,Y)$-CVD set
$S_{e}$ that preserves the edge $e\in E(X,Y)$ and prove Theorem 10. Clearly, a
minimum $(X,Y)$-CVD set $S$ of $G$ is the one that satisfies
$|S|=\min\limits_{e\in E(X,Y)}|S_{e}|$. Therefore, Theorem 9 will follow
directly from Theorem 10. The remainder of this section is devoted to prove
Theorem 10.

######  Theorem 10.

Assuming the same conditions as in Theorem 9, for $e\in E(X,Y)$, a minimum
$(X,Y)$-CVD set of $G$ that preserves $e$ can be computed in
$O\left(|E(G)|.|V(G)|\right)$ time.

First, we need the following observation about the partition trees of well-
partitioned chordal graphs, which is easy to verify.

######  Observation 9.

Let $G$ be a well-partitioned graph with a partition tree $\mathcal{T}$. Let
$X,Y$ be two adjacent nodes of $\mathcal{T}$ such that $X\cup Y$ induces a
complete subgraph in $G$ and $\mathcal{T}^{\prime}$ be the tree obtained by
contracting the edge $XY$ in $\mathcal{T}$. Now associate the newly created
node with the subset of vertices $(X\cup Y)$ and retain all the other nodes of
$\mathcal{T}^{\prime}$ and their associated subsets as in $\mathcal{T}$. Then
$\mathcal{T}^{\prime}$ is also a partition tree of $G$.

Now we begin building the machinery to describe our algorithm for finding a
minimum $(X,Y)$-CVD of $G$ that preserves an $(X,Y)$-edge $ab$. Observe that
any $(X,Y)$-CVD set that preserves the edge $ab$ must contain the set
$\left(N(a)~{}\Delta~{}N(b)\right)$ as subset. (Otherwise, the connected
component of $G-S$ containing $ab$ would not be a cluster, a contradiction).

Let $H$ denote the graph $G-\left(N(a)~{}\Delta~{}N(b)\right)$. Now consider
the partition $\mathcal{Q}$ defined as
$\\{Z-\left(N(a)~{}\Delta~{}N(b)\right)\colon Z\in V(\mathcal{T})\\}$. Now
construct a graph $\mathcal{F}$ whose vertex set is $\mathcal{Q}$ and two
vertices $Z_{1},Z_{2}$ are adjacent in $\mathcal{F}$ if there is an edge
$uv\in E(H)$ such that $u\in Z_{1}$ and $v\in Z_{2}$. Observe that
$\mathcal{F}$ is a forest.

Now we have the following observation that relates the connected components of
$H$ with that of $\mathcal{F}$ .

######  Observation 10.

There is a bijection $f$ between the connected components of $H$ and the
connected components of $\mathcal{F}$, such that for a component $C$ of $H$,
$f(C)$ is the partition tree of $C$. Moreover, the vertices of the root node
of $f(C)$ is subset of a node in $\mathcal{T}$.

###### Proof.

Recall that $\mathcal{Q}$ is a partition of $V(H)$ and the graph $\mathcal{F}$
is a forest. Let $A$ be a connected component of $H$. We have the following
cases.

  1. 1.

There is a vertex $u\in A$ and a vertex in $v\in bd(X,Y)$ such that $uv\in
E(G)$. Then observe that $A$ contains both vertices $a$ and $b$. Observe that
there is a set $Z=bd(X,Y)$ in $\mathcal{Q}$. Hence, $Z$ is a vertex of
$\mathcal{F}$. Now define $f(A)$ to be the subgraph of $\mathcal{F}$ that
contains $Z$. Clearly, $f(A)$ is a partition tree of $A$ and the root node of
$f(A)$ is $bd(X,Y)$ which is a subset of $X$, the root node of $\mathcal{T}$.

  2. 2.

There is a vertex $u\in A$ and a vertex in $v\in bd(Y,X)$ such that $uv\in
E(G)$. In this case, $A$ contains both vertices $a$ and $b$. Hence, $f(A)$ can
be defined as in Case 1.

  3. 3.

Consider the case when any edge $e=uv$ with $u\in X$ and $v\in A$ satisfies
$u\in X-bd(X,Y)$. In this case, observe that $v$ must lie in some child $Z$ of
$X$. Moreover, there is a set $Z$ in $\mathcal{Q}$. Hence, $Z$ is a vertex of
$\mathcal{F}$. Now define $f(A)$ to be the subgraph of $\mathcal{F}$ that
contains $Z$. Clearly, $f(A)$ is a partition tree of $A$ and the root node of
$f(A)$ is $Z$ which is a node of $\mathcal{T}$.

  4. 4.

Consider the case when any edge $e=uv$ with $u\in Y$ and $v\in A$ satisfies
$u\in Y-bd(Y,X)$. In this case, observe that $v$ must lie in some child $Z$ of
$Y$. Moreover, there is a set $Z$ in $\mathcal{Q}$. Hence, $Z$ is a vertex of
$\mathcal{F}$. Now define $f(A)$ to be the subgraph of $\mathcal{F}$ that
contains $Z$. Clearly, $f(A)$ is a partition tree of $A$ and the root node of
$f(A)$ is $Z$ which is a node of $\mathcal{T}$.

This completes the proof. ∎

Consider the connected component $H^{*}$ of $H$ which contains $a$ and $b$ and
let $\mathcal{F}^{\prime}=f(H^{*})$ where $f$ is the function given by
Observation 10. Observe that the root $R^{\prime}$ of $\mathcal{F}^{\prime}$
is actually $bd(X,Y)$. Moreover, $R^{\prime}$ has a child $R^{\prime\prime}$
which is actually $bd(Y,X)$. Observe that, $R^{\prime}\cup R^{\prime\prime}$
induces a complete subgraph in $H^{*}$. Hence, due to Observation 9, the tree
$\mathcal{F}^{*}$ obtained by contracting the edge
$R^{\prime}R^{\prime\prime}$ is a partition tree of $H^{*}$. Moreover,
$R^{*}=R^{\prime}\cup R^{\prime\prime}=bd(X,Y)\cup bd(Y,X)$ is the root node
of $\mathcal{F}^{*}$. Recall that our objective is to find a minimum
$(X,Y)$-CVD set that preserves the edge $ab$. We have the following lemma.

######  Lemma 11.

Let $H^{*},H_{1},H_{2},\ldots,H_{k^{\prime}}$ be the connected components of
$H$. Let $S^{*}$ be a minimum $(R^{*})$-CVD set of $H^{*}$,
$S_{0}=\left(N(a)~{}\Delta~{}N(b)\right)$, and for each $j\in[k^{\prime}]$,
let $S_{j}$ denote a minimum CVD set of $H_{j}$. Then $(S_{0}\cup S_{1}\cup
S_{2}\cup\ldots\cup S_{k^{\prime}}\cup S^{*})$ is a minimum $(X,Y)$-CVD set of
$G$ that preserves the edge $ab$.

###### Proof.

Observe that, any vertex which is adjacent to $a$ or $b$ lie in $R^{*}$. Since
$S^{*}$ is a minimum $(R^{*})$-CVD set, $S^{*}\cap\\{a,b\\}=\emptyset$ and
therefore $H^{*}-S^{*}$ has a cluster that contains the edge $ab$. Hence
$S_{0}\cup S_{1}\cup S_{2}\cup\ldots\cup S_{k^{\prime\prime}}\cup S^{*}$ is an
$(X,Y)$-CVD set that preserves the edge $ab$.

Let $Z$ be any $(X,Y)$-CVD set of $G$ that preserves the edge $ab$. For any
vertex $u\in S_{0}$, observe that $a,b,u$ induce a path of length $3$. Hence,
$S_{0}\subseteq Z$. Let $C$ be a connected component of $G-S_{0}$. Observe
that $Z\cap C$ must be a CVD set of $C$. Therefore, for each
$i\in[k^{\prime}]$, $|Z\cap H_{i}|\leq|S_{i}|$.

Since $Z$ is an $(X,Y)$-CVD set of $G$ that preserves the edge $ab$,
$\\{a,b\\}\cap Z=\emptyset$. Since $a,b$ are vertices of $H^{*}$, $(Z\cap
H^{*})\cap\\{a,b\\}=\emptyset$. Now suppose $(Z\cap H^{*})$ is not a
$(R^{*})$-CVD set of $H^{*}$. Then due to Lemma 4, $(Z\cap H^{*})$ must be a
$(R^{*},R)$-CVD set of $G^{*}$ for some child $R$ of $R^{*}$ in
$\mathcal{T}^{*}$. Hence, there exists a $(R^{*},R)$-edge $cd$ which is
preserved by $(Z\cap H^{*})$. Without loss of generality assume $c\in R^{*}$
and $d\in R$. Observe that $d$ is not adjacent to $a$ or $b$. Hence, $a,c,d$
induce a path of length $3$ in $H^{*}-(Z\cap H^{*})$, a contradiction. Hence
$|Z\cap H^{*}|\leq|S^{*}|$. Therefore $|Z|\leq|S_{0}\cup S_{1}\cup
S_{2}\cup\ldots\cup S_{k^{\prime\prime}}\cup S^{*}|$. ∎

Lemma 11 provides a way to compute a minimum $(X,Y)$-CVD set of $G$ that
preserves the edge $ab$. Clearly, the set
$S_{0}=\left(N(a)~{}\Delta~{}N(b)\right)$ can be computed in polynomial time.
The following observation provides a way to compute a minimum CVD set of all
connected components that are different from $H^{*}$.

######  Observation 11.

Let $A$ be a connected component of $H$ which is different from $H^{*}$. Then
a minimum $CVD$ set of $A$ can be computed in polynomial time.

###### Proof.

Recall that $A$ was obtained by deleting $\left(N(a)~{}\Delta~{}N(b)\right)$
from $G$, $\mathcal{T}$ is the partition tree of $G$ and root of $\mathcal{T}$
is $X$. Due to Observation 10, there is a function $f$ between the connected
components of $H$ and the connected components of $\mathcal{F}$ such that
$f(A)$ is the partition tree of $A$ and there is a node $R\in\mathcal{T}$ such
that the vertices in root node of $f(A)$ is a subset of $R$. Now consider the
following cases.

  1. 1.

Consider the case when $\\{a,b\\}\cap bd(P(R),R)=\emptyset$. This implies no
vertex of $R$ is adjacent to $a$ or $b$. Moreover, since $A$ is different from
$H^{*}$, $bd(P(R),R)\cap(bd(X,Y)\cup bd(Y,X))=\emptyset$. This further implies
that, either $bd(P(R),R)\subseteq N[a]-N[b]$ or $bd(P(R),R)\subseteq
N[b]-N[a]$. In either case, $R\cap(N[a]\cup N[b])=\emptyset$. This implies $R$
is a node of $\mathcal{T}$ distinct from $X$ such that $A$ is isomorphic to
$G_{R}$. Hence, due to the assumption given in Theorem 10, $OPT(G_{R})$ is
known and therefore a minimum CVD set of $A$ is known.

  2. 2.

Consider the case when there is a vertex $z\in\\{a,b\\}$ such that $z\in
bd(P(R),R)$. Let $z^{\prime}$ be the vertex among $a$ and $b$ distinct from
$z$. Since $A$ is different from $H^{*}$, $z^{\prime}\not\in bd(P(R),R)$.
Hence, $bd(R,P(R))\subset N(z)$ and therefore
$bd(R,P(R))\subset\left(N(a)~{}\Delta~{}N(b)\right)$. This implies that $R$ is
a node of $\mathcal{T}$ distinct from $X$ such that $A$ is isomorphic to
$G_{R}-bd(R,P(R))$. Hence, due to the assumption given in Theorem 10,
$OPT(G_{R}-bd(R,P(R)))$ is known and therefore a minimum CVD set of $A$ is
known.

Clearly, distinguishing between the above cases takes $O(|E(G)|)$ time. This
completes the proof. ∎

Let $H_{1},H_{2},\ldots,H_{k^{\prime}}$ be the connected components of $H$,
all different from $H^{*}$. Applying Observation 11 repeatedly on each
component, it is possible to obtain, for each $j\in[k^{\prime}]$, a minimum
CVD set $S_{j}$ of $H_{j}$. The following observation provides a way to
compute a minimum $(R^{*})$-CVD set of $H^{*}$.

######  Observation 12.

Let $R$ be a child of $R^{*}$ in $\mathcal{F}^{*}$. Then both $OPT(H^{*}_{R})$
and $OPT(H^{*}_{R}-bd(R,R^{*}))$ are known.

###### Proof.

Since no vertex of $R$ is adjacent to $a$ or $b$ in $G$, there must exist a
node $Q\in\mathcal{T}$ such that the vertices in the node $Q$ is same as that
in $R$, $\mathcal{T}_{Q}=\mathcal{T}^{*}_{R}$ and $G_{Q}=H^{*}_{R}$. Moreover,
$bd(R,R^{*})=bd(Q,P(Q))$, where $P(Q)$ is the parent of $Q$ in $\mathcal{T}$.
Hence, due to the assumption given in Theorem 10, $OPT(H^{*}_{R}-bd(R,R^{*})$
is known. ∎

Due to Observation 12 and Theorem 5, it is possible to compute a minimum
$(R^{*})$-CVD set $S^{*}$ of $H^{*}$ in $O(|V(G)|\cdot|E(G)|)$ time. Now due
to Lemma 11, we have that $(S_{0}\cup S_{1}\cup S_{2}\cup\ldots\cup
S_{k^{\prime}}\cup S^{*})$ is a minimum $(X,Y)$-CVD set of $G$ that preserves
the edge $ab$. This completes the proof of Theorem 10 and therefore of Theorem
9. In Algorithm 2, we give a short pseudocode of our algorithm to find a
minimum $(X,Y)$-CVD set of $G$ that preserves an $(X,Y)$-edge $ab$. Using
Algorithm 2, in Algorithm 3 we provide a short pseudocode to find a minimum
$(X,Y)$-CVD set of $G$.

Input : A well-partitioned chordal graph $G$, a partition tree $\mathcal{T}$
of $G$ rooted at the node $X$, a child node $Y$, an $(X,Y)$-edge $ab$, for
each node $Z\in\mathcal{T}-\\{X\\}$ both $OPT(G_{Z})$ and
$OPT(G_{Z}-bd(Z,P(Z)))$ are given as part of input

Output : A minimum $(X,Y)$-CVD set of $G$ that preserves the edge $ab$

1

2Construct the set $S_{0}=\left(N(a)~{}\Delta~{}N(b)\right)$;

3Construct the graph $H=G-\left(N(a)~{}\Delta~{}N(b)\right)$;

4Let $H^{*}$ be the connected component of $H$ containing $a$ and $b$. Let
$H_{1},H_{2},\ldots,H_{k^{\prime}}$ be the remaining connected components of
$H$.

5for  _$i=1\text{ to }k^{\prime}$ _ do

6 Compute a minimum CVD set $S_{i}$ of $H_{i}$ (Observation 11);

7

8Find the partition tree of $\mathcal{T}^{*}$ of $G^{*}$ whose root is
$X^{*}=bd(X,Y)\cup bd(Y,X)$;

9Compute a minimum $(X^{*})$-CVD set $S^{*}$ of $G^{*}$ using Algorithm 1;

10$Sol=S_{0}\cup S_{1}\cup S_{2}\cup\ldots\cup S_{k^{\prime}}\cup S^{*}$;

11return Sol;

12

Algorithm 2 Pseudocode to find a minimum $(X,Y)$-CVD set of a well-partitioned
chordal graph that preserves an $(X,Y)$-edge

Input : A well-partitioned chordal graph $G$, a partition tree $\mathcal{T}$
of $G$ rooted at the node $X$, a child node $Y$, for each node
$Z\in\mathcal{T}-\\{X\\}$ both $OPT(G_{Z})$ and $OPT(G_{Z}-bd(Z,P(Z)))$ are
given as part of input

Output : A minimum $(X,Y)$-CVD set of $G$.

1

2For each $(X,Y)$-edge $e$, compute a minimum $(X,Y)$-CVD set that preserves
the edge $e$ using Algorithm 2;

3Let $S$ be a set among all $S_{e}$’s that has the least cardinality;

4return $S$;

5

Algorithm 3 Pseudocode to find $(X,Y)$-CVD set of a well-partitioned chordal
graph.

###  3.5 Main Algorithm

From now on $G$ denote a fixed well-partitioned chordal graph with a partition
tree $\mathcal{T}$ whose vertex set is $\mathcal{P}$, a partition of $V(G)$.
We will process $\mathcal{T}$ in the post-order fashion and for each node $X$
of $\mathcal{T}$, we give a dynamic programming algorithm to compute both
$OPT(G_{X})$ and $OPT(G_{X}-bd(X,P(X)))$ where $P(X)$ is the parent of $X$
(when exists) in $\mathcal{T}$. Due to Observation 9, we can assume that
$bd(X,P(X))\subsetneq X$. In the remaining section, $X$ is a fixed node of
$\mathcal{T}$, $A$ has a fixed value (which is either $\emptyset$ or
$bd(X,P(X))$), $G^{A}_{X}$ denotes the graph $G_{X}-A$. Since well-partitioned
chordal graphs are closed under vertex deletion, $G^{A}_{X}$ is a well
partitioned chordal graph which may be disconnected. Now consider the
partition $\mathcal{P}^{A}$ defined as $\\{Y-A\colon Y\in
V(\mathcal{T}_{X})\\}$. Observe that, apart from the set $X$ all other sets of
the partitions $\mathcal{P}$ have remained in $\mathcal{P}^{A}$. Now construct
a graph $\mathcal{T}^{\prime}$ whose vertex set is the partition sets of
$\mathcal{P}^{A}$ and two vertices $X,Y$ are adjacent in
$\mathcal{T}^{\prime}$ if there is an edge $uv\in E(G^{A}_{X})$ such that
$u\in X$ and $v\in Y$ (since the graph induced by the union of the sets in
$\mathcal{P}^{A}$ is $G^{A}_{X}$, the definition of $\mathcal{T}^{\prime}$ is
valid). Now we have the following observation whose proof is similar to that
of Observation 10.

######  Observation 13.

There is a bijection $f$ between the connected components of $G^{A}_{X}$ and
the connected components of $\mathcal{T}^{\prime}$, such that for a component
$C$ of $G^{A}_{X}$, $f(C)$ is a partition tree of $C$, and the root of $f(C)$
is a child of $X$.

Since the vertices of $X-A$ induces a clique in $G^{A}_{X}$, there exists at
most one component $G^{*}$ in $G^{A}_{X}$ that contains a vertex from $X-A$.
Due to Observation 10 there exists a unique connected component
$f(G^{*})=\mathcal{T}^{*}$ of $\mathcal{T}^{\prime}$ which is a partition tree
of $G^{*}$. Let the remaining connected components of $G^{A}_{X}$ be
$G_{1},G_{2},\ldots,G_{k}$ and for each $i\in[k]$, let
$f(G_{i})=\mathcal{T}_{i}$ and $X_{i}$ is the root of $\mathcal{T}_{i}$. Let
$X^{*}$ denote the root node of $\mathcal{T}^{*}$ and
$X_{1}^{*},X_{2}^{*},\ldots,X_{t}^{*}$ be the children of $X^{*}$ in
$\mathcal{T}^{*}$. We have the following observation.

######  Observation 14.

For each $j\in[t]$, there is a child $Y_{j}$ of $X$ in $\mathcal{T}$ such that
$Y_{j}=X^{*}_{j}$ and $G_{Y_{j}}=G^{*}_{X^{*}_{j}}$.

###### Proof.

Observe that the root of $\mathcal{T}^{*}$ is $X^{*}=X-A$. Since $A\subsetneq
X$, any child of $X^{*}$ must be a child of $X$. ∎

We have the following lemma.

######  Lemma 12.

$OPT(G^{A}_{X})=\left(\displaystyle\bigsqcup\limits_{i=1}^{k}OPT(G_{X_{i}})\right)\sqcup
OPT(G^{*})$

###### Proof.

The lemma follows directly from the fact that
$G_{X_{1}},G_{X_{2}},\ldots,G_{X_{k}}$ and $G^{*}$ are connected components of
$G^{A}_{X}$. ∎

Due to Observation 13, $OPT(G_{X_{i}})$ is already known. Due to Lemma 11, any
CVD set $S$ of $G^{*}$ is either a $(X^{*})$-CVD set or there exists a unique
child $Y$ of $X^{*}$, such that $S$ is a $(X^{*},Y)$-CVD set of $G^{*}$. by
Theorem 5, it is possible to compute a minimum $(R^{*})$-CVD set $S_{0}$ of
$G^{*}$. Due to Observation 14, for any node $Y$ of $\mathcal{T}^{*}$ which is
different from $X^{*}$, both $OPT(G_{Y})$ and $OPT(G_{Y}-bd(Y,P(Y)))$ are
known, where $P(Y)$ is the parent of $Y$ in $\mathcal{T}^{*}$. Hence, by
Theorem 9 for each child $X^{*}_{i}$, $i\in[t]$, computing a minimum
$(X^{*},X^{*}_{i})$-CVD set $S_{i}$ is possible in
$O(|V(G^{*}_{X^{*}_{i}})|\cdot|E(G^{*}_{X^{*}_{i}})|)$ time. Let
$S^{*}\in\\{S_{0},S_{1},S_{2},\ldots,S_{t}\\}$ be a set with the minimum
cardinality. Due to Lemma 4, $S^{*}$ is a minimum CVD set of $G^{*}$ that can
be obtained in $O(m^{2}n)$. Finally, due to Lemma 12, we have a minimum CVD
set of $G^{A}_{X}$.

##  4 $O(n(n+m))$-time algorithm for $s$-CVD on interval graphs

In this section we shall give an $O(n(n+m))$-time algorithm to solve $s$-CVD
on interval graph $G$ with $n$ vertices and $m$ edges. For a set $X\subseteq
V(G)$, if each connected component of $G-X$ is an $s$-club, then we call $X$
as an _$s$ -club vertex deleting set_ ($s$-CVD set). In the next section we
present the main ideas of our algorithm to find a minimum cardinality $s$-CVD
set of an interval graph.

###  4.1 Overview of the algorithm

In the heart of our algorithm lies a characterisation of $s$-CVD sets of an
interval graph. We show (in Lemma 13) that any $s$-CVD set must be one of four
types, defined in Definitions 9\- 12. Hence, the problem boils down to
computing a minimum $s$-CVD set of each type. To do this, first we arrange the
maximal cliques in the order of its _Helly region_. Let
$Q_{1},Q_{2},\ldots,Q_{k}$ be the ordering of the cliques. Then for each
$1\leq a\leq k$, we find minimum cardinality $s$-CVD set of the graph
$G\left[1,a\right]$ which is the subgraph induced by the vertices in
$(Q_{1}\cup Q_{2}\cup\ldots\cup Q_{a})$. Moreover, to facilitate future
computations we also find minimum $s$-CVD set of the graph
$G\left[1,a\right]-A$ where $A=Q_{a}\cap Q_{b}$ for some $a<b\leq k$. The
trick was to show that, by solving $s$-CVD on $O(n+m)$ many different “induced
subgraphs" of $G$, it is possible to solve $s$-CVD on $G$. In other words, by
solving $O(n+m)$ many different subproblems, it is possible to solve $s$-CVD
on $G$. Moreover, it is possible to solve a subproblem in $O(n)$ time. In
Section 4.2 we define four types of $s$-CVD sets and state that any optimal
solution must be one of those four types. In Section 4.4 we give a sketch of
our algorithm and analyse the time complexity in Section 4.5.

###  4.2 Definitions and main lemma

Let $G$ denotes a connected interval graph with $n$ vertices and $m$ edges.
The set $\mathcal{I}$ denotes a fixed interval representation of $G$ where the
endpoints of the representing intervals are distinct. Let $l(v)$ and $r(v)$
denote the left and right endpoints, respectively, of an interval
corresponding to a vertex $v\in V(G)$. Then the interval assigned to the
vertex $v$ in $\mathcal{I}$ is denoted by $I(v)=\left[l(v),r(v)\right]$.

Observe that, intervals on a real line satisfies the Helly property and hence
for each maximal clique $Q$ of $G$ there is an interval
$I=\displaystyle\bigcap_{v\in Q}I(v)$. We call $I$ as the _Helly_ region
corresponding to the maximal clique $Q$. Let $Q_{1},Q_{2},\ldots,Q_{k}$ denote
the set of maximal cliques of $G$ ordered with respect to their _Helly_
regions $I_{a},1\leq a\leq k$ on the real line. That is,
$I_{1}<I_{2}<\ldots<I_{k}$. Observe that, for any two integers $a,b$ we have
$I_{a}\cap I_{b}=\emptyset$ as both $Q_{a}$ and $Q_{b}$ are maximal cliques.
Moreover, for any $a\leq b\leq c$ if a vertex $v\in Q_{a}\cap Q_{c}$, then
$v\in Q_{b}$.

With respect to an ordering of maximal cliques $Q_{1},Q_{2},\ldots,Q_{k}$ of
$G$, we define the following.

######  Definition 6.

  1. (i)

For integers a,b where $1\leq a<b\leq k$, let $S_{a}^{b}=Q_{a}\cap Q_{b}$.

  2. (ii)

For an integer $a$, let

$\mathcal{S}\left(Q_{a}\right)=\left\\{S_{a}^{b}\colon a<b\leq k\text{ and
}S_{a}^{b}\neq S_{a}^{b^{\prime}},a<b^{\prime}<b\right\\}\cup\emptyset$

. (Note that, the members of the set $\mathcal{S}\left(Q_{a}\right)$ are
distinct.)

  3. (iii)

For $A\in\mathcal{S}\left(Q_{a}\right)$, let $Y_{A}^{a}=(Q_{a}-Q_{a-1})-A$.

  4. (iv)

For a vertex $v\in V(G)$, the index $q^{-}_{v}=\min\\{a\colon v\in Q_{a}\\}$.
That is, the minimum integer $a$ such that $v$ belongs to the maximal clique
$Q_{a}$.

  5. (v)

For a vertex $v\in V(G)$, the index $q^{+}_{v}=\max\\{a\colon v\in Q_{a}\\}$.
That is, the maximum integer $b$ such that $v$ belongs to the maximal clique
$Q_{b}$.

We use the following observation to prove our main lemma.

######  Observation 15.

Let $X\subseteq V(G)$ and $u,v$ be two vertices with $r(u)<l(v)$ such that $u$
and $v$ lie in different connected components in $G-X$. Then there exists an
integer $a$ with $q^{+}_{u}\leq a<q^{-}_{v}$, such that $S_{a}^{a+1}\subseteq
X$.

###### Proof.

Let $\mathcal{C}$ be the set of all connected components of $G-X$. For a
connected component $C\in\mathcal{C}$, define $\hat{r}(C)=\max\\{r(v)\colon
v\in C\\}$ and $\hat{l}(C)=\min\\{l(v)\colon v\in C\\}$. Note that the
interval $[\hat{l}(C),\hat{r}(C)]=\bigcup\limits_{v\in V(C)}I(v)$ and we call
it as the _span_($C$). Observe that for two distinct connected components
$C,C^{\prime}\in\mathcal{C}$ we have
$\emph{span}(C)\cap\emph{span}(C^{\prime})=\emptyset$. Therefore,
$\mathcal{C}$ can be ordered with respect to the order in which the span of
components appears on the real line. Let $C_{1},\ldots,C_{x}$ be this
ordering. We define _gap_
$(C_{i},C_{i+1})=(\hat{r}(C_{i}),\hat{l}(C_{i+1})),1\leq i\leq x-1$. Note that
any vertex whose corresponding interval contains a point in _gap_
$(C_{i},C_{i+1})$ should be a member of $X$: otherwise that vertex belongs to
another component in between $C_{i}$ and $C_{i+1}$ (by definition of _gap_
$(C_{i},C_{i+1})$) which contradicts the ordering of components. Let
$C^{u}=C_{t}$ and $C^{v}=C_{t^{\prime}}$ denote the connected components of
$G-X$ that contain $u$ and $v$, respectively. Since $r(u)<l(v)$, we have
$t<t^{\prime}$.

Let $p\in V(G)$ be such that $r(p)=\max\\{r(w)\colon w\in
V(G),r(w)<\hat{l}(C^{v})\\}$. Now take $a=q^{+}_{p}$, the maximum index $i$
such that $p\in Q_{i},1\leq i\leq k$. For the index $a$, we will show that
$q^{+}_{u}\leq a<q^{-}_{v}$ and $S_{a}^{a+1}\subseteq X$.

(i) $q^{+}_{u}\leq a<q^{-}_{v}$: It is immediate from the definition of $r(p)$
that $r(u)\leq\hat{r}(C^{u})\leq r(p)$ and $r(p)<\hat{l}(C^{v})\leq l(v)$.
Since $r(p)<l(v)$, observe that the _Helly_ region corresponding to the clique
containing the vertex $p$ come before that of $v$ on the real line. Moreover,
since the maximal cliques are numbered with respect to the order in which
their _Helly_ regions appear on the real line, we can infer that
$q^{+}_{p}=a<q^{-}_{v}$. Similarly, since $r(u)\leq r(p)$, by similar
arguments as above, we have $q^{+}_{u}\leq a$. Therefore we have proved
$q^{+}_{u}\leq a<q^{-}_{v}$

(ii)$S_{a}^{a+1}\subseteq X$: Consider the component $C_{t^{\prime}-1}$ which
comes in the immediate left of $C^{v}$ in the ordering of the components in
$\mathcal{C}$. Since $r(p)<\hat{l}(C^{v})$, the _Helly_ region of $Q_{a}$ ends
before $span(C^{v})$. Observe that $r(p)\geq\hat{r}(C_{t^{\prime}-1})$.
Moreover, the _Helly_ region of $Q_{a+1}$ starts after that of $Q_{a}$. Since
$p\notin Q_{a+1}$ by definition of $a$ it follows that _Helly_ region of
$Q_{a+1}$ is after the $span(C_{t^{\prime}-1})$. Therefore, the intervals
corresponding to those vertices common to both $Q_{a}$ and $Q_{a+1}$ contain
some points of _gap_ $(C_{t^{\prime}-1},C^{v})$. This implies
$S_{a}^{a+1}\subseteq X$. ∎

For two integers $a,b$ with $1\leq a\leq b\leq k$, let $G\left[a,b\right]$
denotes the subgraph induced by the set $\\{Q_{a}\cup Q_{a+1}\cup\ldots\cup
Q_{b}\\}$.

######  Definition 7.

For an induced subgraph $H$ of $G$, a vertex $v\in V(H)$ and an integer $a$,
let $L_{H}\left(a,v\right)$ denote the set of vertices in $H$ that lie at
distance $a$ from $v$ in $H$.

In the remainder of this section, we use the notation
$L_{H}\left(s+1,v\right)$ where $H=G\left[1,a\right]-A$ for some integer $a$
and $v\in Y^{a}_{A}$ (See Definition 6, (iii)) several times.

######  Definition 8.

For an integer $a,1\leq a\leq k-1$ and a set
$A\in\mathcal{S}\left(Q_{a}\right)$ consider the induced subgraph
$H=G\left[1,a\right]-A$ and the sub-interval representation
$\mathcal{I}^{\prime}\subseteq\mathcal{I}$ of $H$. We define the “frontal
component" of the induced graph as the connected component of
$G\left[1,a\right]-A$ containing the vertex with the rightmost endpoint in
$\mathcal{I}^{\prime}$.

Note that for an integer $a$ and $A\in\mathcal{S}\left(Q_{a}\right)$, the
vertices of $Y_{A}^{a}$, if any, lies in the _frontal_ component of
$G\left[1,a\right]-A$. Below we categorize an $s$-CVD set $X$ of
$G\left[1,a\right]-A$ into four types. In the following definitions, we
consider an integer $a,1<a\leq k$ and a set
$A\in\mathcal{S}\left(Q_{a}\right)$.

######  Definition 9.

An $s$-CVD set $X$ of $G\left[1,a\right]-A$ is of “type-$1$” if
$Y_{A}^{a}\subseteq X$.

######  Definition 10.

An $s$-CVD set $X$ of $H=G\left[1,a\right]-A$ is of “type-$2$” if there is a
vertex $v\in Y_{A}^{a}$ such that $L_{H}\left(s+1,v\right)\subseteq X$.

######  Definition 11.

An $s$-CVD set $X$ of $H=G\left[1,a\right]-A$ is of “type-$3$” if there exists
an integer $c,1\leq c<a$ such that $S_{c}^{c+1}-A\subseteq X$ and
$G\left[c+1,a\right]-(S_{c}^{c+1}\cup A)$ is connected and has diameter at
most $s$.

######  Definition 12.

An $s$-CVD set $X$ of $H=G\left[1,a\right]-A$ is of “type-$4$” if there exists
an integer $c,1\leq c<a$ such that $S_{c}^{c+1}-A\subseteq X$ and
$G\left[c+1,a\right]-(S_{c}^{c+1}\cup A)$ is connected and has diameter
exactly $s+1$.

The following lemma is crucial for our algorithm.

######  Lemma 13 (Main Lemma).

Consider an integer $1\leq a\leq k$ and a set
$A\in\mathcal{S}\left(Q_{a}\right)$. Then at least one of the following holds:

  1. 1.

Every connected component of $G\left[1,a\right]-A$ have diameter at most $s$.

  2. 2.

Any $s$-CVD set of $G\left[1,a\right]-A$ is of some type-$j$ where
$j\in\\{1,2,3,4\\}$.

###### Proof.

Assume that the _frontal_ component of $H=G\left[1,a\right]-A$ has diameter at
least $s+1$ and the set $Y_{A}^{a}\neq\emptyset$. Otherwise, any $s$-CVD set
$X$ of $H$ is of either type-$1$ or type-$2$: Type-$1$ is obvious when
$Y_{A}^{a}=\emptyset$ because $\emptyset\subseteq X$. If the diameter of
_frontal_ component is at most $s$ then the set
$L_{H}\left(s+1,v\right)=\emptyset$ and hence any $s$-CVD set of $H$ is of
type-$2$.
Let $H$ has an $s$-CVD set $X$ that is not of type-$j$ for any $j\in\\{1,2\\}$
and $v$ be a vertex in $Y_{A}^{a}$. Since $X$ is not of type-2, $H-X$ contains
a vertex $u$ such that $u\in L_{H}\left(s+1,v\right)$. Now choose a vertex
$u\in L_{H}\left(s+1,v\right)$ such that
$q^{+}_{u}=\max\\{q^{+}_{u^{\prime}}\colon u^{\prime}\in
L_{H}\left(s+1,v\right)-X\\}$.

Let $X^{\prime}=X\cup A$. Then observe that $G-X^{\prime}=H-X$ and hence,
$u\in G-X^{\prime}$. Since $X$ is an $s$-CVD set of $H$ and the distance
between $u$ and $v$ in $H$ is $s+1$, the vertices $u$ and $v$ must lie in
different connected components in $G-X^{\prime}$. Therefore, by Observation
15, there is an integer $b$ such that $S_{b}^{b+1}\subseteq X^{\prime}$ and
$q^{+}_{u}\leq b<q^{-}_{v}$. Let $b$ be the maximum among all $b^{\prime}$
such that $q^{+}_{u}\leq b^{\prime}<q^{-}_{v}$ and
$S_{b^{\prime}}^{b^{\prime}+1}\subseteq X^{\prime}$. Note that
$S_{b}^{b+1}\subseteq X^{\prime}$ implies $S_{b}^{b+1}-A\subseteq X$. To
complete the proof we need the following claim.

######  Claim.

Let $Y$ be a subset of $H$ such that $S_{b}^{b+1}\subseteq Y\subseteq X$ where
$b$ is the maximum among all $b^{\prime}$ such that
$S_{b^{\prime}}^{b^{\prime}+1}\subseteq X$. Then $G\left[b+1,a\right]-(Y\cup
A)$ is connected.

###### Proof of Claim:.

Suppose $G\left[b+1,a\right]-(Y\cup A)$ is not connected. Let $Z=Y\cup A$ and
$C_{v}$ be the connected component containing a vertex $v\in Q_{a}$ (Note that
$Y_{A}^{a}\neq\emptyset)$) in $G\left[b+1,a\right]-Z$. Since
$G\left[b+1,a\right]-Z$ is not connected, there exists a vertex $u^{\prime}\in
G-Z$ such that $u^{\prime}\not\in C_{v}$. Let $C_{u^{\prime}}$ be the
connected component containing $u^{\prime}$. Observe that
$q^{+}_{u^{\prime}}<q^{-}_{v}=a$ and $G-Z$ is also not connected. Hence by
Observation 15, there exists an integer $b^{*}$ such that
$S_{b^{*}}^{b^{*}+1}\subseteq Z$ and $q^{+}_{u^{\prime}}\leq b^{*}<q^{-}_{v}$.
Since $u^{\prime}\in G\left[b+1,a\right]-Z$, the index $q^{+}_{u^{\prime}}>b$.
Thus it follows that $b<q^{+}_{u}\leq b^{*}<q^{-}_{v}$, which contradicts the
maximality of the index $b$. ∎

Let $H_{b}=G\left[b+1,a\right]-(S_{b}^{b+1}\cup A)$. Now we show that $H_{b}$
has diameter at most $s+1$. Otherwise, $H_{b}$ contains vertices that are at
distance greater than $s+1$ from the vertex $v$. Let $Q_{b^{\prime\prime}}$ be
the highest indexed maximal clique containing a vertex $x$ such that distance
between $x$ and $v$ in $H_{b}$ is exactly $s+2$. Observe that
$b^{\prime\prime}>b$. Now we show that
$S_{b^{\prime\prime}}^{b^{\prime\prime}+1}\subseteq X$ which contradicts the
maximality of $b$ (See the definition of $b$ defined in the above paragraph.)

For that, since $S_{b^{\prime\prime}}^{b^{\prime\prime}+1}\subseteq
Q_{b^{\prime\prime}+1}$, the maximality of $b^{\prime\prime}$ implies that the
vertices in $S_{b^{\prime\prime}}^{b^{\prime\prime}+1}$ are at distance $s+1$
from $v$ in $H_{b}$. Note that by the above claim, the induced subgraphs
$H_{b}$ and $G\left[b+1,a\right]-(X\cup A)$ are connected. Moreover, since $X$
is an $s$-CVD set of $H=G\left[1,a\right]-A$, when $S_{b}^{b+1}-A\subseteq X$
all vertices at distance greater than $s+1$ from the vertex $v$ in $H_{b}$
must be in $X-(S_{b}^{b+1}-A)$. Therefore,
$S_{b^{\prime\prime}}^{b^{\prime\prime}+1}\subseteq X$ and
$S_{b^{\prime\prime}}^{b^{\prime\prime}+1}\cup A\subseteq X^{\prime}$. This
contradicts the maximality of $b$. If the diameter of $H_{b}$ is exactly
$s+1$, then $X$ is of type-$4$. Otherwise, $X$ is of type-$3$. ∎

###  4.3 Some more observations

Let $H$ be an induced subgraph of $G$ and $u,v$ be two vertices of $H$. The
distance between $u$ and $v$ in $H$ is denoted by $d_{H}(u,v)$.

######  Observation 16.

Consider two integers $a,b$ with $1\leq a<b\leq k$ and a set
$A\in\mathcal{S}\left(Q_{b}\right)$. Let $H=G\left[1,b\right]-A$ and $u,v,w$
be three vertices of $H$ such that $\\{u,v\\}\subseteq Q_{b}-Q_{b-1}$ and
$w\in Q_{a}$. Then $d_{H}(u,w)=d_{H}(v,w)$.

###### Proof.

Suppose for contradiction that $d_{H}(u,w)\neq d_{H}(v,w)$. Without loss of
generality assume that $d_{H}(u,w)<d_{H}(v,w)$. Let $P$ be a shortest path
between $u$ and $w$ in $H$ and $u^{\prime}$ be the vertex in $P$ which is
adjacent to $u$. Observe that $u^{\prime}\in Q_{b}\cap Q_{b-1}$(this is
because: $u$ is not intersecting with the _Helly_ region of $Q_{b-1}$, $a<b$
in the ordering and P is a shortest path). Therefore $u^{\prime}$ is adjacent
to $v$ and $P^{\prime}=(P-\\{u\\})\cup\\{v\\}$ is a path between $v$ and $w$
such that $d_{H}(v,w)\leq|P^{\prime}|=|P|=d_{H}(u,w)$, a contradiction. ∎

######  Observation 17.

Let $C_{f}^{H}$ be the _frontal_ component of
$H=G\left[1,a\right]-A^{*},A^{*}\subseteq V(G)$. Let
$Y_{A^{*}}^{a}=(Q_{a}-Q_{a-1})-A^{*}$. If $Y_{A^{*}}^{a}\neq\emptyset$ then
any vertex $v\in Y_{A^{*}}^{a}$ is an end vertex of a diametral path (a
shortest path whose length is equal to the diameter of a graph) of
$C_{f}^{H}$.

###### Proof.

Suppose that $Y_{A^{*}}^{a}\neq\emptyset$ and no vertex $v\in Y_{A^{*}}^{a}$
is an end vertex of a diametral path of $C_{f}^{H}$. Let $P$ be a diametral
path of $C_{f}^{H}$ and $x,y$ be the end vertices. Observe that neither $x$
nor $y$ is in $Y_{A^{*}}^{a}$. Without loss of generality assume that
$q^{-}_{x}\leq q^{-}_{y}$. Let $P^{\prime}$ be a shortest path between $x$ and
$v$ where $v\in Y_{A^{*}}^{a}$. Since $P$ has the maximum size among the
shortest paths and $P^{{}^{\prime}}$ is not a diametral path, we have
$|P^{\prime}|<|P|$. Since $v\in Y_{A^{*}}^{a}$ and $x,y\notin Y_{A^{*}}^{a}$
we have $a=q^{-}_{v}>q^{-}_{y}\geq q^{-}_{x}$. Hence the path $P^{\prime}$
contains a vertex $w$ such that $w\neq v$ and $q^{-}_{w}\leq q^{-}_{y}\leq
q^{+}_{w}$ (That is, any path from $v$ to $x$ should cross the cliques
containing $y$). This implies $w$ is a neighbor of $y$ and there exists a path
$P^{\prime\prime}$ between $x$ and $y$ via $w$ such that
$|P^{\prime\prime}|\leq|P^{\prime}|$ (the path $P^{\prime\prime}$ is obtained
by adding the edge $wy$ to the subpath from $x$ to $w$ in $P^{\prime}$). Since
$|P^{\prime}|<|P|$, this contradicts the assumption that $P$ is a shortest
path between $x$ and $y$. Therefore, there exists at least one vertex $v\in
Y_{A^{*}}^{a}$ which is an end vertex of a diametral path of $C_{f}^{H}$. Then
by Observation 16, each vertex in $Y_{A^{*}}^{a}$ is an end vertex of a
diametral path of $C_{f}^{H}$. ∎

###  4.4 The algorithm

Our algorithm constructs a table $\Psi$ iteratively whose cells are indexed by
two parameters. For an integer $a,1\leq a\leq k$ and a set
$A\in\mathcal{S}\left(Q_{a}\right)$, the cell $\Psi[a,A]$ contains a minimum
$s$-CVD set of $G\left[1,a\right]-A$. Clearly, $\Psi[k,\emptyset]$ is a
minimum $s$-CVD set of $G$.

Now we start the construction of $\Psi$. Since $G\left[1,1\right]$ is a
clique, we set $\Psi[1,A]=\emptyset$ for all
$A\in\mathcal{S}\left(Q_{1}\right)$:

######  Lemma 14.

For any $A\in\mathcal{S}\left(Q_{1}\right)$, $\Psi[1,A]=\emptyset$.

From now on assume $a\geq 2$ and $A$ be a set in
$\mathcal{S}\left(Q_{a}\right)$. Let $H$ be the graph $G\left[1,a\right]-A$
and $F$ be the graph $G\left[1,a-1\right]-(A\cap Q_{a-1})$. Observe that for
any two integers $a,b,1\leq a<b\leq k$ the set $S_{a-1}^{b}=S_{a}^{b}\cap
Q_{a-1}$. Then, for any $A\in\mathcal{S}\left(Q_{a}\right)$ we have $(A\cap
Q_{a-1})\in\mathcal{S}\left(Q_{a-1}\right)$ and $\Psi[a-1,A\cap Q_{a-1}]$ is
defined. Note that $H-F=Y_{A}^{a}$.

In the following lemma we show that $\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$ if the
_frontal_ component of $H$ has diameter at most $s$.

######  Lemma 15.

Let $H=G\left[1,a\right]-A$, for $A\in\mathcal{S}\left(Q_{a}\right),1<a\leq
k$. If the _frontal_ component of $H$ has diameter at most $s$, then
$\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$.

###### Proof.

Let $F$ denote the graph $G\left[1,a-1\right]-(A\cap Q_{a-1})$. Since $H=F\cup
Y_{A}^{a}$, if $Y_{A}^{a}=\emptyset$ then $H=F$ and hence,
$\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$. Now assume that $Y_{A}^{a}\neq\emptyset$.
Observe that the connected components of $H$ and $F$ are same except the
_frontal_ components. The _frontal_ components of $H$ and $F$ differs
depending on the set $S_{a-1}^{a}$ as follows.

  1. i)

If $S_{a-1}^{a}\cap H=\emptyset$ then the _frontal_ component of $H$ is
$Y_{A}^{a}$.

  2. ii)

If $S_{a-1}^{a}\cap H\neq\emptyset$ then the _frontal_ component of $H$ is the
union of the _frontal_ component of $G\left[1,a-1\right]-A$ and $Y_{A}^{a}$.

If the _frontal_ component of $H$ is $Y_{A}^{a}$ then
$\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$ because diameter of $Y_{A}^{a}$ is $1$.
Hence assume that the _frontal_ component of $H$ belongs to the case (ii)
defined above. Let $C_{f}^{H}$ be the _frontal_ component of $H$ and
$C_{f}^{F}$ be the _frontal_ component of $F$. Then $C_{f}^{H}=C_{f}^{F}\cup
Y_{A}^{a}$. We have the following claim.

######  Claim.

Let $C_{f}^{H}=C_{f}^{F}\cup Y_{A}^{a}$. If the diameter of $C_{f}^{H}$ is at
most $s$ then the diameter of $C_{f}^{F}$ is also at most $s$.

###### Proof of Claim:.

Suppose not, then $C_{f}^{F}$ contains two vertices $u$ and $v$ such that the
distance between $u$ and $v$ in $C_{f}^{F}$ is at least $s+1$. Without loss of
generality, assume that $l(u)<l(v)$. Let $P$ be a shortest path between $u$
and $v$ in $C_{f}^{F}$. Observe that since $C_{f}^{F}=C_{f}^{H}-Y_{A}^{a}$, no
vertex $w\in Y_{A}^{a}$ belongs to $V(P)$. Moreover, for any vertex $w\in
Y_{A}^{a}$ we have $l(u)<l(v)<l(w)$ in the interval representation. Therefore,
any shortest path between $u$ and $v$ in $C_{f}^{H}$ does not contain a vertex
$w\in Y_{A}^{a}$. Hence the shortest path between $u$ and $v$ in $C_{f}^{H}$
is also at least $s+1$ which contradicts the assumption that the diameter of
$C_{f}^{H}$ is at most $s$. ∎

Hence by the minimality of $\Psi[a-1,A\cap Q_{a-1}]$, no vertices of
$C_{f}^{F}$ are in $\Psi[a-1,A\cap Q_{a-1}]$. Thus it follows that
$\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$. ∎

Now assume that the _frontal_ component of $H=G\left[1,a\right]-A$ has
diameter at least $s+1$. Recall that if $Y_{A}^{a}=\emptyset$, we have
$\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$. Hence assume that
$Y_{A}^{a}\neq\emptyset$. Due to Lemma 13, any $s$-CVD set of $H$ has to be
one of the four types defined in Section 4.2.

First, for each $j\in\\{1,2,3,4\\}$, we find an $s$-CVD set of minimum
cardinality, which is of type-$j$. We begin by showing how to construct a
minimum cardinality $s$-CVD set $X_{1}$ of type-$1$ of $G\left[1,a\right]-A$.
We define $X_{1}$ as below.

$X_{1}=Y^{a}_{A}\cup\Psi[a-1,A\cap Q_{a-1}]$ (21)

######  Lemma 16.

The set $X_{1}$ is a minimum cardinality $s$-CVD set of type-$1$ of
$G\left[1,a\right]-A$.

###### Proof.

Observe that the graph $H=G\left[1,a\right]-Y^{a}_{A}$ is isomporphic to
$G\left[1,a-1\right]-(A\cap Q_{a-1})$. Hence $X_{1}=Y^{a}_{A}\
\cup\Psi[a-1,A\cap Q_{a-1}]$ is an $s$-CVD set of $H$. By definition,
$Y^{a}_{A}$ is included in an $s$-CVD set of type-$1$. Hence the minimality of
$\Psi[a-1,A\cap Q_{a-1}]$ implies that $X_{1}$ is a minimum cardinality set of
type-$1$. ∎

Let $v$ be some vertex in $Y^{a}_{A}$ and $b<a$ be the maximum integer such
that $\left(Q_{b}\cap L_{H}\left(s+2,v\right)\right)\neq\emptyset$. We
construct a minimum cardinality $s$-CVD set of type-$2$ of
$G\left[1,a\right]-A$ defined as follows.

$X_{2}=L_{H}\left(s+1,v\right)\cup\Psi[b,S_{b}^{b+1}]$ (22)

######  Lemma 17.

The set $X_{2}$ is a minimum cardinality $s$-CVD set of type-$2$ of
$G\left[1,a\right]-A$.

###### Proof.

By the maximality of $b$ we have $S_{b}^{b+1}\subseteq
L_{H}\left(s+1,v\right)$. Moreover, the graph
$(G\left[b+1,a\right]-A)-L_{H}\left(s+1,v\right)$ is connected: otherwise, if
$L_{H}\left(s+1,v\right)$ is a separator of $(G\left[b+1,a\right]-A)$ then
$(S_{b^{\prime}}^{b^{\prime}+1}-A)\subseteq L_{H}\left(s+1,v\right)$ for some
$b^{\prime}>b$. Since $Q_{b^{\prime}}$ is a maximal clique there exists at
least one vertex $w\in Q_{b^{\prime}}$ and $w\not\in Q_{b^{\prime}+1}$. Hence
the distance between $w$ and $v$ is $s+2$ and $\left(Q_{b^{\prime}}\cap
L_{H}\left(s+2,v\right)\right)\neq\emptyset$. Since $b^{\prime}>b$, this
contradicts the maximality of $b$.
Since $(G\left[b+1,a\right]-A)-L_{H}\left(s+1,v\right)$ is connected we have
$((G\left[b+1,a\right]-A)-L_{H}\left(s+1,v\right))$ is a frontal component of
$G[1,a]-(A\cup L_{H}\left(s+1,v\right)$. Let $A^{\prime}=A\cup
L_{H}\left(s+1,v\right)$. Note that
$Y_{A^{\prime}}^{a}=Y_{A}^{a}\neq\emptyset$. Observe that the distance between
$v\in Y_{A^{\prime}}^{a}$ and any other vertex in
$(G\left[b+1,a\right]-A)-L_{H}\left(s+1,v\right)$ is at most $s$. Hence by
Observation 17, $(G\left[b+1,a\right]-A)-L_{H}\left(s+1,v\right)$ has diameter
at most $s$.
Note that any vertex of $G\left[1,b\right]$ that belongs to $A$ is also in
$S_{b}^{b+1}$. Hence $G\left[1,b\right]-(A\cup
S_{b}^{b+1})=G\left[1,b\right]-S_{b}^{b+1}$. Since $\Psi[b,S_{b}^{b+1}]$ is a
minimum cardinality $s$-CVD set of $G\left[1,b\right]-S_{b}^{b+1}$ the set
$X_{2}=L_{H}\left(s+1,v\right)\cup\Psi[b,S_{b}^{b+1}]$ is an $s$-CVD set of
$H$. By definition, $L_{H}\left(s+1,v\right)$ is included in an $s$-CVD set of
type-$2$. Observe that any vertex of $G\left[1,b\right]$ that belongs to
$L_{H}\left(s+1,v\right)$ is also in $S_{b}^{b+1}$ and hence the minimality of
$\Psi[b,S_{b}^{b+1}]$ implies that $X_{2}$ is a minimum cardinality set of
type-$2$. ∎

Now we show how to construct a minimum cardinality $s$-CVD set $X_{3}$ of
type-$3$ of $G\left[1,a\right]-A$. Let $B\subseteq\\{1,2,\ldots,a-1\\}$ be the
set of integers such that for any $i\in B$ the graph
$H_{i}=G\left[i+1,a\right]-(S_{i}^{i+1}\cup A)$ is connected and has diameter
at most $s$. By definition, a type-$3$ $s$-CVD set $X$ of $H$ contains
$S_{c}^{c+1}$ for some $c\in B$. We call each such type-$3$ $s$-CVD set as
type-$3(c)$. Now we define minimum type-$3(c)$ $s$-CVD set as follows.

$\begin{split}\text{For each }c\in B,\quad
Z_{c}&=(S_{c}^{c+1}-A)\cup\Psi[c,S_{c}^{c+1}]\\\ \end{split}$ (23)

######  Claim.

The set $Z_{c}$ is a minimum cardinality $s$-CVD set of type-$3(c)$ of
$G\left[1,a\right]-A$.

###### Proof of Claim.

Note that any vertex of $G\left[1,c\right]$ that belongs to $A$ is also in
$S_{c}^{c+1}$. By definition, $S_{c}^{c+1}$ separates the connected component
$G\left[c+1,a\right]-(S_{c}^{c+1}\cup A)$ from the rest of the graph namely,
$G\left[1,c\right]-(S_{c}^{c+1})$. Since the diameter of
$G\left[c+1,a\right]-(S_{c}^{c+1}\cup A)$ is at most $s$ and
$\Psi[c,S_{c}^{c+1}]$ is the minimal cardinality $s$-CVD set of
$G\left[1,c\right]-S_{c}^{c+1}$ the set
$Z_{c}=(S_{c}^{c+1}-A)\cup\Psi[c,S_{c}^{c+1}]$ is a minimum cardinality
$s$-CVD set of $H$ of type-$3(c)$. ∎

We define $X_{3}$ as below.

$X_{3}=\min\\{Z_{c}\colon c\in B\\}$ (24)

######  Lemma 18.

The set $X_{3}$ is a minimum cardinality $s$-CVD set of type-$3$ of
$G\left[1,a\right]-A$.

###### Proof.

The minimality of each $Z_{c}$ implies that the set $X_{3}$ is a minimum
cardinality type-$3$ $s$-CVD set. ∎

Finally, we show the construction of a minimum cardinality $s$-CVD set $X_{4}$
of type-$4$ of $G\left[1,a\right]-A$. Let $C\subseteq\\{1,2,\ldots,a-1\\}$ be
the set of integers such that for any $i\in C$ the graph
$H_{i}=G\left[i+1,a\right]-(S_{i}^{i+1}\cup A)$ is connected and has diameter
exactly $s+1$. By definition, a type-$4$ $s$-CVD set $X$ of $H$ contains
$S_{i}^{i+1}$ for some $i\in C$. We call each such type-$4$ $s$-CVD set as
type-$4(c)$. Now we define minimum type-$4(c)$ $s$-CVD set as follows. Note
that $Y_{A}^{a}\neq\emptyset$. Let $v$ be some vertex in $Y^{a}_{A}$ and
$Y_{i}=L_{H_{i}}\left(s+1,v\right)$.

$\begin{split}\text{For each }i\in C,\quad Z_{i}&=(S_{i}^{i+1}-A)\cup
Y_{i}\cup\Psi[i,S_{i}^{i+1}]\\\ \end{split}$ (25)

######  Claim.

The set $Z_{i}$ is a minimum cardinality $s$-CVD set of type-$4(c)$ of
$G\left[1,a\right]-A$.

###### Proof of Claim.

Recall that $H_{i}$ is connected and we claim that the graph $H_{i}-Y_{i}$ is
also connected: otherwise, if $Y_{i}$ is a separator of $H_{i}$ then there
exits a vertex $w$ in $H_{i}-Y_{i}$ such that $w$ does not belongs to the
component containing $v$ in $H_{i}-Y_{i}$. Since any path from $v$ to $w$ in
$H_{i}$ passes through $Y_{i}$, the distance of $w$ from $v$ in $H_{i}$ is at
least $s+2$ contradicting the assumption that $H_{i}$ has diameter exactly
$s+1$.
Since $H_{i}-Y_{i}$ is connected, it is the _frontal_ component of
$G\left[1,a\right]-A-(S_{i}^{i+1}\cup Y_{i})$. Let $A^{\prime}=A\cup
S_{i}^{i+1}\cup Y_{i}$. Note that $Y_{A^{\prime}}^{a}=Y_{A}^{a}\neq\emptyset$.
Hence the distance between $v\in Y_{A^{\prime}}^{a}$ and any other vertex in
$H_{i}-Y_{i}$ is at most $s$. Thus by Observation 17 the graph $H_{i}-Y_{i}$
has diameter at most $s$. Note that $\Psi[i,S_{i}^{i+1}]$ is the minimal
cardinality $s$-CVD set of $G\left[1,i\right]-S_{i}^{i+1}$ and any vertex of
$G\left[1,i\right]-S_{i}^{i+1}$ that belongs to $Y_{i}$ or $A$ is also in
$S_{i}^{i+1}$. Hence, the set $Z_{i}=(S_{i}^{i+1}-A)\cup
Y_{i}\cup\Psi[i,S_{i}^{i+1}]$ is a minimum $s$-CVD set of $H$ of type-$4(c)$.
∎

Now define $X_{4}$ as follows.

$X_{4}=\min\\{Z_{i}\colon i\in C\\}$ (26)

######  Lemma 19.

The set $X_{4}$ is a minimum cardinality $s$-CVD set of type-$4$ of
$G\left[1,a\right]-A$.

###### Proof.

The minimality of each $Z_{i}$ implies that the set $X_{4}$ is a minimum
cardinality type-$4$ $s$-CVD set. ∎

Now we define a minimum $s$-CVD set of $G\left[1,a\right]-A$ as the one with
minimum cardinality among the sets $X_{i},1\leq i\leq 4$. That is,

$\Psi[a,A]=\min\\{X_{1},X_{2},X_{3},X_{4}\\}$ (27)

A pseudocode of the procedure to find Equation 27 is given by Procedure 4.

1

2Let $H=G[1,a]-A$ and $Y_{A}^{a}=(Q_{a}-Q_{a-1})-A$

3 Set $X_{1}=Y_{A}^{a}\cup\Psi[a-1,A\cap Q_{a-1}]$

4 For a vertex $v\in Y^{a}_{A}$, find the maximum integer $b$ such that $b<a$
and $Q_{b}\cap L_{H}\left(s+2,v\right)\neq\emptyset$

5 Set $X_{2}=L_{H}\left(s+1,v\right)\cup\Psi[b,S_{b}^{b+1}]$

6 Set $B=C=\emptyset$

7 for  _$c=1\text{ to }a-1$_ do

8 if  __Diam_ $[c][a][A]\leq s$_ then

9 $Z_{c}=(S_{c}^{c+1}-A)\cup\Psi[c,S_{c}^{c+1}]$ $\triangleright$
$H_{c}=G\left[c+1,a\right]-(S_{c}^{c+1}\cup A)$

10 $B=B\cup\\{c\\}$

11 if  __Diam_ $[c][a][A]=s+1$_ then

12 $W_{c}=(S_{c}^{c+1}-A)\cup
L_{H_{c}}\left(s+1,v\right)\cup\Psi[c,S_{c}^{c+1}]$

13 $C=C\cup\\{c\\}$

14

15Set $X_{3}=\min\\{Z_{i}\colon i\in B\\}$

16 Set $X_{4}=\min\\{W_{i}\colon i\in C\\}$

17

18Set $\Psi[a,A]=\min\\{X_{1},X_{2},X_{3},X_{4}\\}$

19 Return $\Psi[a,A]$

Procedure 4 Compute_sCD$(G,a,A)$

We formally summarize the above discussion in the following lemma.

######  Lemma 20.

For $1<a\leq k$, if the diameter of the _frontal_ component of
$G\left[1,a\right]-A$ is at least $s+1$, then
$\Psi[a,A]=\min\\{X_{1},X_{2},X_{3},X_{4}\\}$.

###### Proof.

The proof follows from Lemma 13 and the above discussion on the minimality of
the sets $X_{i},1\leq i\leq 4$, in their respective types. ∎

The proof of correctness of the algorithm follows from the Lemmas 14, 15 and
20. A pseudocode of the algorithm for finding a minimum $s$-CVD set of an
interval graph is given in Algorithm 5. In the following section, we discuss
the time complexity of the algorithm.

Input : An interval graph $G$ and a positive integer $s$

Output : $\Psi[k,\emptyset]$

1 Using algorithm in [8] find the ordered set of maximal cliques of $G$, say
$Q_{1},Q_{2},\ldots,Q_{k}$ and $N_{\text{left}}(v)$, $q^{+}_{v}$ and
$q^{-}_{v}$ for each vertex $v\in V(G)$

2

3Find $\mathcal{S}\left(Q_{1}\right)$

4 for  _all $A\in\mathcal{S}\left(Q_{1}\right)$_ do

5 $\Psi[1,A]=\emptyset$

6

7for  _$a=2\text{ to }k$ _ do

8 Find $\mathcal{S}\left(Q_{a}\right)$

9 for  _$A\in\mathcal{S}\left(Q_{a}\right)$_ do

10 Set $Y_{A}^{a}=(Q_{a}-Q_{a-1})-A$

11 if  _$Y_{A}^{a}=\emptyset$_ then

12 $\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$

13 else

14 for  _$c=1\text{ to }a-1$_ do

15 Find the diameter of the induced subgraph $H_{c}=G[c+1,a]-(A\cup
S_{c}^{c+1})$ using $N_{\text{left}}(v),v\in Y_{A}^{a}$ and store it in
Diam$[c][a][A]$.

16 if  _diameter _Diam $[1][a][A]$_ of the _frontal_ component of
$H_{0}=G[1,a]-A\leq s$_ then

17 $\Psi[a,A]=\Psi[a-1,A\cap Q_{a-1}]$

18 else

19 $\Psi[a,A]=\textnormal{{Compute\\_sCD(G,a,A)}}$

20

21

22

23return

Algorithm 5 $s$-CVD$(G,s)$:G is an interval graph and $s$ is a positive
integer

###  4.5 Time complexity

For a given interval graph $G$ with $n$ vertices and $m$ edges, the algorithm
first finds the ordered set of maximal cliques of $G$ as described in Section
4.2. Such an ordered list of the maximal cliques of G can be produced in
linear time as a byproduct of the linear (O(n + m)) time recognition algorithm
for interval graphs due to Booth and Leuker [8]. For each vertex $v\in G$, the
algorithm gathers the following information during the enumeration of maximal
cliques: (i) the values $q^{-}_{v}$ and $q^{+}_{v}$ and (ii) the set of
neighbours of $v$ whose corresponding interval starts before that of $v$ which
we call as $N_{\text{left}}(v)$ and are ordered with respect to the left
endpoints.

Let $Q_{1},Q_{2},\ldots,Q_{k}$ be the ordered set of maximal cliques of $G$.
From the ordered set of cliques, the algorithm constructs the set
$\mathcal{S}\left(Q_{a}\right)$ (steps 2, 6, Algorithm 5) for each
$Q_{a},1\leq a<k$. For an integer $a,1\leq a<k$ the set
$\mathcal{S}\left(Q_{a}\right)$ can be constructed by adding a vertex $v\in
Q_{a}$ to each $S_{a}^{b}\in\mathcal{S}\left(Q_{a}\right)$ for $a<b\leq
q^{+}_{v}$. For the computation of each $\Psi[a,A],1\leq a\leq
k,A\in\mathcal{S}\left(Q_{a}\right)$ the algorithm needs to compute the
following: (i) the set of vertices, $Y_{A}^{a}$ (step 8, Algorithm 5); (ii)
the diameter of the frontal component of the graph $H=G[1,a]-A$ (step 14,
Algorithm 5) and (iii) the diameter of the induced subgraphs
$H_{c}=G[c+1,a]-(A\cup S_{c}^{c+1}),1\leq c\leq a-1$ (steps 12-13, Procedure
4).

The set $Y_{A}^{a}$ can be obtained from the vertex set of $Q_{a}$ in linear
time by checking the $q^{-}_{v}$ and $q^{+}_{v}$ values of each vertex $v\in
Q_{a}$. That is, $Y_{A}^{a}=\\{v\in Q_{a}:q^{-}_{v}=a\text{ and
}q^{+}_{v}<b,A=S_{a}^{b}\\}$. Let Diam$[1][a][A]$ be the diameter of the
frontal component of $H=G[1,a]-A$. By Observation 17, diameter of the frontal
component of $H$ is equal to the eccentricity of a vertex $v\in Y_{a}^{A}$.
That is, the maximum distance of $v$ from other vertices in $H$ which we
denote by ecc${}_{H}(v)$. Hence, Diam$[1][a][A]=$ecc${}_{H}(v)$. Let $v_{l}$
be the _leftmost_ neighbour of $v$ in $H$ such that $q^{-}_{v_{l}}=a^{\prime}$
and ecc${}_{H^{\prime}}(v_{l})$ be the eccentricity of $v_{l}$ in
$H^{\prime}=G[1,a^{\prime}]-(Q_{a^{\prime}}\cap Q_{b})$. Then observe that
ecc${}_{H}(v)$= ecc${}_{H^{\prime}}(v_{l})+1$. Therefore, Diam$[1][a][A]$ =
Diam$[1][a^{\prime}][Q_{a^{\prime}}\cap Q_{b}]+1$. Since the _leftmost_
neighbour of $v$ in $H$ can be found in linear time from $N_{\text{left}}(v)$
by checking the $q^{-}_{v}$ and $q^{+}_{v}$ values of each vertex $u\in
N_{\text{left}}(v)$, diameter of the frontal component of $H$ can be found in
$O(n)$ time. Similarly, diameter of the induced subgraphs
$H_{c}=G[c+1,a]-(A\cup S_{c}^{c+1})$ in steps 12 -13, Procedure 4 together can
be found in $O(n)$ time by similar arguments as above and the following
observation; $N_{\text{left}}(v)-(A\cup S_{c}^{c+1})\supseteq
N_{\text{left}}(v)-(A\cup S_{c+1}^{c+2})$.

To compute the overall time complexity of our algorithm, we have the following
claims.

######  Claim 2.

Total number of subproblems computed by the algorithm, Algorithm 5 is at most
$O(|V|+|E|)=O(n+m)$.

###### Proof of Claim.

Note that with respect to the ordering of maximal cliques of $G$ the elements
of the set $\mathcal{S}\left(Q_{a}\right)$ have the following relation. For
each $b,a<b\leq k$ we have $S_{a}^{b+1}\subseteq S_{a}^{b}$. Hence the number
of distinct subproblems computed by the algorithm corresponding to each
maximal clique $Q_{a}$ is at most $|S_{a}^{a+1}|+1$ (Recall that one of the
subproblem corresponds to $\emptyset\in\mathcal{S}\left(Q_{a}\right)$). Since
the number of maximal cliques in $G$ is at most $|V|=n$ and $|S_{a}^{a+1}|\leq
degree(v),v\in Q_{a}-Q_{a+1}$, the total number of subproblems computed by the
algorithm is at most $\sum\limits_{v\in Q_{a}-Q_{a+1}}degree(v)+|V|\leq
O(|V|+|E|)=O(n+m)$. ∎

######  Claim 3.

The procedure _Compute_sCD $(G,a,A)$_ computes the minimum cardinality $s$-CVD
set of $H=G\left[1,a\right]-A$ in $O(n)$ time.

###### Proof of Claim:.

Observe that the time complexity of the procedure _Compute_sCD $(G,a,A)$_
depends mainly on building the sets $X_{i},1\leq i\leq 4$. Since the set
$Y_{A}^{a},1\leq a<k,A\in\mathcal{S}\left(Q_{a}\right)$ is obtained in $O(n)$
time, the set $X_{1}$ can be computed in $O(n)$ time.
The set $L_{H}\left(s+1,v\right)$ can be computed from the leftmost neighbour
of $v$ in $H$, say $v_{l}$ in linear time by $s$ iterations: In the first
iteration, find the leftmost vertex of $v_{l}$ in $N_{\text{left}}(v_{l})-A$,
in the second iteration find the leftmost vertex in the second neighbourhood
and so on. Moreover, the leftmost neighbour of $v$ in $H$ can be obtained by a
linear search of $N_{\text{left}}(v)$. Since the number of induced subgraphs
$H_{c}$ is at most $O(n)$, the sets $X_{3}$ and $X_{4}$ can be constructed in
$O(n)$ time. Hence the claim follows. ∎

Therefore, by the above claims the overall time complexity of our algorithm is
$O(n\cdot(n+m))$ and Theorem 3 follows.

##  5 Hardness for well-partitioned chordal graphs

.

In this section, we prove Theorem 2. We shall use the following observation.

######  Observation 18.

Let $H$ be a well-partitioned chordal graph. Let $H^{\prime}$ be a graph
obtained from $H$ by adding a vertex of degree $1$. Then $H^{\prime}$ is an
well-partitioned chordal graph.

Let $s\geq 2$ be an even integer and let $s=2k$. We shall reduce Minimum
Vertex Cover (MVC) on general graphs to $s$-CVD on well partitioned graphs.
Let $\langle G,k\rangle$ be an instance of Minimum Vertex Cover such that
maximum degree of $G$ is at most $n-3$. Let $\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu$ denote the complement
of $G$. Now construct a split graph $G_{well}$ from $G$ as follows. For each
vertex of $v\in V(G)$, we introduce a new path $P_{v}$ with $k-1$ edges and
let $x_{v},x^{\prime}_{v}$ be the endpoints of $P_{v}$. For each edge $e\in
E\left(\mkern 1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu\right)$ we
introduce a new vertex $y_{e}$ in $G_{well}$. For each pair of edges
$e_{1},e_{2}\in E(\mkern 1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern
1.5mu)$ we introduce an edge between $y_{e_{1}}$ and $y_{e_{2}}$ in
$G_{well}$. For each edge $e=uv\in E\left(\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu\right)$, we introduce
the edges $x_{u}y_{e}$ and $x_{v}y_{e}$ in $G_{well}$. Observe that
$C=\\{y_{e}\\}_{e\in E\left(\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu\right)}$ is a clique,
$I=\\{x_{v}\\}_{v\in V(G)}$ is an independent set of $G_{well}$. Therefore
$C\cup I$ induces a split graph, say $G^{\prime}$, in $G_{well}$. Since
$G_{well}$ can be obtained from $G^{\prime}$ by adding vertices of degree $1$,
due to Observation 18, we have that $G_{well}$ is an well-partitioned graph.
We shall show that $G$ has a vertex cover of size $k$ if and only if
$G_{well}$ has a $s$-CVD set of size $k$.

######  Observation 19.

For each vertex $v\in C$, $|N[v]\cap I|=2$ and for each vertex $u\in I$,
$|N[u]\cap C|\geq 2$.

######  Lemma 21.

Let $D$ be a subset of $I$ and let $T=\\{u\in V(G)\colon x_{u}\in D\\}$. The
set $D$ is a $s$-CVD set of $G_{well}$ if and only if $T$ is a vertex cover of
$G$.

###### Proof.

Let $D^{\prime}=\\{x^{\prime}_{v}\colon x_{v}\in I-D\\}$ and
$T^{\prime}=\\{u\in V(G)\colon x_{u}\in D^{\prime}\\}$ (note that
$T=V(G)-T^{\prime}$). Note that there is one single component $G^{\prime}$ of
$G_{well}-D$ that contains vertices from $C$ since there are no isolated
vertices by observation 19. Observe that $G^{\prime}$ contains $I-D$.
Therefore, for any two vertices $x^{\prime}_{u},x^{\prime}_{v}\in D^{\prime}$
the distance between $x^{\prime}_{u},x^{\prime}_{v}$ is $s$ if and only if
there is an edge between $u,v$ in $\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu$. Therefore, distance
between any two pair of vertices in $D^{\prime}$ is $s$ if and only if
$T^{\prime}$ induces a clique in $\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu$ and therefore an
independent set in $G$. Since $T=V(G)-T^{\prime}$, we have that distance
between any two pair of vertices in $D^{\prime}$ is $s$ if and only if $T$ is
a vertex cover of $G$. Since $|D^{\prime}|=|I-D|$ we have that $D$ is an
$s$-CVD set of $G_{well}$ if and only if $T$ is a vertex cover of $G$. ∎

######  Lemma 22.

There is a subset of $I$ which is a minimum $s$-CVD set of $G_{well}$.

###### Proof.

Let $S$ be a minimum $s$-CVD set of $G_{well}$ such that $|S\cap I|$ is
maximum. We claim that $S\subseteq I$. Suppose for contradiction this is not
true. Let $I^{\prime}=\bigcup\limits_{u\in V(G)}P_{u}-\\{x_{u}\\}$. Then we
must have that $S\cap I^{\prime}\neq\emptyset$ or $S\cap C\neq\emptyset$. Let
$a$ be a vertex of $S\cap I^{\prime}$. Observe that there must be a vertex
$u\in V(G)$ such that $a\in P_{u}$ and that $(S-\\{a\\})\cup\\{x_{u}\\}$ is an
$s$-CVD set of $G_{well}$. This contradicts the assumption that $S$ is a
minimum $s$-CVD set of $G_{well}$ with $|S\cap I|$ maximum.

Now consider the collection $\mathcal{C}$ of connected components of
$G_{well}-S$. First, observe that there exists at most one connected component
in $\mathcal{C}$ that intersects $C$ (the clique of $G_{well}$). We shall call
such a component as the _big component_ and let $X$ be the set of vertices of
the big component. In fact $I$ itself is a $s$-CVD set and observation 19
implies $|I|\leq|C|$. Therefore, without loss of generality we can assume that
$C\not\subset S$ and indeed such a big component exists.

Let $Y$ denote those vertices of $G_{well}-S$ that belongs to $I-X$. Let
$S_{C}=S\cap C$ and $S_{I}=S\cap I$. Recall that by assumption,
$S_{C}\neq\emptyset$.

If there is a vertex $v\in S_{C}$ such that $|N[v]\cap Y|=0$, then $S-\\{v\\}$
is a $s$-CVD set with $X\cup\\{v\\}$ as corresponding big component with
diameter less than or equal to $s$. This contradicts the minimality of $S$.
Similarly, if there exists a vertex $v\in S_{C}$ such that $N[v]\cap
Y=\\{u\\}$, a singleton set then $S^{\prime}=S\cup\\{u\\}-\\{v\\}$ is a new
$s$-CVD set with $X\cup\\{v\\}$ as corresponding new big component. This
contradicts the assumption that $S$ is a minimum $s$-CVD set with $|S\cap I|$
is maximum. Hence together with observation 19 we infer that $|N(v)\cap Y|=2$,
for each $v\in S_{C}$. Observation 19 also implies that for each vertex $u\in
Y$, $|N(u)\cap S_{C}|\geq 2$, since $Y\subseteq I$ for each $u\in Y$ we have
$N(u)\subseteq S_{C}$. Therefore, $|Y|\leq|S_{C}|$ and
$S^{\prime}=(S-S_{C})\cup Y$ is a minimum $2$-CVD set with $X\cup S_{C}$ as
the corresponding new big component and $|S^{\prime}\cap I|>|S\cap I|$. This
contradicts the assumption for $S$.

Hence we conclude that $S$ is indeed a minimum $s$-CVD set such that
$S\subseteq I$. ∎

Lemmas 21 and 22 imply that $G$ has a vertex cover of size $k$ if and only if
$G_{well}$ has a $s$-CVD set of size $k$. Now Theorem 2 follows from a result
of Khot and Regev [22], where they showed that unless the Unique Games
Conjecture is false, there is no $(2-\epsilon)$-approximation algorithm for
Minimum Vertex Cover on general graphs, for any $\epsilon>0$.

##  6 Conclusion

In this paper we studied the computational complexity of $s$-CVD on well-
partitioned chordal graphs, a subclass of chordal graphs which generalizes
split graphs. We gave a polynomial-time algorithm for $s=1$ and we proved that
for any even integer $s\geq 2$, $s$-CVD is NP-hard on well-partitioned chordal
graphs. We also provide a faster algorithm for $s$-CVD on interval graphs for
each $s\geq 1$. This raises the following questions.

######  Question 1.

What is the time complexity of Cluster Vertex Deletion on chordal graphs?

######  Question 2.

What is the time complexity of $s$-CVD on chordal graphs for odd values of
$s$?

######  Question 3.

Is there a constant factor approximation algorithm for $s$-CVD, $s\geq 2$ on
chordal graphs?

Another generalisation of interval graphs is the class of _cocomparability_
graphs. It would be interesting to investigate the following question.

######  Question 4.

What is the time complexity of $s$-CVD on cocomparability graphs for each
$s\geq 1$?

## References

  * [1] Jungho Ahn, Lars Jaffke, O-joung Kwon, and Paloma T Lima.  Well-partitioned chordal graphs: obstruction set and disjoint paths.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 148–160. Springer, 2020.
  * [2] Jungho Ahn, Lars Jaffke, O-joung Kwon, and Paloma T Lima.  Three problems on well-partitioned chordal graphs.  In Algorithms and Complexity: 12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings 12, pages 23–36. Springer, 2021.
  * [3] Richard D Alba.  A graph-theoretic definition of a sociometric clique.  Journal of Mathematical Sociology, 3(1):113–126, 1973.
  * [4] Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh.  A tight approximation algorithm for the cluster vertex deletion problem.  In International Conference on Integer Programming and Combinatorial Optimization, pages 340–353. Springer, 2021.
  * [5] Balabhaskar Balasundaram, Sergiy Butenko, and Svyatoslav Trukhanov.  Novel approaches for analyzing biological networks.  Journal of Combinatorial Optimization, 10(1):23–39, 2005.
  * [6] Nikhil Bansal, Avrim Blum, and Shuchi Chawla.  Correlation clustering.  Machine learning, 56(1):89–113, 2004.
  * [7] Amir Ben-Dor, Ron Shamir, and Zohar Yakhini.  Clustering gene expression patterns.  Journal of computational biology, 6(3-4):281–297, 1999.
  * [8] Kellogg S. Booth and George S. Lueker.  Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms.  Journal of Computer and System Sciences, 13(3):335–379, 1976.
  * [9] Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk.  A fast branching algorithm for cluster vertex deletion.  Theory of Computing Systems, 58(2):357–376, 2016.
  * [10] Yixin Cao, Yuping Ke, Yota Otachi, and Jie You.  Vertex deletion problems on chordal graphs.  Theoretical Computer Science, 745:75–86, 2018.
  * [11] Dibyayan Chakraborty, L Sunil Chandran, Sajith Padinhatteeri, and Raji R Pillai.  Algorithms and complexity of s-club cluster vertex deletion.  In International Workshop on Combinatorial Algorithms, pages 152–164. Springer, 2021.
  * [12] Dibyayan Chakraborty, L Sunil Chandran, Sajith Padinhatteeri, and Raji R Pillai.  s-club cluster vertex deletion on interval and well-partitioned chordal graphs.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 129–143. Springer, 2022.
  * [13] Frank Dehne, Michael A Langston, Xuemei Luo, Sylvain Pitre, Peter Shaw, and Yun Zhang.  The cluster editing problem: Implementations and experiments.  In International Workshop on Parameterized and Exact Computation, pages 13–24. Springer, 2006.
  * [14] Michael R Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann.  Graph-based data clustering with overlaps.  Discrete Optimization, 8(1):2–17, 2011.
  * [15] Aleksander Figiel, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier.  On 2-clubs in graph-based data clustering: Theory and algorithm engineering.  In CIAC, pages 216–230, 2021.
  * [16] Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt.  Improved approximation algorithms for hitting 3-vertex paths.  In International Conference on Integer Programming and Combinatorial Optimization, pages 238–249. Springer, 2016.
  * [17] Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt.  Improved approximation algorithms for hitting 3-vertex paths.  Mathematical Programming, 182(1):355–367, 2020.
  * [18] Fedor V Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh.  Exact algorithms via monotone local search.  Journal of the ACM (JACM), 66(2):1–23, 2019.
  * [19] Fedor V Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi.  Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.  ACM Transactions on Algorithms (TALG), 15(1):1–44, 2019.
  * [20] Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Automated generation of search tree algorithms for hard graph modification problems.  Algorithmica, 39(4):321–347, 2004.
  * [21] Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier.  Fixed-parameter algorithms for cluster vertex deletion.  Theory of Computing Systems, 47(1):196–217, 2010.
  * [22] S. Khot and O. Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [23] Valerie King, Satish Rao, and Rorbert Tarjan.  A faster deterministic maximum flow algorithm.  Journal of Algorithms, 17(3):447–474, 1994.
  * [24] Jon Kleinberg and Eva Tardos.  Algorithm design.  Pearson Education India, 2006.
  * [25] J. M Lewis and M. Yannakakis.  The node-deletion problem for hereditary properties is NP-complete.  Journal of Computer and System Sciences, 20(2):219–230, 1980.
  * [26] H. Liu, P. Zhang, and D. Zhu.  On editing graphs into 2-club clusters.  In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, pages 235–246. Springer, 2012.
  * [27] Robert J. Mokken.  Cliques, clubs and clans.  Quality and Quantity, 13:161–173, 1979.
  * [28] James B Orlin.  Max flows in o (nm) time, or better.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 765–774, 2013.
  * [29] Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos.  Community detection in social media.  Data Mining and Knowledge Discovery, 24(3):515–554, 2012.
  * [30] Srinivas Pasupuleti.  Detection of protein complexes in protein interaction networks using n-clubs.  In European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, pages 153–164. Springer, 2008.
  * [31] Sven Rahmann, Tobias Wittkop, Jan Baumbach, Marcel Martin, Anke Truss, and Sebastian Böcker.  Exact and heuristic algorithms for weighted cluster editing.  In Computational Systems Bioinformatics: (Volume 6), pages 391–401. World Scientific, 2007.
  * [32] Ignasi Sau and Uéverton dos Santos Souza.  Hitting forbidden induced subgraphs on bounded treewidth graphs.  In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [33] A. Schäfer.  Exact algorithms for s-club finding and related problems.  Diploma thesis, Friedrich-Schiller-University Jena, 2009.
  * [34] Ron Shamir, Roded Sharan, and Dekel Tsur.  Cluster graph modification problems.  Discrete Applied Mathematics, 144(1-2):173–182, 2004.
  * [35] Roded Sharan and Ron Shamir.  CLICK: a clustering algorithm with applications to gene expression analysis.  In Proc Int Conf Intell Syst Mol Biol, volume 8, page 16, 2000.
  * [36] Victor Spirin and Leonid A Mirny.  Protein complexes and functional modules in molecular networks.  Proceedings of the national Academy of sciences, 100(21):12123–12128, 2003.
  * [37] Dekel Tsur.  Faster parameterized algorithm for cluster vertex deletion.  Theory of Computing Systems, 65(2):323–343, 2021.
  * [38] Zhenyu Wu and Richard Leahy.  An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation.  IEEE transactions on pattern analysis and machine intelligence, 15(11):1101–1113, 1993.
  * [39] Zhao Yang, René Algesheimer, and Claudio J Tessone.  A comparative analysis of community detection algorithms on artificial networks.  Scientific reports, 6(1):1–18, 2016.
  * [40] M. Yannakakis.  Node-and edge-deletion np-complete problems.  In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 253–264, 1978.
  * [41] Jie You, Jianxin Wang, and Yixin Cao.  Approximate association via dissociation.  Discrete Applied Mathematics, 219:202–209, 2017.