Revisiting Connected Vertex Cover: FPT Algorithms and
Lossy Kernels
R. Krithika, Diptapriyo Majumdar, and Venkatesh Raman

arXiv:1711.07872v1 [] 21 Nov 2017

The Institute of Mathematical Sciences, HBNI, Chennai, India.
{rkrithika|diptapriyom|vraman}@imsc.res.in

Abstract
The Connected Vertex Cover problem asks for a vertex cover in a graph that
induces a connected subgraph. The problem is known to be fixed-parameter tractable
(FPT), and is unlikely to have a polynomial sized kernel (under complexity theoretic
assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et
al. [STOC 2017], have shown an α-approximate kernel for the problem for every α > 1,
in the framework of approximate or lossy kernelization. We exhibit lossy kernels and
FPT algorithms for Connected Vertex Cover for parameters that are more natural
and functions of the input, and in some cases, smaller than the solution size.
Our first result is a lossy kernel for Connected Vertex Cover parameterized
by the size k of a split deletion set. A split graph is a graph whose vertex set can be
partitioned into a clique and an independent set and a split deletion set is a set of
vertices whose deletion results in a split graph. Let n denote the number of vertices in
the input graph. We show that
• Connected Vertex Cover parameterized by the size k of a split deletion set
d 2α−1
α−1 e ) vertices and a
admits an α-approximate kernel with O(k + (2k + d 2α−1
α−1 e)
k O(1)
3 n
time algorithm.
• For the special case when the split deletion set is a clique deletion set, the algorithm
runs in 2k nO(1) time and the lossy kernel has O(k + d 2α−1
α−1 e) vertices.

To the best of our knowledge, this (approximate) kernel is one of the few lossy kernels
for problems parameterized by a structural parameter (that is not solution size). We
extend this lossy kernelization to Connected Vertex Cover parameterized by an
incomparable parameter, and that is the size k of a clique cover. A clique cover of a
graph is a partition of its vertex set such that each part induces a clique. We show that
• Connected Vertex Cover parameterized by the size k of a clique cover is
W[1]-hard but admits an α-approximate kernel with O(kd 2α−1
α−1 e) vertices for every
α > 1. This is one of the few problems that are not FPT but admit a lossy kernel.
Then, we consider the size of a cluster deletion set as parameter. A cluster graph is a
graph in which every component is a complete graph and a cluster deletion set is a set
of vertices whose deletion results in a cluster graph. We show that
• Connected Vertex Cover parameterized by the size k of a cluster deletion set
is FPT via an 4k nO(1) time algorithm and admits an α-approximate kernel with
α
k
α
d α−1
e
O(k2 + d 2α−1
) vertices for every α > 1.
α−1 e · α−1 + d α−1 e · k

• For the special case when the cluster deletion set is a degree-1 modulator (a subset
of vertices whose deletion results in a graph with maximum degree 1), the FPT
k
α
algorithm runs in 3k nO(1) time and the lossy kernel has O(k2 + α−1
+ d α−1
e·
α
d α−1
e
k
) vertices.

1

Finally, we consider Connected Vertex Cover parameterized by the size k of a
chordal deletion set. A chordal graph is a graph in which every cycle of length at least
4 has a chord – an edge joining non-adjacent vertices of the cycle. A chordal deletion
set of a graph is a subset of vertices whose deletion results in a chordal graph. We
show that Connected Vertex Cover parameterized by k is FPT using the known
algorithm for Connected Vertex Cover on bounded treewidth graphs.

1

Introduction, Motivation and Our Results

A vertex cover in a graph is a set of vertices that has at least one endpoint from every edge
of the graph. In the Vertex Cover problem, given a graph G and an integer `, the task
is to determine if G has a vertex cover of size at most `. Undoubtedly, Vertex Cover
is one of the most well studied problems in parameterized complexity. In this framework,
each problem instance is associated with a non-negative integer called parameter. The pair
consisting of a decision problem and a parameterization is called a parameterized problem. A
common parameter is a bound on the size of an optimum solution for the problem instance.
A problem is said to be fixed-parameter tractable (FPT) with respect to parameter k if it can
be solved in f(k)nO(1) time for some computable function f, where n is the input size. Such
an algorithm is called a parameterized algorithm or FPT algorithm. For convenience, the
running time f(k)nO(1) where f grows super-polynomially with k is denoted as O∗ (f(k)). A
kernelization algorithm is a polynomial-time algorithm that transforms an arbitrary instance
of the problem to an equivalent instance of the same problem whose size is bounded by some
computable function g of the parameter of the original instance. The resulting instance is
called a kernel and if g is a polynomial function, then it is called a polynomial kernel and
we say that the problem admits a polynomial kernel. In order to classify parameterized
problems as being FPT or not, the W-hierarchy: FPT ⊆ W[1] ⊆ W[2] ⊆ · · · ⊆ XP is defined.
It is believed that the subset relations in this sequence are all strict and a parameterized
problem that is hard for some complexity class above FPT in this hierarchy is unlikely to
be FPT. A parameterized problem is said to be in XP if it has an algorithm with runtime
f(k)ng(k) time for some computable functions f and g. A problem is said to be para-NP-hard
if it is not in XP unless P=NP. The complexity classes FPT and para-NP can be viewed as
the parameterized analogues of P and NP.
Vertex Cover is FPT via an easy O∗ (2` ) algorithm and after a long race, the current
fastest algorithm runs in O∗ (1.2738` ) time [6]. Vertex Cover also has a kernel with
2` − O(log `) vertices and O(`2 ) edges [21]. In the Connected Vertex Cover problem,
we seek a connected vertex cover, i.e., a vertex cover that induces a connected subgraph. It
is easy to observe that Vertex Cover reduces to Connected Vertex Cover implying
that the latter is at least as hard as the former in general graphs. In fact, Connected
Vertex Cover is NP-hard even on bipartite graphs [13] where Vertex Cover is solvable in
polynomial time (Theorem 2.1.1 [11]). However, Connected Vertex Cover is polynomialtime solvable on chordal graphs and sub-cubic graphs [13,26] and has an O∗ (2O(t) ) algorithm
when the input graph has treewidth upper bounded by t [2]. The best known parameterized
algorithm for Connected Vertex Cover takes O∗ (2` ) time where ` is the size of the
connected vertex cover that we are looking for [7]. Further, the problem does not admit
a polynomial kernel unless the polynomial hierarchy collapses (specifically, unless NP ⊆
coNP/poly) [12].
As the goal in parameterized algorithms is to eventually solve the given instance of a
problem, the application of a (classical) kernelization algorithm is typically followed by an
exact or approximation algorithm that finds a solution for the reduced instance. However,
the current definition of kernels provide no insight into how this solution relates to a solution
2

for the original instance and the basic framework is not amenable to be a precursor to
approximation algorithms or heuristics. Recently, Lokshtanov et al. [22] proposed a new
framework, referred to as lossy kernelization, that is a bit less stringent than the notion of
polynomial kernels and combines well with approximation algorithms and heuristics. The
key new definition in this framework is that of an α-approximate kernelization. The precise
definitions are deferred to Section 2. Informally, an α-approximate polynomial kernelization
(lossy kernelization) is a polynomial time preprocessing algorithm that takes as input an
instance of a parameterized problem and outputs another instance of the same problem
whose size is bounded by a polynomial function of the parameter of the original instance.
Additionally, for every c ≥ 1, a c-approximate solution for the reduced instance can be
turned into a (αc)-approximate solution for the original instance in polynomial time. The
authors of [22] exhibit lossy polynomial kernels for several problems that do not admit
classical polynomial kernels including Connected Vertex Cover parameterized by the
solution size. In this paper, we extend this lossy kernel for Connected Vertex Cover to
parameters that are more natural and functions of the input, and in some cases, smaller
than the solution size.
In the initial work on parameterized complexity, the parameter was almost always the
solution size (with treewidth being a notable exception). A recent trend is to study the
complexity of the given problem with respect to structural parameters that are more likely
to be small in practice. Also, once a problem is shown to be FPT or to have a polynomial
sized kernel by a parameterization, it is natural to ask whether the problem is FPT (and
admits a polynomial kernel) when parameterized by a smaller parameter. Similarly, once
a problem is shown to be W-hard by a parameterization, it is natural to ask whether the
problem is FPT when parameterized by a larger parameter. Structural parameterizations
of Vertex Cover [3, 18], Feedback Vertex Set [20] and Graph Coloring [19] have
been explored extensively. We refer to [18] and [17] for a detailed introduction to the
whole program. A parameter that has gained significant attention recently is the size of
a modulator to a family of graphs. Let F denote a hereditary graph class (which is closed
under induced subgraphs) on which Vertex Cover is polynomial-time solvable. Suppose
S is a set of vertices (called a F-modulator) such that G − S ∈ F. Then, Vertex Cover is
FPT when parameterized by the size of |S|. Following is an easy O∗ (2|S| ) algorithm: guess
the intersection of the required solution with the modulator and solve the problem on the
remaining graph in polynomial time. In contrast, a similar generic result does not seem
easy for Connected Vertex Cover and a study of such structural parameterizations for
Connected Vertex Cover is another goal of this paper.
Our Results. The starting point of our study is to extend the lossy kernelization known
for Connected Vertex Cover parameterized by solution size to Connected Vertex
Cover parameterized by a smaller parameter. A split graph is a graph whose vertex set
can be partitioned into a clique and an independent set. Split graphs can be recognized in
polynomial time and such a partition can be obtained in the process [16]. A split deletion
set is a set of vertices whose deletion results in a split graph. Connected Vertex Cover
has an easy polynomial time algorithm in split graphs, and it is easy to verify that the size
of minimum connected vertex cover is at least the size of the minimum vertex cover which
is at least the size of the minimum split deletion set. We show that
• Connected Vertex Cover parameterized by the size k of a split deletion set is FPT
via an O∗ (3k ) algorithm and that the α-approximate kernel for Connected Vertex
Cover parameterized by solution size can be extended in a non-trivial way to an
d 2α−1
e
α−1 ) vertices for every α > 1. This
α-approximate kernel with O(k + (2k + d 2α−1
α−1 e)
adds to the small list of problems for which lossy kernels with respect to structural
3

parameterizations are known.
• For the special case when the split deletion set is a clique deletion set (a set of vertices
whose deletion results in a complete graph), the algorithm runs in O∗ (2k ) time and
the lossy kernel has O(k + d 2α−1
α−1 e) vertices (linear size).
Then, we consider Connected Vertex Cover parameterized by the size of a clique cover.
A clique cover of a graph is a partition of its vertex set such that each part induces a clique.
We show that
• Connected Vertex Cover parameterized by the size k of a clique cover is W[1]-hard
but admits an α-approximate kernel with O(kd 2α−1
α−1 e) vertices for every α > 1. This
is one of the few problems that are not FPT but admit a lossy kernel.
Then, we consider a parameter related (structurally) to clique cover size, namely, the size of
a cluster deletion set and show that Connected Vertex Cover is FPT with respect to
this parameter. A cluster graph is a graph in which every component is a complete graph
and a cluster deletion set is a set of vertices whose deletion results in a cluster graph. We
show that
• Connected Vertex Cover parameterized by the size k of a cluster deletion set
is FPT via an O∗ (4k ) algorithm and admits an α-approximate kernel with O(k2 +
α
d α−1
e
k
α
d 2α−1
) vertices for every α > 1.
α−1 e · α−1 + d α−1 e · k
• For the special case when the cluster deletion set is a degree-1 modulator (a subset
of vertices whose deletion results in a graph with maximum degree 1), the algorithm
α
α
k
runs in O∗ (3k ) time and the lossy kernel has O(k2 + α−1
+ d α−1
e · kd α−1 e ) vertices.
Finally, we consider Connected Vertex Cover parameterized by the size k of a chordal
deletion set. A chordal graph is a graph in which every cycle of length at least 4 has a chord
– an edge joining non-adjacent vertices of the cycle. A chordal deletion set of a graph is a
subset of vertices whose deletion results in a chordal graph. We show that Connected
Vertex Cover parameterized by k is FPT using the known algorithm for Connected
Vertex Cover on bounded treewidth graphs. A summary of these results is presented in
Figure 1.
Techniques. Our FPT algorithms involve a reduction to the Steiner Tree problem on
bipartite graphs. Given a graph G, an integer p and a set T (called terminals) of vertices of
G, the Steiner Tree problem is the task of determining whether G contains a tree (called
Steiner tree) on at most p vertices that contains T . A bipartite graph is a graph whose vertex
set can be partitioned into 2 independent sets. Such a partition is called a bipartition. We
use the following result known for Steiner Tree on bipartite graphs.
Lemma 1. [7, 25] Given a connected bipartite graph G with bipartition (P, Q), there is an
algorithm running in O∗ (2|Q| ) time that computes a minimum set X of vertices of G such
that Q ⊆ X and G[X] is connected.
Our lower bound results are based on the hardness results known for the Set Cover
problem. Given a family F of subsets of a universe U and a positive integer `, the Set
Cover problem isSthe task of determining whether there is a subfamily F 0 ⊆ F of size at
most ` such that X∈F 0 X = U. Set Cover can be solved in O∗ (2|U| ) time by a dynamic
programming routine [14] and the Set Cover Conjecture states that no O∗ ((2 − )|U| ) time
algorithm exists for any  > 0 [8]. Our lower bound results are based on the following result
that is a consequence of this conjecture.
4

Connected
Vertex Cover
Clique
Deletion Set

Vertex
Cover

Split
Deletion Set

Modulator

Cluster
Deletion Set

Feedback
Vertex Set

Degree-1

Chordal
Deletion Set

Degree-2
Modulator
Degree-i(i 3)
Modulator

FPT
FPT and
admits P SAKS

para-N P -hard

Figure 1: Ecology of Parameters for Connected Vertex Cover. The parameter values
are the minimum possible for a given graph. An arrow from parameter x to parameter y
means y ≤ x.
Lemma 2. [8] Connected Vertex Cover parameterized by the solution size ` has no
O∗ ((2 − )` ) time algorithm under the Set Cover Conjecture.
For each of the parameterized problems considered in this paper, we assume that the
modulator (whose size is the parameter) under consideration is given as part of the input.
In most cases, this assumption is reasonable. For instance, there is an algorithm by Cygan
and Pilipczuk [10] that runs in O∗ (1.2732k+o(k) ) time and returns a split deletion set of
size at most k (or decides that no such set exists). In the case of cluster deletion set size
as parameter, we use the algorithm by Boral et al. [5] that runs in O∗ (1.9102k ) time and
returns a cluster deletion set of size at most k, if one exists. Also, a degree-1 modulator S
of size at most k, if one exists, can be obtained in O∗ (1.882k ) time using the algorithm by
Wu [27]. Finally, there is an algorithm by Marx [23] that runs in O∗ (2O(k log k) ) time and
either outputs a chordal deletion set of size k or decides that no such set exists.

2

Preliminaries

We refer to [11] for graph theoretic terms and notation that are not explicitly
 defined here.
A
We use [r] to denote the set {1, 2, . . . , r}. Given a finite set A, we use k to denote the

A
collection of subsets of A containing exactly k elements and we use ≤k
to denote the
collection of subsets of A containing at most k elements.
For a graph G, V(G) and E(G) denote the set of vertices and edges respectively. Two
vertices u, v are said to be adjacent if there is an edge {u, v} in the graph. The neighbourhood
of a vertex v, denoted by NG (v), is the set of vertices adjacent to v and its degree dG (v)
is |NG (v)|. The subscript in the notation for neighbourhood and degree is omitted if the
5

graph under consideration is clear. For a set S ⊆ V(G), G − S denotes the graph obtained
by deleting S from G and G[S] denotes the subgraph of G induced by set S. The contraction
operation of an edge e = uv in G results in the deletion of u and v and the addition of a new
vertex w adjacent to vertices that were adjacent to either u or v. Any parallel edges added
in the process are deleted so that the graph remains simple. This operation is extended to a
subset of edges and the resultant graph is oblivious to the contraction sequence. A path is a
sequence of distinct vertices where every consecutive pair of vertices are adjacent. A set of
pairwise non-adjacent vertices is called as an independent set and a set of pairwise adjacent
vertices is called as a clique. A complete graph is a graph whose vertex set is a clique. The
number of components of a graph G is denoted by #comp(G) and by convention if G is
connected then #comp(G) is 1. Two non-adjacent vertices u and v are called false twins if
N(u) = N(v).
A tree-decomposition of a graph G is a pair (T, X = {Xt }t∈V(T) ) such that T is a tree
whose every node t is assigned a vertex subset Xt , called a bag, satisfying the following
properties.
S
• t∈V(T) Xt = V(G).
• For every edge {x, y} ∈ E(G) there is a t ∈ V(T) such that {x, y} ⊆ Xt .
• For every vertex v ∈ V(G) the subgraph of T induced by the set {t | v ∈ Xt } is
connected.
The width of a tree decomposition is maxt∈V(T) |Xt | − 1 and the treewidth of G, denoted by
tw(G), is the minimum width over all tree decompositions of G.
Lossy Kernelization: Parameterized complexity terminology and definitions not stated
here can be found in [9]. We now state terminology and definitions related to lossy kernelization given in [22]. The key definition in this framework is the notion of a parameterized
optimization (maximization / minimization) problem which is the parameterized analogue
of an optimization problem in the theory of approximation algorithms. A parameterized
minimization problem is a computable function Π : Σ∗ × N × Σ∗ 7→ R ∪ {±∞}. The instances of Π are pairs (I, k) ∈ Σ∗ × N and a solution for (I, k) is a string S ∈ Σ∗ such
that |S| ≤ |I| + k. The value of a solution S is Π(I, k, S). The optimum value of (I, k) is
OPTΠ (I, k) =
min
Π(I, k, S), and an optimum solution for (I, k) is a solution S such
S∈Σ∗ , |S|≤|I|+k

that Π(I, k, S) = OPTΠ (I, k). A parameterized maximization problem is defined in a similar
way. We will omit the subscript Π in the notation for optimum value if the problem under
consideration is clear from context.
Next, we define the notion of a strict α-approximate polynomial-time preprocessing
algorithm for Π. It is defined as a pair of polynomial-time algorithms, called the reduction
algorithm and the solution lifting algorithm, that satisfy the following properties.
• Given an instance (I, k) of Π, the reduction algorithm computes an instance (I 0 , k 0 ) of
Π.
• Given the instances (I, k) and (I 0 , k 0 ) of Π, and a solution S 0 to (I 0 , k 0 ), the solution
Π(I,k,S)
Π(I 0 ,k 0 ,S 0 )
lifting algorithm computes a solution S to (I, k) such that OPT(I,k)
≤ max{ OPT(I
0 ,k 0 ) , α}.
A reduction rule is the execution of the reduction algorithm on an instance, and we say that
it is applicable on an instance if the output instance is different from the input instance. An
α-approximate kernelization (or α-approximate kernel) for Π is an α-approximate polynomialtime preprocessing algorithm such that the size of the output instance is upper bounded by
a computable function g : N → N of k. A reduction rule is said to be α-safe for Π if there
6

is a solution lifting algorithm, such that the rule together with this algorithm constitute a
strict α-approximate polynomial-time preprocessing algorithm for Π. A reduction rule is
safe if it is 1-safe. Observe that this definition is more strict that the definition of safeness
in classical kernelization. A polynomial-size approximate kernelization scheme (PSAKS) for
Π is a family of α-approximate polynomial kernelization algorithms for each α > 1. Note
that, the size of an output instance of a PSAKS, when run on (I, k) with approximation
parameter α, must be upper bounded by f(α)kg(α) for some functions f and g independent
of |I| and k. A PSAKS is said to be time efficient if the reduction algorithm and the solution
lifting algorithm run in f(α)|I|c , for some computable function f. We encourage the reader
to see [22] for a more comprehensive discussion of these ideas and definitions.

3

Connected Vertex Cover parameterized by Split Deletion
Set

In this section, we describe an FPT algorithm and a lossy polynomial kernel for Connected
Vertex Cover parameterized by the size of a split deletion set. Recall that a split deletion
set is a set of vertices whose deletion results in a split graph.

3.1

An FPT algorithm

In this subsection we describe an O∗ (3k ) time algorithm for Connected Vertex Cover
parameterized by the size k of a split deletion set.
Theorem 3. Given a graph G, a split deletion set S and a positive integer `, there is an
algorithm that determines whether G has a connected vertex cover of size at most ` in O∗ (3|S| )
time. Moreover, no O∗ ((2 − )|S| ) time algorithm exists for any  > 0 for this problem under
the Set Cover Conjecture. Further, if S is a clique deletion set, then there is an algorithm
that runs in O∗ (2|S| ) time.
Proof. Let H denote the split graph G − S whose vertex set can be partitioned into a clique
C and an independent set I. Let |S| = k and let X∗ be a connected vertex cover of G of size
at most ` (if one exists). We show that once we guess the intersection of X∗ with S and C,
the problem reduces to a version of the Steiner tree problem with at most |S| terminals. As
X∗ can afford to exclude at most one vertex from C, there are at most |C| + 1 choices for
X∗ ∩ C. Also, there are at most 2k choices for X∗ ∩ S. Consider one such choice (Y, Z) where
Y = X∗ ∩ C and Z = X∗ ∩ S. Let T denote the set Y ∪ Z. We will extend T into a connected
vertex cover of G. If (C \ Y) ∪ (S \ Z) is not an independent set, no such connected vertex
cover exists and we skip to the next choice of (Y, Z). Let us first consider the case when
I = ∅. That is, S is a clique deletion set of G. In this case, as we have already made our
choice in S and C, and so if G[T ] is not connected, we can skip to the next choice of (Y, Z).
If none of the choices leads to the required solution, we declare that G has no connected
vertex cover of size at most `. The overall running time of the algorithm is O∗ (2k ).
When I 6= ∅, observe that G[T ] has at most |Z| + 1 components. Let R denote the set
(N(C \ Y) ∪ N(S \ Z)) \ (Y ∪ Z). Clearly, R ⊆ I and has to be included in the solution. See
Figure 2. If there is a vertex r ∈ R that has no neighbours in T , then r cannot be connected
to T by vertices from I as R ⊆ I. Therefore, if there is such a vertex r, then we skip to
the next choice of (Y, Z). Otherwise, by adding R to T , #comp(G[T ]) cannot increase in
this process. The problem now reduces to finding a set J ⊆ I \ R such that G[T ∪ R ∪ J] is
connected.
b with bipartition (T ∗ , I \ R) where each vertex of
Now consider the bipartite graph G
∗
T corresponds to a component of G[T ∪ R]. We draw an edge between a vertex p ∈ I \ R
7

S = split deletion set

Z

H=G
Y

R

S

• Y [ Z = Vertices included in solution.
• R = Vertices that are forced into
solution by choice of Y [ Z.

J

• J = Vertices that are required to connect
the components of G[Y [ Z [ R].

C

I

Clique Independent
Set

Figure 2: Connected vertex cover parameterized by split deletion set.
and a vertex c in T ∗ if there is an edge in G between p and a vertex in the component
b with terminal set
corresponding to c. The task now is to find a minimum Steiner tree of G
∗|
∗
∗
|T
T which can be done
Pkin Ok(2i ) time using Lemma 1. Therefore, the overall running time
of the algorithm is i=0 i 2 where the first term in the product denotes the number of
choices for X∗ ∩ S where |X∗ ∩ S| = i and the second term is the time taken to find a minimum
Steiner tree for an instance with at most i terminals. Thus, the algorithm runs in O∗ (3k )
time. As an edgeless graph is a split graph, we have that the size of a minimum connected
vertex cover is at least the size of a minimum connected split deletion set. Therefore, the
claimed lower bound follows from Lemma 2.
In order to obtain a tighter and refined analysis of the running time of the above
algorithm, we generalize the following lemma. Here VC(H) denotes the set of vertex covers
of H.
P
Lemma 4. [7] Let H be a connected graph on h vertices. Then,
2#comp(H[C]) ≤
C∈VC(H)

3·

2h−1 .

We next generalize Lemma 4 to graphs that are not necessarily connected.
P
Lemma 5. Let H be a graph on h vertices with #comp(H) = d. Then,
2#comp(H[C]) ≤
C∈VC(H)

3d 2h−d .
Proof. Let H1 , · · · , Hd denote the components of H and let hi denote the number of vertices
in Hi . Then, any vertex cover of H is the union of the vertex covers of Hi for 1 ≤ i ≤ d.
Thus, we have the following bound from Lemma 4.
X
C∈VC(H)

2#comp(H[C]) =

d
Y

X

2#comp(Hi [C]) ≤

i=1 C∈VC(Hi )

d
Y
i=1

3 · 2hi −1 = 3d · 2h−d

Now, using Lemma 5 and Theorem 3, we have the following result.
Corollary 6. Given a graph G, a split deletion set S with #comp(G[S]) = d and a positive
integer `, there is an algorithm that determines whether G has a connected vertex cover of
size at most ` in O∗ (3d 2|S|−d ) time.
8

Proof. The running time of the
presented in Theorem 3 is upper bounded (ignoring
P algorithm
polynomial factors) by
2#comp(G[Z]) which in turn is upper bounded by 3d 2|S|−d
Z∈VC(G[S])

from Lemma 5. Therefore, the claimed bound follows.
Using Lemma 2, Corollary 6 and the fact that a vertex cover of size k (if one exists) can
be obtained in O∗ (1.2738` ) time [6], we have the following result.
Corollary 7. Given a graph G, a vertex cover S with #comp(G[S]) = d and a positive
integer `, there is an algorithm that determines whether G has a connected vertex cover of
size at most ` in O∗ (3d 2|S|−d ) time. Further, no O∗ ((2 − )|S| ) time algorithm exists for this
problem for any  > 0 under the Set Cover Conjecture.

3.2

A Lossy Kernel

It is known that Vertex Cover parameterized by the size of a clique deletion set has no
polynomial kernel unless NP ⊆ coNP/poly [4]. As Vertex Cover reduces to Connected
Vertex Cover by just adding a universal vertex to the graph, we have the following
observation.
Observation 1. Connected Vertex Cover parameterized by the size of a clique deletion
set has no polynomial kernel unless NP ⊆ coNP/poly.
In this section, we show that Connected Vertex Cover parameterized by the size
of a split deletion set admits a lossy polynomial kernel. As a consequence, we show that
Connected Vertex Cover parameterized by the size of a clique deletion set admits a
lossy linear kernel. The parameterized minimization problem definition of interest to us is
the following. The cases specified in the definition are ordered, i.e., given (G, S), an integer
k and a set T ⊆ V(G), CVC((G,
S), k, T ) is assigned the first value applicable.


−∞
if
|S| > k or G − S is not a split graph

CVC((G, S), k, T ) = ∞
if T is not a connected vertex cover


|T |
otherwise
Without loss of generality, we assume that G has no isolated vertices as no minimum
connected vertex cover contains them. Given α > 1, let d be the minimum integer greater
d−1
than 1 such that α ≥ d−2
. That is, d = d 2α−1
α−1 e. Let H denote the split graph G − S whose
vertex set can be partitioned into a clique C and an independent set I. First, we bound the
number of vertices in C by applying Reduction Rule 3.1.
Reduction Rule 3.1. If |C| ≥ d, then add a new vertex uC adjacent to N(C) and delete
C to get the graph G 0 . The resulting instance is (G 0 , S).
Observe that S continues to be a split deletion set of G 0 as a result of applying this rule
since V(G 0 − S) can be partitioned into the clique {uC } and the independent set I.
Lemma 8. Reduction Rule 3.1 is α-safe.
Proof. Consider a solution D 0 of the reduced instance. If uC ∈ D 0 , then the solution
lifting algorithm returns D = (D 0 \ {uC }) ∪ C which is a connected vertex cover of G
such that CVC((G, S), k, D) = CVC((G 0 , S), k, D 0 ) − 1 + |C|. Otherwise, we know that
N(C) ⊆ D 0 . Let x be a vertex in C such that C \ {x} has a neighbour in V(G 0 ) \ C.
Then, D = D 0 ∪ (C \ {x}) is a connected vertex cover of G such that CVC((G, S), k, D) =
CVC((G 0 , S), k, D 0 ) + |C| − 1. In any case, we have shown that CVC((G, S), k, D) =
CVC((G 0 , S), k, D 0 ) + |C| − 1. Now, consider an optimum solution D∗ for the original
9

instance. Clearly, |D∗ ∩ C| ≥ |C| − 1. Then, (D∗ \ C) ∪ {uC } is a connected vertex cover of G 0 .
Hence, OPT((G 0 , S), k) ≤ OPT((G, S), k) − |C| + 1 + 1. Combining these bounds, we have
CVC((G,S),k,D)
CVC((G 0 ,S),k,D 0 ) |C|−1
CVC((G 0 ,S),k,D 0 )
OPT((G,S),k) ≤ max
OPT((G 0 ,S),k) , |C|−2 ≤ max
OPT((G 0 ,S),k) , α} as |C| ≥ d.
Observe that the application of Reduction Rule 3.1 does not make any vertex isolated in
the reduced graph. Further, when S is a clique deletion set and this rule is not applicable, it
follows that G − S has at most d − 1 vertices. This leads to the following result.
Theorem 9. Connected Vertex Cover parameterized by the size k of a clique deletion
set has a time efficient PSAKS with at most k + d 2α−1
α−1 e vertices.
Proof. Let (G, S, `) be an instance on which Reduction Rule 3.1 is not applicable. Then,
|S| ≤ k and |V(G − S)| ≤ d where d = d 2α−1
α−1 e. Therefore, |V(G)| ≤ k + d.
Let us now consider the case when S is not a clique deletion set.
Lemma 10. Let (G, S) be an instance on which Reduction Rule 3.1 is not applicable. Then,
G has a connected vertex cover of size at most 2k + d − 1.
Proof. If Reduction Rule 3.1 is not applicable, then |C| ≤ d − 1. Now, T = S ∪ C is a vertex
cover of G such that G[T ] has at most |S| + 1 components. If G[T ] is not connected, then we
can add at most |S| vertices from V(G) \ T to T so that G[T ] becomes connected. Such a
choice of vertices exists as G is connected. Hence, it follows that G has a connected vertex
cover of size at most |T | + |S| ≤ 2k + d − 1.
From Lemma 10, we have OPT((G, S), k) ≤ 2k + d − 1. Therefore, any vertex with at
least 2k + d neighbours is present in any optimal solution. We define a partition of vertices
of G into the following three parts.
• B = {u ∈ V(G) | d(u) ≥ 2k + d}
• IB = {v ∈ V(G) \ B | N(v) ⊆ B}
• R = V(G) \ (B ∪ IB )
We apply the following two reduction rules which are known from [22] to bound IB
(which is an independent set).
Reduction Rule 3.2. If there exists u ∈ IB ∩ V(G − S) such that dG (u) ≥ d, then delete
NG [u] and add a new vertex w adjacent to every vertex in NG (NG (u)) \ {u}. Further,
add 2k + d new vertices W adjacent to w to get the graph G 0 . The resulting instance is
(G 0 , (S ∪ {w}) \ N(u)).
Observe that S 0 = (S ∪ {w}) \ N(u) is a split deletion set of G 0 as V(G 0 − S 0 ) can be
partitioned into the clique C ∩ V(G 0 − S 0 ) and independent set (I ∩ V(G 0 − S 0 )) ∪ W. Further,
as |C| ≤ d − 1 and dG (u) ≥ d, it follows that N(u) ∩ S 6= ∅. As we add at most one vertex
to S and delete at least one vertex from S to get S 0 , we have |S 0 | ≤ |S|.
Lemma 11. Reduction Rule 3.2 is α-safe.
Proof. Consider a solution D 0 of the reduced instance. If w ∈
/ D 0 , the solution lifting
algorithm returns a connected vertex cover D of G of size at most 2k + d − 1 obtained
from Lemma 10. Then, we have CVC((G 0 , S 0 ), k, D 0 ) ≥ 2k + d since w has at least
2k + d neighbours and CVC((G, S), k, D) ≤ 2k + d − 1 implying CVC((G, S), k, D) ≤
10

CVC((G 0 , S 0 ), k, D 0 ). Otherwise, we have w ∈ D 0 and the solution lifting algorithm returns D = (D 0 \ (W ∪ {w})) ∪ N[u] which is a connected vertex cover of G such that
CVC((G, S), k, D) ≤ CVC((G 0 , S 0 ), k, D 0 ) − 1 + |N[u]|. Next, consider an optimum solution
D∗ for the original instance. Clearly, |D∗ | ≤ 2k + d − 1 from Lemma 10. Thus, B ⊆ D∗ .
In particular, NG (u) ⊆ D∗ . Then, (D∗ \ NG [u]) ∪ {w} is a connected vertex cover of
G 0 . Hence, OPT((G 0 , S 0 ), k) ≤ OPT((G, S), k) − |NG (u)| + 1. Combining these bounds,
0 ,S 0 ),k,D 0 )
CVC((G 0 ,S 0 ),k,D 0 )
|N(u)|
we have CVC((G,S),k,D)
as
≤ max CVC((G
OPT((G,S),k) ≤ max
OPT((G 0 ,S 0 ),k) , |N(u)|−1
OPT((G 0 ,S 0 ),k) , α
|N(u)| ≥ d.
Recall that two non-adjacent vertices u and v are called false twins if N(u) = N(v).
Reduction Rule 3.3. If there exists x ∈ IB ∩ V(G − S) such that x has at least 2k + d false
twins in IB ∩ V(G − S), then delete x. The resulting instance is (G − {x}, S \ {x}).

Observe that S 0 = S \ {x} continues to be a split deletion set of G 0 = G − {x} as a result
of applying this rule.
Lemma 12. Reduction Rule 3.3 is 1-safe.

Proof. Consider a solution D 0 of the reduced instance. If |D 0 | ≥ 2k + d, the solution lifting
algorithm returns a connected vertex cover D of G of size at most 2k + d − 1 obtained from
Lemma 10. Then, we have CVC((G 0 , S 0 ), k, D 0 ) ≥ 2k+d and CVC((G, S), k, D) ≤ 2k+d−1
implying CVC((G, S), k, D) ≤ CVC((G 0 , S 0 ), k, D 0 ). Otherwise, it follows that one of the
false twins of x, say y, is excluded from D 0 . Thus, N(y) ⊆ D 0 implying that N(x) ⊆ D 0 .
Then, the solution lifting algorithm returns D = D 0 which is a connected vertex cover of G
such that CVC((G, S), k, D) = CVC((G 0 , S 0 ), k, D 0 ). Next, consider an optimum solution
D∗ for the original instance. Clearly, |D∗ | ≤ 2k + d − 1 from Lemma 10. Thus, either x and
one of its false twins y is excluded from D∗ or two of the false twins of x, say y and z are
excluded from D∗ . In any case, we have another optimal connected vertex cover D∗∗ of G 0
that excludes x. Hence, OPT((G 0 , S 0 ), k) ≤ OPT((G, S), k). Combining these bounds, we
CVC((G 0 ,S 0 ),k,D 0 )
have CVC((G,S),k,D)
OPT((G,S),k) ≤ OPT((G 0 ,S 0 ),k) .
Now, we have the following bound.
Lemma 13. Suppose S is a split deletion set of size k of G and none of the Reduction Rules
3.1, 3.2 and 3.3 is applicable on the instance (G, S). Then, |V(G)| is O(k + (2k + d)d ).
Proof. We will bound B, IB and R separately in order to bound V(G). We know that G
has a connected vertex cover T of size at most 2k + d − 1. As B is the set of vertices of
degree at least 2k + d, B ⊆ T and so |B| ≤ 2k + d − 1. Every vertex in R has degree at
most 2k + d − 1. Therefore, as T ∩ R is a vertex cover of G[R], |E(G[R])| is O((2k + d − 1)2 ).
Also, by the definition of IB , every vertex in R has a neighbour in R and hence there are no
isolated vertices in G[R]. Thus, |R| is O((2k + d − 1)2 ). Finally, we bound the size of IB .
As Reduction Rule 3.2 is not applicable, every vertex in IB ∩ V(G − S) has degree at
most d − 1. For every set B 0 ⊆ B of size at most d − 1, there are at most 2k + d vertices in
IB ∩ V(G − S) which have B 0 as their neighbourhood. Otherwise, Reduction Rule 3.3 would

have been applied. Hence, there are at most (2k + d) · 2k+(d−1)
vertices in IB ∩ V(G − S).
d−1
Finally, as none of the reduction rules increases the size of the split deletion set S, we have
|IB ∩ S| ≤ k. Therefore, |IB | is O(k + (2k + d)d ).
This leads to a PSAKS for the problem as claimed.
Theorem 14. Connected Vertex Cover parameterized by the size k of a split deletion
d 2α−1
e
α−1 ) vertices.
set admits a time efficient PSAKS with O(k + (2k + d 2α−1
α−1 e)
11

Proof. Given α > 1, we choose d = d 2α−1
α−1 e and apply the reduction rules as long as they
are applicable. Then, from Lemma 13, |V(G)| is O(k + (2k + d)d ).
We note that this kernel is one of the few lossy kernels for a problem with respect to a
structural parameter.

4

Connected Vertex Cover parameterized by Clique Cover

In this section, we first show that some of the ideas from the previous section can be used
to give a lossy kernel for Connected Vertex Cover when parameterized by the size of
the clique cover. A clique cover of a graph is a partition of its vertex set such that each part
induces a clique. We assume that we are given a partition of the vertex set of the input
graph into cliques. For this parameterization, the corresponding parameterized minimization
problem is defined in a similar way as defined for split deletion set.
Theorem 15. Connected Vertex Cover parameterized by the size k of a clique cover
admits a time efficient PSAKS with O(kd 2α−1
α−1 e) vertices.
Proof. Without loss of generality, we assume that the graph has no isolated vertices as no
minimum connected vertex cover contains them. Given α > 0, let d = d 2α−1
α−1 e. Let C denote
the set of k cliques in the clique cover of G. We bound the number of vertices in G by
applying Reduction Rule 3.1 on each C ∈ C. From Lemma 8, each application of this rule
is α-safe. When this rule is no longer applicable, it follows that G has at most k(d − 1)
vertices. This leads to the claimed result.
Now, we modify a reduction known from [20] used in the hardness of Feedback Vertex
Set with respect to the size of a clique cover to show that Connected Vertex Cover is
W[1]-hard under the same parameterization. This makes this one of the few problems that
are unlikely to be in FPT but have a lossy kernel.
Theorem 16. Connected Vertex Cover parameterized by the size of a clique cover is
W[1]-hard.
Proof. We reduce the well known W[1]-hard problem, Independent Set parameterized
by solution size, to our problem. A non-separating independent set of a graph G is an
independent set I such that V(G) \ I is a connected vertex cover of G. Let (G, k) be an
instance of Independent Set. We construct a graph G 0 on the vertex set {(v, i) | v ∈
V(G), i ∈ [k]} ∪ {x, y}. We add an edge between (v, i) and (u, j) if and only if i = j or u = v
or v ∈ NG (u). Further, for every w ∈ V(G 0 ) \ {x}, we add the edge {w, x} to G 0 . Note that
G 0 has a clique cover of size k + 1 as for all j ∈ [k], G 0 [{(v, j) | v ∈ V(G)}] is a complete graph
and {x, y} is a clique. We claim that G has an independent set of size k if and only if G 0 has
a non-separating independent set of size k + 1.
Suppose S = {v1 , . . . , vk } is an independent set of size k in G. Define the set S 0 ⊆ V(G 0 )
as {(v1 , 1), (v2 , 2), . . . , (vk , k), y}. Consider any two vertices (vi , i) and (vj , j) in S 0 such that
i 6= j. As for each distinct i, j ∈ [k], we have {vi , vj } ∈
/ E(G), it follows that there is no edge
between (vi , i) and (vj , j). Also, by the construction of G 0 , y is not adjacent to any vertex in
G 0 other than x. Therefore, S 0 is an independent set of size k + 1 in G 0 . As x is adjacent to
every vertex in G 0 − S 0 , it follows that the deletion of S 0 does not disconnect G 0 . In other
words, S 0 is a non-separating independent set of G 0 .
Conversely, suppose S 0 is a non-separating independent set of size k + 1 in G 0 . Clearly,
different vertices of S 0 have to come from different cliques of the clique cover of G 0 . We may
assume that y ∈ S 0 as if x ∈ S 0 , then (S 0 \ {x}) ∪ {y} is another non-separating independent
12

set of size k + 1. This is due to the facts that y is not adjacent to any vertex other than x
and x is a universal vertex in G 0 . Define the set S ⊆ V(G) as {v | (v, j) ∈ S 0 \ {y}}. Consider
any two vertices (v, i) and (u, j) in S 0 . Then, u 6= v, i 6= j and v ∈
/ NG (u). Therefore, S is
an independent set in G of size k.
From Theorem 16, it follows that Connected Vertex Cover parameterized by k + q
is W[1]-hard where k is the size of a set S whose deletion results in a graph for which there
exists a clique cover of size q. However, the problem is in XP as the algorithm in Theorem
3 can be easily generalized to solve Connected Vertex Cover in O∗ (2k nq ) time where
n is the number of vertices in the input graph. Further, by an easy adaptation of Theorem
15, the problem admits a PSAKS leading to the following result.
Theorem 17. Given a graph G on n vertices, a set S ⊆ V(G) such that |S| ≤ k and G − S
has a clique cover Q of size q and a positive integer `, there is an algorithm that determines
whether G has a connected vertex cover of size at most ` in O∗ (2k nq ) time. Further, the
problem admits a time efficient PSAKS with O(k + qd 2α−1
α−1 e) vertices.
Proof. Without loss of generality, we assume that the graph has no isolated vertices as no
minimum connected vertex cover contains them. We also assume that the set S and the
clique cover Q of G − S are part of the input. First, let us describe the XP algorithm. Let
X∗ be a connected vertex cover of G of size at most `. S
As at least |Q| − 1 vertices from each
∗
∗
clique Q ∈ QSare contained in X , we guess Y = X ∩ ( Q∈Q Q). Then, we guess Z = X∗ ∩ S
such that (( Q∈Q Q) \ Y) ∪ (S \ Z) is an independent set. The number of choices for (Y, Z)
is O∗ (nq 2k ). If G[Y ∪ Z] is not connected or has more than ` vertices, we skip to the next
choice of (Y, Z). Otherwise, Y ∪ Z is the required solution. If none of the choices leads to a
solution, we declare that G has no connected vertex cover of size at most `. The overall
running time of the algorithm is thus O∗ (2k nq ).
Now, we describe an α-approximate kernel for each α > 1. Given α > 0, let d = d 2α−1
α−1 e.
We bound the number of vertices in G by applying Reduction Rule 3.1 on each Q ∈ Q. From
Lemma 8, each application of this rule is α-safe. When this rule is no longer applicable, it
follows that G has at most k + q(d − 1) vertices. This leads to the claimed result.

5

Connected Vertex Cover parameterized by Cluster Deletion Set

In Section 3.1, we gave an O∗ (2k ) time algorithm for Connected Vertex Cover parameterized by the size k of a clique deletion set. Here, we generalize this algorithm to solve
Connected Vertex Cover in O∗ (4k ) time where k is the size of a cluster deletion set.
Observe that this is a parameter smaller than the clique deletion set size. Further, we also
describe a lossy kernel with respect to this parameterization. A classical polynomial kernel
is unlikely as the size of a minimum cluster deletion set is at most the size of a minimum
connected vertex cover. This is due to the fact that deleting a connected vertex cover from
a graph results in a cluster graph in which every component is an isolated vertex.

5.1

An FPT Algorithm

Consider an instance (G, S, `) of Connected Vertex Cover where S is a cluster deletion
set. Let H denote the cluster graph G − S. Let X∗ be a connected vertex cover of size at
most ` (if one exists) that we are looking for. First, we guess the subset S 0 of S such that
S 0 = S ∩ X∗ . If S \ S 0 is not an independent set, we skip to the next choice of S 0 . Define the
set F as N(S \ S 0 ) ∩ V(H). Initialize the set X to be S 0 . In the latter steps of our algorithm,
13

we will extend X to a connected vertex cover of G. We also update ` to ` − |S 0 | and delete
S \ S 0 from G. We will now describe a sequence of reduction and branching rules to be
applied. The rules are applied in the order stated and a rule is applied as long as it is
applicable on the instance. That is, a rule is applied only when none of the preceding rules
can be applied.
Let I denote the set of isolated vertices of H and Q denote the set of vertex sets of
components of H − I. That is, I is an independent set and each element of Q is a clique in
H. These sets are updated accordingly as and when the rules are applied. First, we apply
the following preprocessing rule.
Preprocessing Rule 5.1. If there is a clique Q ∈ Q with N(Q) ∩ X = ∅ or a vertex
v ∈ F ∩ I such that N(v) ∩ X = ∅, then skip to the next choice of S 0 .
The correctness of the first part of the rule follows from the fact that at least |Q| − 1
vertices from Q has to be in any vertex cover and any set of such vertices along with X
cannot be extended to a connected subgraph by only adding vertices from V(H). The
correctness of the second part follows from the facts that F is forced into the solution and
G[X ∪ {v}] cannot be extended to a connected subgraph by only adding vertices from V(H).
Let F be partitioned into sets Y and Z defined as follows.
• Y = {v ∈ F | N(v) ∩ X 6= ∅}, the set of vertices of F that have a neighbour in X.
• Z = F \ Y, the set of vertices of F that have no neighbour in X.
These sets are updated over the execution of the algorithm according to the current
partial solution X. In particular, at any point of time, Z is the set of vertices in F that are
not adjacent to any vertex in the current partial solution X. Our first reduction rule is as
follows.
Reduction Rule 5.1. Add Y ∪ Z to X, update ` to ` − |Z ∪ Y| and delete Y from H.
This rule is justified by the fact that X∗ must contain F. Due to Preprocessing Rule
5.1, every vertex v ∈ Z is in some clique Q in Q. When Reduction Rule 5.1 is no longer
applicable, we have V(H) ∩ F = Z. For each v ∈ Z, let Qv denote the clique in Q containing
v. The next rule is the following.
Reduction Rule 5.2. If there is a vertex v ∈ Z with |Qv ∩ Z| = |Qv | − 1, then add Qv \ Z
to X, update ` to ` − 1 and delete Qv from H and Z.
The correctness of this rule follows from the fact that there is exactly one vertex u in
Qv ∩ N(X \ Z). This vertex is forced into the solution since Qv \ {u} ⊆ X and Qv \ {u} has
no neighbours in X \ (Qv \ {u}). Now, for any clique Q ∈ Q, there are at least two vertices
that are not in Z. For a vertex v ∈ V(H), let C(v) = {A ∈ G[X] | A is a component of G[X]
and NG (v) ∩ V(A) 6= ∅}. The next rule is the following.
Reduction Rule 5.3. If there is a clique Q in Q that has two vertices u, v ∈
/ Z with
C(u) ⊆ C(v), then update X to X ∪ (Q \ {u}) and reduce ` by the number of vertices added to
X. Delete Q from H and Z.
If there exists an optimal connected vertex cover X that does not contain v, then u ∈ X
and X 0 = (X \ {u}) ∪ {v} is also a connected vertex cover of G. This justifies the correctness
of the rule. The next rule is a branching rule that is applied when H has a triangle or a
larger clique Q with vertices not in Z. Further, for each v ∈ Q \ Z, |C(v)| ≥ 1 and for every
u, v ∈ Q \ Z, C(u) 6⊆ C(v).
14

Branching Rule 5.1. If there is a triangle {u, v, w} in H with u, v, w ∈
/ Z, then branch
into adding u, v or u, w or w, v into X. In each of the branches update ` to ` − 2.
The branches in this rule are clearly exhaustive as any vertex cover contains at least
two vertices from a triangle. The reason for handling such special triangles will be apparent
during the application of subsequent rules. When none of the rules described so far is
applicable, every clique Q ∈ Q has exactly 2 vertices not in Z. In particular, if Q ∩ Z = ∅,
then |Q| = 2.
/ Z in H and |C(u)| = 1 and
Reduction Rule 5.4. If there is an edge {u, v} with u, v ∈
|C(v)| ≥ 1, then update X to X ∪ (Q \ {u}) and reduce ` by the number of vertices added to X
where Q is the clique in Q that contains u and v. Delete Q \ {u} from H and Z. Add u to I.
If there exists an optimal connected vertex cover X that does not contain v, then u ∈ X
and X 0 = (X \ {u}) ∪ {v} is also a vertex cover of G. Further, G[X 0 ] is connected as the only
vertex in Q ∩ X that is adjacent to a vertex in X \ {u} is u and |C(u)| = 1. Note that we
crucially use the property that Q has exactly two vertices adjacent to a vertex in X \ {u, v}
which is achieved by the application of Branching Rule 5.1. This justifies the correctness
of the rule. The next rule is a branching rule that is applied until X is a vertex cover (not
necessarily connected) of G.
Branching Rule 5.2. If there is an edge {u, v} in H, then in one branch we add u into
X and in other branch we add v into X. In both branches, update ` to ` − 1 and delete the
vertex added to X from H.
When this rule is applied on an edge {u, v}, we have |C(x)|, |C(y)| ≥ 2 and {x, y} ∩ Z = ∅.
The branches are exhaustive as any vertex cover contains x or y. At this point, when none
of the described rules (reduction and branching) is applicable, we have a vertex cover X of
G. That is, V(H) is an independent set. However, X may not necessarily induce a connected
subgraph. Let G 0 be the graph obtained from G[V(H) ∪ X] by contracting each component
b where X
b is the
of G[X] into a single vertex. G 0 is bipartite and has a bipartition (V(H), X)

set of vertices of G 0 corresponding to the set of components of G[X]. The problem is now to
b
b which can be solved in O∗ (2|X|
find a Steiner tree of G 0 that contains X
) time using Lemma
1. This completes the description of the algorithm leading to the following result.
Theorem 18. Given a graph G, a cluster deletion set S and a positive integer `, there is
an algorithm that determines whether G has a connected vertex cover of size at most ` in
O∗ (4|S| ) time.

Proof. Given an instance (G, S, `), we first guess a subset S 0 of S that is contained in the
solution. Then, we apply the reduction rules and branching rules in the order stated. We
reiterate that each rule is applied as long as it is applicable. Also, a rule is applied only
when none of the earlier rules is applicable. Let X be the partial solution that we are trying
to extend to a connected vertex cover. Initially X is S 0 . The measure that we use to bound
the running time is the number #comp(G[X]) of components of G[X] which is at most |S 0 |.
On applying either of the branching rules, it is clear that #comp(G[X]) drops in all the
branches by at least one. We will now show that the reductions rules do not increase the
measure. When Reduction Rule 5.2 is applied, Qv has a neighbour in X due to Preprocessing
Rule 5.1. Similarly, when Reduction Rule 5.3 or 5.4 is applied, Q \ {u} has a neighbour in X.
Hence, these three rules do not increase #comp(G[X]). Now consider Reduction Rule 5.1.
Adding Y to X do not increase #comp(G[X]) while adding Z to X will definitely increase it.
However, if Z is non-empty, then in subsequent rules, some neighbour of Z which is also
adjacent to some vertex in (current) X is added to the solution. Consider a vertex z ∈ Z on
15

which Reduction Rule 5.2 is applicable. Then, we add a neighbour z 0 of z that is adjacent
to X. Therefore, the measure does not increase. In fact, the measure first increases by 1
(due to addition of z to X) and then decreases by at least 1 (due to addition of z 0 to X).
Suppose Reduction Rule 5.2 is not applicable on a vertex z ∈ Z. Then, Qz has at least 2
vertices not in Z. If Reduction Rule 5.3 is applicable on Qz , then adding z into X does not
increase the measure. Let us consider the case when Reduction Rule 5.3 is not applicable
on Qz . Then, either Branching Rule 5.1 or Reduction Rule 5.4 or Branching Rule 5.2 is
applicable to vertices of Qz . In any case, as we add a neighbour of z that is adjacent to X,
the measure does not increase.
When none of the reduction and branching rules is applicable, we have a set X that is
a vertex cover of G. That is, at each leaf of the recursion tree, we have a vertex cover X
of G that needs to be connected by adding a minimum number of vertices from V(H). We
b as described earlier. Here, X
b
construct the bipartite graph G 0 with bipartition (V(H), X)
is the set of vertices of G 0 corresponding to the set of components of G[X]. Observe that
#comp(G[X]) is at most |S 0 |. Then, the time taken at each leaf of the recursion tree is upper
b
b which is O∗ (2|X|
bounded by the time taken to find a Steiner tree of G 0 that contains X
) from
0
Lemma 1. Let |S | = i. If a leaf is at depth j where j ≤ i, it follows that the #comp(G[X])
is at most i − j. Then, the Steiner tree algorithm at this leaf runs in O∗ (2i−j ) time.
Let T (j) denote the number of leaves of the search tree at depth j. It is easy to verify that
the search tree is a ternary tree as there are at most three branches in any rule. Thus, the
number of leaves at depth j is at most 3j . Therefore, the running time (ignoring polynomial
factors) of the algorithm is upper bounded by the following value. Let k denote |S|.
k  X
i
X
k
i=0

i

j=0

j i−j

32



k  
k
X
X
k i
k − 1 i−1
≤
i
3 =3
k
3
= 3k · 4k−1
i
i−1
i=0

i=1

Thus, the running time of the algorithm is O∗ (4k ).
A degree-i modulator is a set of vertices whose deletion results in a graph with maximum
degree at most i. As a degree-1 modulator is also a cluster deletion set, it follows that
Connected Vertex Cover can be solved in O∗ (4|S| ) time when given a degree-1 modulator
S as part of input. However, observe that this algorithm runs in O∗ (3k ) time as branching
rule 5.2 is never applicable (and so the search tree is a binary tree). Thus, we have the
following result.
Theorem 19. Given a graph G, a degree-1 modulator S and a positive integer `, there is
an algorithm that determines whether G has a connected vertex cover of size at most ` in
O∗ (3|S| ) time.
It is well known that the treewidth (tw) of a graph is not larger than the size of its
minimum vertex cover, and hence of its minimum connected vertex cover. Therefore, a naive
dynamic programming routine over a tree decomposition of width tw solves Connected
Vertex Cover in O∗ (2tw log tw ) time [24]. The running time bound has been improved
to O∗ (2O(tw) ) using algebraic techniques [2]. If the maximum degree of a graph G is upper
bounded by 2, then every component of G is an induced path or an induced cycle. Hence,
the treewidth of G is at most 2. Therefore, if G has a degree-2 modulator of size at most k,
then the treewidth of G is at most k + 2. This shows that Connected Vertex Cover is
FPT when parameterized by the size of a degree-2 modulator. As Connected Vertex
Cover is NP-hard on graphs with maximum degree at most 4, it is clear that Connected
Vertex Cover when parameterized by the size of a degree-4 modulator is para-NP-hard
(NP-hard for fixed values of parameter). This observation doesn’t immediately carry over
16

when parameterized by the size of a degree-3 modulator as Connected Vertex Cover
is polynomial time solvable in sub-cubic graphs [26]. Nevertheless, Connected Vertex
Cover is para-NP-hard even when parameterized by the size of a degree-3 modulator. This
is due to the fact that Vertex Cover in sub-cubic graphs is NP-complete [1, 15] and
Vertex Cover reduces to Connected Vertex Cover by just adding a universal vertex
(which is a degree-3 modulator) to the graph.
Theorem 20. Connected Vertex Cover parameterized by the size of a degree-i modulator is FPT when i ≤ 2 and para-NP-hard for i ≥ 3.
It is intriguing that though Connected Vertex Cover is polynomial-time solvable
on sub-cubic graphs, it is NP-hard on graphs that are just one vertex away from being a
sub-cubic graph. Note that the related Feedback Vertex Set problem is also solvable
in polynomial-time on sub-cubic graphs, but it is a major open problem whether it is
polynomial-time solvable on graphs that have a degree-3 modulator of size 1.

5.2

A Lossy Kernel

In this section, we give a PSAKS for Connected Vertex Cover parameterized by the
size of a cluster deletion set. We formally define the parameterized minimization problem
as follows.


−∞ if |S| > k or some component of G − S is not a clique
CVC((G, S), k, T ) = ∞
if T is not a connected vertex cover


|T |
otherwise
We now prove the following main result of this section.
Theorem 21. Connected Vertex Cover parameterized by the size k of a cluster deletion
α
d α−1
e
k
α
set admits a time efficient PSAKS with O(k2 + d 2α−1
) vertices.
α−1 e · α−1 + d α−1 e · k
Proof. Let G be a connected graph and S denote its cluster deletion set of size at most k.
Given α > 1, define  = α − 1. Let H denote the cluster graph G − S and F0 be the set of
isolated vertices in H. Let F1 = V(H) \ F0 and t denote the number of components in G[F1 ].
α
Let C1 , · · · , Ct denote the components of G[F1 ]. Let d1 = d 2α−1
α−1 e and d2 = d α−1 e. Define the
set T as follows. We first initialize T to S. Then, for each i ∈ [t], we add a set Xi of |V(Ci )|−1
vertices of Ci such that NG (Xi )∩S 6= ∅ to T . Such a set always exists as G is connected. Now,
t
P
T is a vertex cover of G and |T | = |S|+ (|V(Ci )|−1). Further, #comp(G[T ]) = #comp(G[S]).
i=1

If G[T ] is not connected, then we add at most |S| − 1 vertices from V(G) \ T to T so that
G[T ] becomes connected. Once again, such a set exists as G is connected. Thus, we have
t
t
P
P
|T | < 2k + (|V(Ci )| − 1). We know that OPT ((G, S), k) ≥ (|V(Ci )| − 1) as each V(Ci )
i=1

i=1

is a clique and any vertex cover excludes at most one vertex from any clique. Therefore,
|T | < 2k + OPT ((G, S), k). If t ≥ 2k
 , then the reduction algorithm outputs a constant size
0
0
instance (G , S ). Since OPT ((G, S), k) ≥ t, we have k ≤ 2 OPT ((G, S), k) and it follows that
|T | is at most (1 + )OPT ((G, S), k). Equivalently, CVC((G, S), k, T ) ≤ (1 + )OPT ((G, S), k).
The solution lifting algorithm simply returns T which is obtained in polynomial time.
On the other hand, suppose t < 2k
 . For each i ∈ [t], we apply Reduction Rule 3.1 with
d = d1 to bound the number of vertices in Ci by d1 . From Lemma 8, we know that Reduction
Rule 3.1 is α-safe. When this rule is no longer applicable, we have at most d1 2k
 vertices in F1 .
Now, it remains to bound the number of vertices in F0 . Observe that any optimal connected
vertex cover must contain any vertex x ∈ S with |NG (x) ∩ F0 | ≥ 2k. This is because, if some
17

optimal connected vertex cover T ∗ excludes x, then |T ∗ | ≥ 2k +
T is a connected vertex cover with |T | < 2k +

t
P

t
P

(|V(Ci )| − 1). However,

i=1

(|V(Ci )| − 1) leading to a contradiction.

i=1

Let S1 = {x ∈ S | |NG (x) ∩ F0 | ≥ 2k}. We first partition F0 into A0 = {v ∈ F0 | NG (v) ⊆ S1 }
and B0 = F0 \ A0 . Then, we apply Reduction Rule 3.2 to vertices in A0 with d = d2 and
Reduction Rule 3.3 to vertices in A0 with d = 0. Reduction Rule 3.2 is α-safe and Reduction
Rule 3.3 is 1-safe from Lemmas 11 and 12.
Suppose none of the described rules is applicable on the instance (G, S). We will show
that |V(G)| = O(k2 + d2 · kd2 + d1 · k). The set V(G) is partitioned into sets S, F1 , A0 and
B0 . As G is connected, G has no isolated vertex. As Reduction Rule 3.1 is not applicable,
each component in G[F1 ] has at most d1 vertices. Thus, |V(F1 )| ≤ 2k
 · d1 . For any vertex
v ∈ F0 , there is a vertex x ∈ S such that {x, v} ∈ E(G). Since the reduction rules described
are not applicable,
 every vertex x ∈ A0 has at most d2 − 1 neighbors in S1 . Further, for
every X ∈ ≤dS21−1 , there are at most 2k vertices from A0 such that each of those 2k vertices
dP
2 −1

k
d2 as |S | ≤ k.
has X as its neighborhood in G. Therefore, |A0 | ≤ 2k ·
1
i ≤ 2(d2 − 1)k
i=1

As G is connected, each vertex in B0 has a neighbour in S \ S1 . Since, the degree of any
vertex in S \ S1 is at most 2k, it follows that |B0 | ≤ 2k2 . Thus, |V(G)| = |S| + |F1 | + |A0 | + |B0 |
α
d α−1
e
2α−1
k
α
d2
2
2
is at most k + 2k
).
 · d1 + 2(d2 − 1)k + 2k which is O(k + d α−1 e · α−1 + d α−1 e · k
As the deletion of a degree-1 modulator results in a graph in which every component
has at most 2 vertices, we have the following result as a consequence of Theorem 21.
Corollary 22. Connected Vertex Cover parameterized by the size k of a degree-1
α
k
α
modulator admits a time efficient PSAKS with O(k2 + α−1
+ d α−1
e · kd α−1 e ) vertices.

6

Connected Vertex Cover parameterized by Chordal Deletion Set

In this section, we show that Connected Vertex Cover parameterized by the size of a
chordal deletion set is FPT. It is well known that the treewidth (tw) of a graph is at most
one more than the size of a minimum feedback vertex set (a set of vertices whose removal
results in a forest). This immediately implies that Connected Vertex Cover is FPT
when parameterized by the size of a feedback vertex set. Recall that a chordal graph is a
graph in which every induced cycle is a triangle. As forests, split graphs and cluster graphs
are chordal, the minimum chordal deletion set size is at most a minimum feedback vertex
set, a minimum split deletion set size and a minimum cluster deletion set.
Theorem 23. Given a graph G, a chordal deletion set S and a positive integer `, there is
an algorithm that determines whether G has a connected vertex cover of size at most ` in
O∗ (2|S| log |S| ) time.
Proof. Let G be a connected graph on n vertices and S denote its chordal deletion set. As
G − S is a chordal graph, a tree decomposition of G − S of optimum width in which every
bag is a clique can be obtained in linear time [16]. From this tree decomposition of G − S,
a tree decomposition T = (T, {Xt }t∈V(T ) ) of G can be obtained by adding S to every bag.
We will show that the algorithm for Connected Vertex Cover on bounded treewidth
graphs [24] runs in O∗ (2O(|S| log |S|) ) time. The algorithm employs a dynamic programming
routine over the tree decomposition T . As this approach is largely standard, we only present
an outline of the algorithm here.
18

For a node t of T , let Tt denote the subtree of T rooted at t ∈ V(T ) and Vt denote
the union of all the bags of Tt . Let Gt denote the subgraph of G induced by Vt . For
t ∈ V(T ), X ⊆ Xt and a partition P = {P1 , · · · , Pq } into at most |X| parts, let Γ [t, X, P]
denote a minimum vertex cover Z of Gt with Xt ∩ Z = X and Gt [Z] has exactly q connected
components C1 , · · · , Cq where Pi = V(Ci ) ∩ Xt for each i ∈ {1, · · · , q}. Further, if X is empty,
Z is required to be connected in Gi . Then, Γ [t, ∅, {∅}] is a minimum connected vertex cover
of G. Observe that the total number of (valid) states per node is |S|O(|S|) n. This is due to
the fact that for each vertex t ∈ V(T ), G[Xt ] has a clique deletion set of size |S|. Further,
each entry can be computed in |S|O(|S|) nO(1) time. This leads to the claimed result.
We remark that the lossy kernelization status of this problem remains open even when
the chordal deletion set is a feedback vertex set.

7

Concluding Remarks

We have given lossy kernels and studied the parameterized complexity statuses of Connected Vertex Cover parameterized by split deletion set size, clique cover number
and cluster deletion set size. Our FPT running times (for Connected Vertex Cover
parameterized by split deletion set and cluster deletion set) have slight gaps between upper
bounds and lower bounds (based on well-known conjectures), and tightening the bounds
is an interesting open problem. A more general direction is to explore the parameterized
and (lossy) kernelization complexity of Connected Vertex Cover in the parameter
ecology program. Figure 1 gives a partial landscape of the (parameterized) complexity
of Connected Vertex Cover under various structural parameters. Designing (lossy)
kernels (or proving impossibility results) for those whose status is unknown is an interesting
future direction.

References
[1] P. Alimonti and V. Kann. Some APX-Completeness Results for Cubic Graphs. Theoretical Computer Science, 237(1-2):123–134, 2000.
[2] H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic Single
Exponential Time Algorithms for Connectivity Problems parameterized by Treewidth.
Information and Computation, 243:86–111, 2015.
[3] H. L. Bodlaender and B. M. P. Jansen. Vertex Cover Kernelization Revisited: Upper and
Lower Bounds for a Refined Parameter. Theory of Computing Systems, 63(2):263–299,
2013.
[4] H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernelization Lower Bounds by
Cross-Composition. SIAM Journal of Discrete Mathematics, 28(1):277–305, 2014.
[5] A. Boral, M. Cygan, T. Kociumaka, and M. Pilipczuk. A Fast Branching Algorithm
for Cluster Vertex Deletion. Theory of Computing Systems, 58(2):357–376, 2016.
[6] J. Chen, I. A. Kanj, and W. Jia. Vertex Cover: Further Observations and Further
Improvements. Journal of Algorithms, 41(2):280–301, 2001.
[7] M. Cygan. Deterministic Parameterized Connected Vertex Cover. In Proceedings of the
13th Scandinavian Workshop on Algorithm Theory (SWAT), pages 95–106, 2012.

19

[8] M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi,
S. Saurabh, and M. Wahlstrm. On Problems as Hard as CNF-SAT. ACM Transactions
on Algorithms, 12(3):41:1–41:24, 2016.
[9] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
[10] M. Cygan and M. Pilipczuk. Split Vertex Deletion meets Vertex Cover: New FixedParameter and Exact Exponential-Time Algorithms. Information Processing Letters,
113(5-6):179–182, 2013.
[11] R. Diestel. Graph Theory. Springer, Graduate Text in Mathematics, 2012.
[12] M. Dom, D. Lokshatanov, and S. Saurabh. Kernelization Lower Bounds through Colors
and IDs. ACM Transaction on Algorithms, 11(2):13:1–13:20, 2014.
[13] B. Escoffier, L. Gourvs, and J. Monno. Complexity and Approximation Results for
the Connected Vertex Cover problem in Graphs and Hypergraphs. Journal of Discrete
Algorithms, 8(1):36–49, 2010.
[14] F. Fomin and D. Kratsch. Exact Exponential Algorithms. Springer-Verlag, 2010.
[15] M. R. Garey and D. S. Johnson. Computer and Intractability: A Guide to the Theory
of NP-Completeness. W. H. Freeman & Co., 1979.
[16] M. C. Golumbic. Algorithmic Graph Theory for Perfect Graphs. Springer, 2004.
[17] B. M. P. Jansen. The Power of Data Reduction: Kernels for Fundamental Graph
Problems. PhD thesis, Utrecht University, The Netherlands, 2013.
[18] B. M. P. Jansen, M. R. Fellows, and F. A. Rosamond. Towards fully Multivariate
Algorithmics: Parameter Ecology and the Deconstruction of Computational Complexity.
European Journal of Combinatorics, 34(3):541–566, 2013.
[19] B. M. P. Jansen and S. Kratsch. Data Reduction for Coloring Problems. Information
and Computation, 231:70–88, 2013.
[20] B. M. P. Jansen, V. Raman, and M. Vatshelle. Parameter Ecology for Feedback Vertex
Set. Tsinghua Science and Technology, 19(4):387–409, 2014.
[21] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh.
Faster Parameterized Algorithms Using Linear Programming. ACM Transactions on
Algorithms, 11(2):15:1–15:31, 2014.
[22] D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh. Lossy Kernelization.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
(STOC), pages 224–237, 2017.
[23] D. Marx. Chordal Deletion is Fixed-Parameter Tractable. Algorithmica, 57(4):747–768,
2010.
[24] H. Moser. Exact Algorithms for Generalizations of Vertex Cover. Master’s thesis,
Institut für Informatik, Friedrich-Schiller-Universität, 2005.
[25] J. Nederlof. Fast Polynomial-Space Algorithms Using Inclusion-Exclusion. Algorithmica,
65(4):868–884, 2013.
20

[26] S. Ueno, Y. Kajitani, and S. Gotoh. On the Nonseparating Independent Set problem
and Feedback Set problem for Graphs with no Vertex Degree exceeding Three. Discrete
Mathematics, 72:355–360, 1988.
[27] B. Y. Wu. A Measure and Conquer based Approach for the Parameterized Bounded
Degree-one Vertex Deletion. In Proceedings of the 21st International Computing and
Combinatorics Conference (COCOON), pages 469–480, 2015.

21

