Connected Vertex Cover
for (sP1 + P5 )-Free Graphs⋆
Matthew Johnson, Giacomo Paesani, and Daniël Paulusma

arXiv:1712.08362v2 [] 28 Feb 2018

Department of Computer Science, Durham University, UK
{matthew.johnson2,giacomo.paesani,daniel.paulusma}@durham.ac.uk

Abstract. The Connected Vertex Cover problem is to decide if a graph
G has a vertex cover of size at most k that induces a connected subgraph
of G. This is a well-studied problem, known to be NP-complete for restricted
graph classes, and, in particular, for H-free graphs if H is not a linear forest (a
graph is H-free if it does not contain H as an induced subgraph). It is easy to
see that Connected Vertex Cover is polynomial-time solvable for P4 -free
graphs. We continue the search for tractable graph classes: we prove that it is
also polynomial-time solvable for (sP1 +P5 )-free graphs for every integer s ≥ 0.

1

Introduction

A set S of vertices in a graph G form a vertex cover of G if every edge of G is incident
with a vertex of S. The set S is an an independent set if no two vertices in S are
adjacent. These definitions lead to two classical graph problems, which are both NPcomplete: the Vertex Cover problem is to decide if a given graph G has a vertex
cover of size at most k for a given integer k; the Independent Set problem is to
decide if a given graph G has an independent set of size at least ℓ for a given integer ℓ.
A set S of at least k vertices of a graph G on n vertices is a vertex cover if and
only if VG \ S is an independent set (of size at most n − k). Hence Vertex Cover
and Independent Set are polynomially equivalent. A vertex cover of a graph G is
connected if it induces a connected subgraph of G. In our paper, we focus on the
corresponding decision problem.
Connected Vertex Cover
Instance: a graph G and an integer k.
Question: does G have a connected vertex cover S with |S| ≤ k?
In 1977, Garey and Johnson [10] proved that Connected Vertex Cover is NPcomplete for planar graphs of maximum degree 4. More recently, Priyadarsini and
Hemalatha [22] and Fernau and Manlove [9] strengthened this result to 2-connected
planar graphs of maximum degree 4 and planar bipartite graphs of maximum degree 4,
respectively. Wanatabe, Kajita, and Onaga [26] proved that Connected Vertex
Cover is NP-complete even for 3-connected graphs. Very recently, Munaro [20] proved
the same for line graphs of planar cubic bipartite graphs and for planar bipartite graphs
of arbitrarily large girth, and Li, Yang, and Wang [16] showed NP-completeness for
4-regular graphs.
We now turn to tractable cases. Ueno, Kajitani, and Gotoh [25] proved that Connected Vertex Cover is polynomial-time solvable for graphs of maximum degree
at most 3. Escoffier, Gourvès, and Monnot [8] proved the same result for chordal
graphs. As Vertex Cover is also polynomial-time solvable for chordal graphs [11],
⋆

This work was supported by The Leverhulme Trust (Grant RPG-2016-258).

the authors of [8] proposed a general study on the complexity of Connected Vertex
Cover on graph classes for which Vertex Cover is polynomial-time solvable. This
leads us to the research question of our paper:
For which classes of graphs do the complexities of Vertex Cover and Connected
Vertex Cover coincide?
Chiarelli, Hartinger, Johnson, Milanic, and Paulusma [7] studied this question by
considering classes of graphs characterized by a single forbidden induced subgraph H.
Such graphs are called H-free. They observed that the results of Munaro [20] imply
that Connected Vertex Cover is NP-complete for H-free graphs if H contains a
cycle or a claw. Using Poljak’s construction [21], Vertex Cover is readily seen to be
NP-complete for graphs of arbitrarily large girth and thus for H-free graphs whenever
H contains a cycle. When H is the claw, Vertex Cover becomes polynomial-time
solvable for H-free graphs [18,24]. Hence, there is at least one graph H such that
Connected Vertex Cover and Vertex Cover have different complexities when
restricted to H-free graphs (assuming P 6= NP).
So the complexity of Connected Vertex Cover is known for H-free graphs
unless H is a linear forest (the disjoint union of one or more paths). Even the case where
H is a single path on r vertices (denoted Pr ) is settled neither for Vertex Cover
nor for Connected Vertex Cover; it is not known if there exists an integer r
such that Vertex Cover or Connected Vertex Cover is NP-complete for Pr free graphs. Lokshtanov, Vatshelle, and Villanger [17] proved that Independent Set,
and thus Vertex Cover, is polynomial-time solvable for P5 -free graphs. Recently,
Grzesik, Klimošová, Pilipczuk, and Pilipczuk [12] extended this to P6 -free graphs.
We also note that if Vertex Cover is polynomial-time solvable on H-free graphs
for some graph H, then it is polynomial-time solvable on (P1 + H)-free graphs. This
follows from the observation (see, e.g., [19]) that to solve the complementary problem
of Independent Set on a (P1 + H)-free graph one solves the problem on each H-free
graph obtained by removing a vertex and all its neighbours.
Theorem 1 ([12]). For every s ≥ 0, Vertex Cover can be solved in polynomial
time for (sP1 + P6 )-free graphs.
By using the concept of the price of connectivity [4,6,14], Chiarelli et al. [7] proved that
Connected Vertex Cover is polynomial-time solvable for sP2 -free graphs for any
integer s ≥ 1. For Vertex Cover this follows by combining two classical results [3,23]
(as is well-known). No other complexity results are known for Connected Vertex
Cover for H-free graphs if H is a linear forest.
Our Contribution. We continue the study of [7,8] and prove the following result,
which includes polynomial-time solvability for P5 -free graphs.
Theorem 2. For every s ≥ 0, Connected Vertex Cover can be solved in polynomial time for (sP1 + P5 )-free graphs.
We observe that our result is somewhat unexpected; there exist many problems whose
computational complexity jumps from polynomial-time solvable on Pr -free graphs to
NP-complete on (P1 + Pr , Pr+1 )-free graphs; for instance, Colouring for r = 4 [15]
and Clique Transversal for r = 4 [2,13].
Our Method. We first note that the difference between a minimum vertex cover
and a minimum connected vertex cover in an (sP1 + P5 )-free graph is at most 1 if
s = 0 and at most 3s + 10 if s ≥ 1 [14]. (For an example that shows the bound is
tight when s = 0, see the graph G1 in Figure 1.) We cannot exploit this property
2

directly as that would require an algorithm to enumerate all minimum vertex covers
in polynomial time. Moreover, the graph G2 in Figure 1 shows that even if this were
possible, it is not immediately obvious how to proceed; one cannot necessarily hope
to find a minimum connected vertex cover by extending a minimum vertex cover. As
an extra complication, for Connected Vertex Cover one cannot extend results on
H-free graphs to results on (sP1 + H)-free graphs in a straightforward way (certainly
one cannot use the technique for Vertex Cover described before Theorem 1).
Our method is based on an analysis of the structure of dominating sets in (sP1 +P5 )free graphs using a characterization of P5 -free graphs due to Bacsó and Tuza [1]. We
translate the problem into a problem in which we try to extend a partial vertex cover
into a full connected vertex cover. We solve this extension variant of Connected
Vertex Cover by using Theorem 1 (applied to the smaller class of (sP1 + P5 )-free
graphs). We show how to do this in Section 3 and then show how to use this result to
prove Theorem 2 in Section 4. An important ingredient of our proof is to reduce the
size of the input graph by contracting an edge between two vertices u and v whenever
we detect that u and v will belong to the connected vertex cover. This idea stems
from the observation that a connected graph G on n vertices has a connected vertex
cover of size k if and only if G contains the star K1,n−k on n − k + 1 vertices as a
contraction.1
G1

G1

G2

G2

Fig. 1: An example of a P5 -free graph G1 with a minimum connected vertex cover
(coloured black in the right-hand drawing) that contains no minimum vertex cover
(there are exactly two, indicated by the sets of black and white vertices in the lefthand drawing). The graph G2 is an example of a (P1 + P5 )-free graph with a minimum
vertex cover (coloured black in the left hand drawing) that is not contained in any
minimum connected vertex cover; clearly any connected vertex cover that contains it
has at least five vertices and an example of a minimum connected vertex cover on four
vertices is indicated by the vertices coloured black in the right-hand drawing.

2

Preliminaries

We consider only finite, undirected graphs without multiple edges or self-loops. Let
G = (V, E) be a graph. For a set S ⊆ V , the graph G[S] denotes the subgraph
of G induced by S, and we say that S is connected if G[S] is connected. We write
G − S = G[V \ S], and if S = {u} we may simply write G − u. For a vertex u ∈ V ,
we write NG (u) = {v | uv ∈ E} to denote the neighbourhood of u. For a set S ⊆ V ,
1

If G has a connected vertex cover S of size k, then contracting every edge between vertices
in S modifies G into K1,n−k . If G contains K1,n−k as a contraction, then VG can be
partitioned into sets A, B1 , . . . , Bn−k that each induce a connected graph such that there
exists at least one edge between a vertex from A and a vertex from Bi for i = 1, . . . , n − k
and no edges between two vertices from different B-sets. If |Bi | ≥ 2, then we move every
vertex that is adjacent to a vertex of A to A until we have only one vertex in Bi left. This
gives us a connected vertex cover of size k.

3

S
we write NG (S) = ( u∈S NG (u)) \ S. A subset D ⊆ V is a dominating set of G if
every vertex of V \ D is adjacent to at least one vertex of D. An edge uv of a graph
G = (V, E) is dominating if {u, v} is dominating. The contraction of an edge uv ∈ E
is the operation that replaces u and v by a new vertex adjacent to precisely those
vertices of V \ {u, v} adjacent to u or v in G. Recall that for a graph H, we say that
another graph G is H-free if it does not contain an induced subgraph isomorphic to
H. The disjoint union G + H of two vertex-disjoint graphs G and H is the graph
(VG ∪ VH , EG ∪ EH ). The disjoint union of r copies of a graph G is denoted by rG. A
linear forest is the disjoint union of one or more paths. The following, straightforward
lemma holds for any linear forest, but, as we repeatedly make use of it, it is convenient
to state in these terms.
Lemma 1. Let G be a connected (sP1 + P5 )-free graph for some s ≥ 0. The graph
obtained from G after contracting an edge is also connected and (sP1 + P5 )-free.
We will use the following result of Bacsó and Tuza [1] as a lemma in our proof.
Lemma 2 ([1]). Every connected P5 -free graph G has a dominating set D, computable
in O(n3 ) time, that either induces a P3 or a complete graph.
Note that it is not difficult to compute the set D in polynomial time via a step-by-step
vertex approach; this also follows from a more general result of Camby and Schaudt [5]
for Pr -free graphs (r ≥ 1).

3

An Auxiliary Problem

In this section we prove that a variant of Connected Vertex Cover can be solved in
polynomial time for (sP1 +P5 )-free graphs for every integer s ≥ 0. To prove Theorem 2
we will solve a polynomial number of instances of this variant, which we show can be
solved in polynomial time for (sP1 + P5 )-free graphs for every s ≥ 0. We introduce
the variant by first describing its input. Let G be a connected graph, let J ⊆ VG be
a subset of the vertex set of G and let y be a vertex of J. We call the triple (G, J, y)
cover-complete if it has the following properties (see also Figure 2):
(A) J is an independent set;
(B) y is adjacent to every vertex of G − J;
(C) the neighbours of each vertex in J \ {y} form an independent set in G − J.
We now describe the problem.
Connected Vertex Cover Completion
Instance: a cover-complete triple (G, J, y).
Goal: find a smallest connected vertex cover S of G such that J ⊆ S.
We will show how to solve this problem in polynomial time for (sP1 + P5 )-free graphs
for any s ≥ 0. We first make some further definitions and then prove a number of
lemmas.
Let (G, J, y) be a cover-complete triple, where G is a connected (sP1 + P5 )-free
graph. For a vertex w ∈ NG (J \ {y}), we write Jw = NG (w) ∩ J. Note that, by (B),
y ∈ Jw . Let G′ be the graph obtained from G by contracting every edge of G[Jw ∪{w}].
As G[Jw ∪{w}] is connected, contracting its edges reduces it to a single vertex which we
denote yw . We say that we have set-contracted G into G′ via w and that we contracted
Jw ∪ {w} into yw ; see Figure 2 for an example.
The following lemma is crucial.
4

L

J

w

L′

y

Jw

yw

J′

Fig. 2: An example of a cover-complete triple (G, J, y) and the cover-complete triple
(G′ , J ′ , yw ) obtained from set-contracting G via vertex w. The sets L = NG (J \ {y})
and L′ = NG′ (J ′ \ {yw }) are also displayed.

Lemma 3. Let (G, J, y) be a cover-complete triple, where G is a connected (sP1 +P5 )free graph for some s ≥ 0. Let w ∈ NG (J \ {y}), and let G′ be the graph obtained from
G after set-contracting via w. Let J ′ = (J \Jw )∪{yw } and y ′ = yw . Then the following
hold:
1. G′ is a connected (sP1 + P5 )-free graph;
2. (G′ , J ′ , y ′ ) is a cover-complete triple;
3. A set S ⊆ VG is a (smallest) connected vertex cover of G that contains J ∪ {w}
if and only if (S \ (J ∪ {w}) ∪ J ′ is a (smallest) connected vertex cover of G′ that
contains J ′ .
Proof. We will prove 1-3 separately.
1. By Lemma 1, G′ is connected and (sP1 + P5 )-free. This proves 1.
2. We will prove (A)-(C) for (G′ , J ′ , y ′ ). Before we do this we first observe the following.
As (B) holds for (G, J, y), we find that y ∈ J is adjacent to w in G. Hence y belongs
to Jw and thus to Jw ∪ {w}, which is contracted to the single vertex y ′ in G′ . Hence,
y is not in G′ and its role has been taken over by y ′ , as we show below.
We first prove (A). As J is an independent set in G, we find that J \ Jw is an
independent set in G′ . For contradiction, suppose that y ′ is adjacent to a vertex in
J \ Jw . Then there is an edge between a vertex of J \ Jw and a vertex of Jw ∪ {w} in G.
However, this not possible as J is independent in G, and thus every edge in G[J ∪ {w}]
is incident with w. Hence J ′ = (J \ Jw ) ∪ {y ′ } is an independent set in G′ . This proves
(A).
We now prove (B). Recall that y belongs to Jw ∪ {w}, which is contracted to y ′ in
′
G . Hence, as y is adjacent to every vertex of G − J in G, we find that y ′ is adjacent
to every vertex of G′ − J ′ . This proves (B).
Finally we prove (C). Let x ∈ J ′ \ {y ′ }. Then x is not adjacent to y ′ , as we showed
above that J ′ is an independent set in G′ . Then NG′ (x) = NG (x) is an independent
set, as (C) holds for (G, J, y). This proves (C) and 2.
3. Any connected vertex cover S of G that contains J ∪ {w} contains every vertex of
Jw ∪ {w}. Hence contracting Jw ∪ {w} to y ′ yields a connected vertex cover (S \ (J ∪
{w}) ∪ J ′ of G′ that contains J ′ . Any connected vertex cover S ′ of G′ that contains J ′
contains y ′ . Hence uncontracting the edges of G[Jw ∪ {w}] yields a connected vertex
cover (S ′ ∪ J ∪ {w}) \ J ′ of G that contains J ∪ {w}. This proves 3.
⊓
⊔
5

Let (G, J, y) be a cover-complete triple. We define LJ = NG (J \ {y}). If there is
no ambiguity, we will just write L = LJ (see also Figure 2). Note that, by (C), L is
the union of a number of independent sets, but L itself might not be independent.
However we can deduce the following lemma, which follows immediately from (C).
Lemma 4. Let (G, J, y) be a cover-complete triple. If w1 and w2 are two adjacent
vertices in L, then no vertex of J \ {y} is adjacent to both w1 and w2 .
We introduce two key definitions for a cover-complete triple (G, J, y). Two vertices
w1 , w2 ∈ L form a pseudo-dominating pair if
– w1 and w2 are non-adjacent;
– w1 has a neighbour x1 ∈ J not adjacent to w2 ; and
– w2 has a neighbour x2 ∈ J not adjacent to w1 .
Three vertices w1 , w2 , w3 ∈ L form a pseudo-dominating triple if
– w1 is adjacent to neither w2 nor w3 ;
– w2 and w3 are adjacent;
– J contains two distinct vertices x1 and x2 such that
• x1 ∈ NG (w1 ) \ NG ({w2 , w3 }) and
• x2 ∈ (NG (w1 ) ∩ NG (w2 )) \ NG (w3 ).
See the illustrations in Figure 3, from which we also observe that no pseudo-dominating
pair or pseudo-dominating triple can be found in a P5 -free graph.

L

J

w1

w2

x1

x2

w1

w3
w2

y

x1

x2

L

J

Fig. 3: Examples, on the left, of a pseudo-dominating pair (w1 , w2 ), and, on the right, of
a pseudo-dominating triple (w1 , w2 , w3 ). As easily seen, the presence of either implies
the existence of at least one induced P5 .

Let S be a connected vertex cover of G that contains J. Recall that J is an
independent set. A subset L∗ ⊆ L ∩ S is a connector of S if J ∪ L∗ is connected. We
present the following two lemmas.
Lemma 5. Let (G, J, y) be a cover-complete triple, where G is an (sP1 + P5 )-free
graph for some s ≥ 0. Let S be a connected vertex cover of G that contains J. If S
contains both vertices of a pseudo-dominating pair w1 , w2 , then S has a connector of
size at most s + 1 that contains both w1 and w2 .
Proof. By definition, there exist two vertices x1 and x2 in J, such that w1 is not
adjacent to x2 and w2 is not adjacent to x1 . As J is an independent set by (A) and
each vertex of L is adjacent to y by (B), we find that {x1 , w1 , y, w2 , x2 } induces a P5
in that order. As G is (sP1 + P5 )-free and J is an independent set, this means that
{w1 , w2 } dominates all vertices of J except for a subset I ⊆ J of at most s − 1 vertices.
6

We choose L∗ to consist of w1 , w2 and a neighbour in L ∩ S of each vertex of I (note
that such a neighbour must exist for each vertex of I as S is connected). Then J ∪ L∗
is connected, that is, L∗ is a connector, as each vertex of J is adjacent to some vertex
of L∗ and each vertex of L∗ is adjacent to y ∈ J due to (B). Moreover, L∗ has size at
most s + 1.
⊓
⊔
Lemma 6. Let (G, J, y) be a cover-complete triple, where G is an (sP1 +P5 )-free graph
for some s ≥ 0. Let S be a connected vertex cover of G that contains J. If S contains
all three vertices of a pseudo-dominating triple w1 , w2 , w3 , then S has a connector of
size at most s + 2 that contains {w1 , w2 , w3 }.
Proof. By definition, there exist two vertices x1 and x2 in J such that x1 is adjacent
to w1 but not to w2 and w3 , and x2 is adjacent to w1 and w2 but not w3 . Then
{x1 , w1 , x2 , w2 , w3 } induce a P5 in that order. As G is (sP1 + P5 )-free and J is an
independent set, this means that {w1 , w2 , w3 } dominates all vertices of J except for a
subset I ⊆ J of at most s − 1 vertices. We choose L∗ to consist of w1 , w2 , w3 and a
neighbour in L ∩ S of each vertex of I (note that such a neighbour must exist for each
vertex of I as S is connected). Then J ∪ L∗ is connected, that is, L∗ is a connector,
as each vertex of J is adjacent to some vertex of L∗ and each vertex of L∗ is adjacent
to y ∈ J due to (B). Moreover, L∗ has size at most s + 2.
⊓
⊔
Let (G, J, y) be a cover-complete triple. Let S be a connected vertex cover of G
that contains J. If S contains both vertices of some pseudo-dominating pair of G or
all three vertices of some pseudo-dominating triple of G, then S is of type 1. Otherwise
S must contain at most one vertex of any pseudo-dominating pair and at most two
vertices of any pseudo-dominating triple of G. In that case we say that S is of type 2.
We observe that G might have connected covers of only one type.
We will now see, in Lemma 8, how to find a smallest type 1 connected vertex
cover of a graph G of a cover-complete triple (G, J, y) in polynomial time (if it exists).
After that we shall prove how to find a smallest type 2 connected vertex cover of G
in polynomial time (if it exists). To compute these sets we need the following lemma,
which uses Theorem 1 in its proof.
Lemma 7. Let (G, {y}, y) be a cover-complete triple, where G is an (sP1 + P5 )-free
graph for some s ≥ 0. Then it is possible to compute a smallest connected vertex cover
of G that contains y in polynomial time.
Proof. As (G, {y}, y) is a cover-complete triple, y dominates G. Moreover G − y is
(sP1 + P5 )-free. Then we can compute a smallest vertex cover S of G − y in polynomial
time by Theorem 1. As y dominates G, we find that S ∪ {y} is a smallest connected
vertex cover of G that contains y.
⊓
⊔
Using Lemmas 5–7, we are now ready to deal with type 1 smallest connected vertex
covers.
Lemma 8. Let (G, J, y) be a cover-complete triple. Then it is possible to find in polynomial time a smallest type 1 connected vertex cover of G.
Proof. We find pseudo-dominating pairs of G by brute force. Note that this takes
polynomial time. For each pseudo-dominating pair (w1 , w2 ) of G, we describe how to
compute a smallest connected vertex cover Sw1 ,w2 of G that contains J ∪ {w1 , w2 }.
By Lemma 5, such a vertex cover must have a connector L∗ of size at most s + 1 that
contains w1 and w2 . We guess L∗ \ {w1 , w2 }. (By guess, we mean choose a set of up
to s − 1 vertices and check if they form, with w1 and w2 , a connector. We eventually
7

look at all such sets.) As there are O(ns−1 ) sets to guess, this adds only a polynomial
factor to the running time of our algorithm. For each guess L∗ , we check if J ∪ L∗ is
connected. If so, then we apply Lemma 3 recursively for each w ∈ L∗ . As |L∗ | ≤ s + 1,
this takes polynomial time. Let (G′ , J ′ , y ′ ) be the resulting cover-complete triple. Then
J ′ = {y ′ }, which means we can apply Lemma 7 to find a smallest connected vertex
cover S ′ of G′ in polynomial time. We translate S ′ , in polynomial time, into the desired
vertex cover Sw1 ,w2 by uncontracting any contracted edges using Lemma 3.
For each pseudo-dominating triple (w1 , w2 , w3 ) of G we compute a smallest connected vertex cover Sw1 ,w2 ,w3 of G that contains J ∪ {w1 , w2 , w3 }. We can do this in
polynomial time by exactly the same arguments: the only difference is that we need
to apply Lemma 6 and guess a connector L∗ of size at most s + 2.
From all the computed sets Sw1 ,w2 and Sw1 ,w2 ,w3 we take the smallest one (which
we can do in polynomial time). This proves Lemma 8.
⊓
⊔
Let (G, J, y) be a cover-complete triple. Using Lemma 8 we can find a smallest
type 1 connected vertex cover of G. However, it might be possible that G has a smaller
connected vertex cover of type 2. To investigate this, we introduce two reduction
rules that will transform a cover-complete triple (G, J, y) into a triple (G′ , J ′ , y ′ ) with
|J ′ | < |J|. We say that such a rule is safe if the following three statements hold:
1. If G is (sP1 + P5 )-free and connected, then G′ is (sP1 + P5 )-free and connected.
2. (G′ , J ′ , y ′ ) is cover-complete.
3. Given a smallest connected vertex cover S ′ of G′ that contains J ′ , it is possible, in
polynomial time, to find a smallest connected vertex cover S of G that contains J.
Rule 1. Set-contract via x whenever x is a vertex in L ∩ NG (w1 ) ∩ NG (w2 ) for some
pseudo-dominating pair (w1 , w2 ).
Rule 2. For any vertex w5 ∈ L that is not adjacent to any vertex of a clique of four
vertices w1 , w2 , w3 , w4 in L, delete w5 and set-contract via u for every u ∈ L ∩ NG (w5 ).
Lemma 9. Rules 1 and 2 are safe.
Proof. We first consider Rule 1.
Let (G′ , J ′ , y ′ ) be the resulting triple after an application of Rule 1, where J ′ =
(J \ Jx ) ∪ {yx } and y ′ = yx . By Lemma 3, (G′ , J ′ , y ′ ) is a cover-complete triple. By the
same lemma, G′ is (sP1 + P5 )-free and connected if G is (sP1 + P5 )-free and connected.
Hence we have proven that conditions 1 and 2 hold.
We are left to prove condition 3. Let S ′ be a smallest connected vertex cover in G′
that contains J ′ . Then S = (S ′ \ {y ′ }) ∪ Jx ∪ {x} is a smallest connected vertex cover
of G that contains J ∪ {x} due to Lemma 3. We prove the following claim.
Claim. For any type 2 connected vertex cover T of G, it holds that |T | ≥ |S|.
We prove the Claim as follows. Let T be a connected vertex cover T of G that is of
type 2. Suppose x ∈
/ T . Then, as x is adjacent to both w1 and w2 , we find that T
contains both w1 and w2 . Thus T is not of type 2, a contradiction. Hence T contains
x. This implies that the set T ′ = (T \ (J ∪ {x}) ∪ J ′ is a connected vertex cover of G′
that contains J ′ . As S ′ is a smallest connected vertex cover of G′ that contains J ′ , we
find that |T ′ | ≥ |S ′ |. Hence |T | = |T ′ | + |Jx | ≥ |S ′ | + |Jx | = |S|. This proves the Claim.
The above means that we can do as follows. Given S ′ we compute S in polynomial time.
By Lemma 8 we can also compute, in polynomial time, a smallest type 1 connected
vertex cover S ∗ of G (note that S = S ∗ is possible). If S is of type 2, then S is a
smallest type 2 connected cover of G, due to the Claim. We compare |S| and |S ∗ | and
8

choose the smallest one. If S is of type 1, then S ∗ is a smallest connected vertex cover
of G, again due to the Claim. This proves condition 3 and completes the proof that
Rule 1 is safe.
We now consider Rule 2. We first show that w5 cannot be in any connected vertex
cover S of G that is of type 2. For contradiction, suppose that w5 is in such a connected
cover S. Because S is a vertex cover and {w1 , w2 , w3 , w4 } is a clique, S contains at
least three of {w1 , w2 , w3 , w4 }, say w1 , w2 , w3 .
For i = 1, . . . , 5, let Xi be the set of neighbours of wi in J. As wi ∈ L, every Xi 6= ∅
by definition of L. By Lemma 4, we find that X1 ∩ X2 ∩ X3 = ∅. Let x ∈ X1 . If x ∈
/ X5 ,
then X5 ⊆ X1 , as otherwise (w1 , w5 ) is a pseudo-dominating pair of vertices that are
both contained in S, which is not possible as S is of type 2. As X1 ∩ X2 = ∅, we find
that X5 ∩ X2 = ∅. This means that (w2 , w5 ) is a pseudo-dominating pair of vertices
that are both contained in S, which is not possible either. Hence x ∈ X5 . We conclude
that X1 ⊆ X5 . For the same reason, we find that X2 ⊆ X5 and X3 ⊆ X5 .
Recall that X1 ∩ X2 ∩ X3 = ∅. Hence we can pick a vertex x1 ∈ X1 and a vertex
x3 ∈ X3 , which are both adjacent to w5 but not to w2 , and so find that (w5 , w1 , w2 )
is a pseudo-dominating triple. As all three vertices w1 , w2 , w5 belong to S, while S is
of type 2, this is not possible. Hence S does not contain w5 .
As no connected vertex cover of G of type 2 may contain w5 , any connected vertex
cover of G that is of type 2 must contain all neighbours of w5 , and we can delete w5 .
The proof of conditions 1–3 is identical to the proof for Rule 1 where the neighbours
of w5 in L take the role of the vertex x in the proof for Rule 1.
⊓
⊔
We call a cover-complete triple (G, J, y) free if G has no pseudo-dominating pair
with a common neighbour in L, and moreover, G[L] is (P1 + K4 )-free. By exhaustively
applying Rules 1 and 2 in arbitrary order, which we may safely do due to Lemma 9,
we have the following lemma.
Lemma 10. A cover-complete triple (G, J, y) can be modified, in polynomial time,
into a free cover-complete triple (G′ , J ′ , y) with the following properties:
1. .If G is (sP1 + P5 )-free and connected, then G′ is (sP1 + P5 )-free and connected.
2. Given a smallest connected vertex cover S ′ of G′ that contains J ′ , it is possible to
find in polynomial time a smallest connected vertex cover S of G that contains J.
Proof. We first apply Rule 1 exhaustively and afterwards we apply Rule 2 exhaustively.
As each application of each of these rules take polynomial time and reduces |VG |,
this procedure will stop after polynomial time. By repeated use of Lemma 9, this
results in a cover-complete triple (G′ , J ′ , y) that satisfies the two properties of the
lemma. Moreover, G′ contains no pseudo-dominating pair with a common neighbour
in L′ = LJ ′ and G′ [L′ ] is (P1 + K4 )-free, as otherwise we could still apply Rule 1 or
Rule 2, respectively.
⊓
⊔
Let (G, J, y) be a free cover-complete triple. A connector of a connected vertex
cover S of G is minimal if it does not properly contain a smaller connector of S. The
next three lemmas are on free cover-complete triples; the second makes use of the first.
Lemma 11. Let (G, J, y) be a free cover-complete triple. Every minimal connector L∗
of every type 2 connected vertex cover S of G is a clique.
Proof. For contradiction, suppose that L∗ is not a clique. Then L∗ contains two nonadjacent vertices w1 and w2 . As L∗ is a minimal connector, w1 has a neighbour in
J not adjacent to w2 , and vice versa. However, then (w1 , w2 ) is a pseudo-dominating
pair of G. This is not possible, as S is of type 2.
⊓
⊔
9

Lemma 12. Let (G, J, y) be a free cover-complete triple that has a pseudo-dominating
pair (w1 , w2 ). Then every minimal connector L∗ of every type 2 connected vertex
cover S of G has size at most 5.
Proof. For contraction, suppose that |L∗ | ≥ 6. By Lemma 11, L∗ is a clique. As
(G, J, y) is free, G′ [L′ ] is (K4 + P1 )-free by definition. Hence w1 must be adjacent to
least three vertices of L∗ , which we denote by x1 , x2 , x3 . Note that {w1 , x1 , x2 , x3 }
induces a K4 in G[L]. By definition of a pseudo-dominating pair, w1 and w2 are
non-adjacent. As (G, J, y) is free, w2 is not adjacent to any neighbour of w1 in L by
definition. Hence w2 is not adjacent to any vertex of {x1 , x2 , x3 }. This means that the
set {w1 , w2 , x1 , x2 , x3 } induces a K4 + P1 in G[L], a contradiction.
⊓
⊔
Lemma 13. Let (G, J, y) be a free cover-complete triple that has no pseudo-dominating
pair. It is possible to find in polynomial time a clique K ⊆ L with NG (K) ∩ J = J.
Proof. We describe how to construct K. Consider a vertex w1 ∈ L that has maximum
neighbourhood in J, that is, there is no vertex w ∈ L with NG (w1 ) ∩ J ( NG (w) ∩ J.
We put w1 in K. Suppose that at some point we have constructed a clique K =
{w1 , . . . , wi } for some i ≥ 1. If NG (K) ∩ J = J, then we stop. Otherwise we pick a
vertex wi+1 with maximum neighbourhood in J \ NG (K) over all vertices in L (or
equivalently, all vertices in L \ {w1 , . . . , wi }. Note that wi+1 exists as G is connected.
Suppose that wi+1 is adjacent to some x ∈ NG (K) ∩ J. Then, by Lemma 4, we find
that x is adjacent to a unique vertex wh in K. By the same lemma, wi+1 is not adjacent
to wh . As G has no pseudo-dominating pair and wi+1 has a neighbour in J \ NG (K)
(that is, a neighbour not adjacent to wh ), we find that NG (wh ) ( NG (wi+1 ). This
means that we would have chosen wi+1 earlier, namely instead of wh . Hence, wi+1 is
not adjacent to any x ∈ NG (K) ∩ J. As G has no pseudo-dominating pairs, this means
that wi+1 is adjacent to every wj with 1 ≤ j ≤ i. That is, we can extend K into a
larger clique by adding wi+1 .
As we increase NG (K) ∩ J each time we add a new vertex to K, our procedure
will stop with the desired output K = {w1 , . . . , wr } for some r ≥ 1. We note that
constructing K takes polynomial time.
⊓
⊔
We are now ready to prove the following theorem.
Theorem 3. For every s ≥ 0, Connected Vertex Cover Completion can be
solved in polynomial time for (sP1 + P5 )-free graphs.
Proof. Let s ≥ 0 and let (G, J, y) be a cover-complete triple, where G is an (sP1 + P5 )free graph. We first apply Lemma 10 to obtain a free cover-complete triple (G′ , J ′ , y ′ )
in polynomial time. By the same lemma, G′ is (sP1 + P5 )-free. Our aim is to find a
smallest connected vertex cover of G′ that contains J ′ in polynomial time, so that we
can apply statement 2 of Lemma 10. We first compute in polynomial time a smallest
type 1 connected vertex cover S ∗ of G′ using Lemma 8. We now need to compute a
smallest type 2 connected vertex cover S ′ of G′ and compare |S ′ | with |S ∗ |.
First suppose that G′ contains a pseudo-dominating pair. We guess a minimal
connector of size at most 5 and apply Lemma 3 on its vertices. If we obtain an instance
(G′′ , {y ′′ }, y ′′ ), then we apply Lemma 7. Then we uncontract all contracted edges to
get a connected vertex cover of G′ of type 2. By Lemma 12, doing this for every guessed
minimal connector of size at most 5 gives us a smallest type 2 connected vertex cover
S ′ of G′ . As we process each guess in polynomial time and there are at most O(n5 )
guesses, we find S ′ in polynomial time. We compare S ′ and S ∗ and choose the smaller
of the two.
10

Now suppose that G′ has no pseudo-dominating pair. Let L′ = NG′ (J ′ \ {y ′ }). By
Lemma 13, we can obtain in polynomial time a clique K ⊆ L′ with NG′ (K) ∩ J ′ = J ′ .
Let K = {w1 , . . . , wr } for some r ≥ 1. As K is a clique, every vertex cover contains at
least r − 1 vertices of K. We will do as follows: first we will find in polynomial time a
smallest connected vertex cover of G′ that contains J ′ ∪ K, and then we will find in
polynomial time, for i = 1, . . . , r, a smallest connected vertex cover of G′ that contains
J ′ ∪ K \ {wi } and that does not contain wi . As there are O(n) cases, the total time is
polynomial.
We start by computing a smallest connected vertex cover of G′ that contains J ′ ∪K
by set-contracting via each vertex of K. By Lemma 3, this yields a cover-complete triple
(G′′ , {y ′′ }, y ′′ ) to which we apply Lemma 7. Then we uncontract all contracted edges
in polynomial time. By Lemma 3, this yields a smallest connected vertex cover SK of
G′ that contains J ′ ∪ K.
We now show how to compute, in polynomial time, a smallest connected vertex
cover of G′ that contains J ′ ∪ K \ {w1 } and that does not contain w1 . The case i ≥ 2
is done in the same way.
Let A = L′ \ NG′ (w1 ) consist of all non-neighbours of w1 in L′ . As G′ [L′ ] is (K4 +
P1 )-free by definition, we find that G′ [A] is K4 -free. As w1 is not in the connected vertex
cover we are looking for we remove w1 , and we set-contract via each neighbour of w1 in
L. By Lemma 3, we may now consider the resulting cover-complete triple (G′′ , J ′′ , y ′′ )
where G′′ is connected and (sP1 + P5 )-free. As G′ had no pseudo-dominating pairs,
we have that G′′ has no pseudo-dominating pairs. We write L′′ = NG′′ (J ′′ \ {y ′′ }). As
L′′ ⊆ A, we find that G′′ [L′′ ] is K4 -free.
Claim. Every minimal connector L∗ of every connected vertex cover of G′′ that contains
J ′′ has size at most 3.
We prove the Claim by showing that L∗ is a clique, which implies that L∗ has size
at most 3, as G′′ [L′′ ] is K4 -free. Suppose instead that L∗ is not a clique. Then L∗
contains two non-adjacent vertices w1 and w2 . As L∗ is a minimal connector, w1 has
a neighbour in J ′′ not adjacent to w2 , and vice versa. But then (w1 , w2 ) is a pseudodominating pair of G′′ : this is not possible, as G′′ has no pseudo-dominating pairs.
This contradiction proves the claim.
We now guess a minimal connector by considering all subsets in L′′ that have size at
most 3. For each guess we apply Lemma 3 on its vertices. If we obtain an instance
(G′′′ , {y ′′′ }, y ′′′ ), then we apply Lemma 7. Then we uncontract all contracted edges to
obtain in polynomial time a connected vertex cover of G′′ that contains J ′′ . We take
the smallest one of these connected vertex covers of G′′ . For this connected vertex
cover of G′′ , we uncontract all contracted edges again to obtain in polynomial time a
smallest connected vertex cover Sw1 of G′ that contains J ′ ∪ K \ {w1 } and that does
not contain w1 .
As mentioned, we pick the smallest one out of the connected vertex covers SK and
Swi , 1 ≤ i ≤ r, to obtain a smallest type 2 connected vertex cover of G′ , the size of
which we compare with the size of S ∗ . We pick the smallest one.
Thus we obtain in polynomial time a smallest connected vertex cover of G′ that
contains J ′ (both in the case where G′ has a pseudo-dominating pair and in the case
where G′ has no pseudo-dominating pair). As stated, it remains to apply statement 2
of Lemma 10 to find in polynomial time a smallest connected vertex cover of G that
contains J. The correctness of our algorithm follows immediately from the above case
analysis and the description of the cases.
⊓
⊔
11

4

Our Main Result

In this section we prove Theorem 2, that is, we show that Connected Vertex Cover
can be solved in polynomial time for (sP1 + P5 )-free graphs for every integer s ≥ 0.
The proof relies heavily on Theorem 3. The main idea is to reduce an (sP1 + P5 )-free
input graph G of Connected Vertex Cover to a polynomial number of instances
(Gi , Ji , yi ) of Connected Vertex Cover Completion. We can then solve each of
these instances (Gi , Ji , yi ) in polynomial time by Theorem 3. Then we translate the
resulting connected vertex covers of Gi (which contain Ji ) into connected vertex covers
of G. We pick the smallest of these sets as our final output.
We need two more lemmas (we use Lemma 2 to prove the first one).
Lemma 14. Let s ≥ 0 and let G be a connected (sP1 + P5 )-free graph. Then G has
a connected dominating set D that is either a clique or has size at most 2s2 + s + 2.
2
Moreover, D can be found in O(n2s +s+4 ) time.
Proof. If G is P5 -free, then we apply Lemma 2. Otherwise, as G is (sP1 +P5 )-free, there
exists an integer 0 ≤ r ≤ s−1 such that G contains an induced subgraph H isomorphic
to rP1 + P5 . Let VH = {a1 , . . . , ar , b1 , . . . , b5 } such that the b-vertices induce a P5 in
that order. We choose r to be maximum so G contains no induced (r + 1)P1 + P5 .
Hence, VH dominates G. As G is (sP1 + P5 )-free, G is P5+2s -free. Hence, for each ai ,
there exists a path of at most 5 + 2s − 1 vertices that connects ai to b1 . Let H ∗ be the
graph that contains H and all these ai − b1 -paths. Then we choose D = VH ∗ . As VH
dominates G, we find that D ⊇ VH also dominates G. Moreover, D has size at most
r(5 + 2s − 2) + 5 ≤ 2s2 + s + 2. We can find D by considering, if needed, every set of
at most 2s2 + s + 2 vertices in G and checking if such a set is dominating. This brute
2
force procedure takes O(n2s +s+4 ) time in total.
⊓
⊔
Lemma 15. Let J be an independent set of a connected graph G, such that J has a
vertex y that is adjacent to every vertex of G − J. Let J ′ consist of those vertices of
J \ {y} that have two adjacent neighbours in G − J (or equivalently, in G). Then a
subset S is a connected vertex cover of G that contains J if and only if S \ J ′ is a
connected vertex cover of G − J ′ that contains J \ J ′ .
Proof. Let w ∈ J \ {y} be a vertex in G with two adjacent neighbours a and b in G − J
(or equivalently in G). Let S be a subset of G. First suppose that S is a connected
vertex cover of G that contains J. Then S \ {w} is a vertex cover of G − w that
contains J \ {w}. As y ∈ J and y 6= w, we find that S contains y. Then every vertex of
S that belongs to G − J is adjacent to y in G[S]. Moreover, as S is connected and J
is independent, every vertex of J \ {w} must be adjacent in G[S] to a vertex of G − J.
Hence, S is connected in G − w.
Now suppose that S \ {w} is a connected vertex cover of G − w that contains
J \ {w}. Then S is a vertex cover of G that contains J. As y ∈ J, we find that S
contains y. As ab is an edge, S contains at least one of a and b. Then w and y are
adjacent in S either due to the edges ya, aw (if a is in S) or due to the edges yb, bw
(if a is not in S, as then b ∈ S). Hence S is connected in G.
We now consider the graph G − w and repeat the arguments above for any vertex
in J ′ \ {w}.
⊓
⊔
We are now ready to prove our main result.
Theorem 2. (Restated) For every s ≥ 0, Connected Vertex Cover can be
solved in polynomial time for (sP1 + P5 )-free graphs.
12

Proof. Let G be an (sP1 + P5 )-free graph on n vertices for some s ≥ 0. We may assume
without loss of generality that G is connected. By Lemma 14 we can first compute in
2
O(n2s +s+4 ) time a connected dominating set D that either has size at most 2s2 +s+2
or is a clique. We note that, if D is a clique, any vertex cover of G contains all but at
most two vertices of D. This leads to a case analysis where we guess the subset D∗ ⊆ D
of vertices not in a minimum connected vertex cover of G. Because |D∗ | ≤ 2s2 + s + 2,
the number of guesses is polynomial. For each guess of D∗ , we compute a smallest
connected vertex cover SD∗ that contains all vertices of D \ D∗ and no vertex of D∗ .
Then, in the end, we return the one that has minimum size overall.
Let D∗ be a guess. Before we start our case analysis we first prove the following
claim.
Claim 1. We may assume without loss of generality that D \ D∗ is connected.
We prove Claim 1 as follows. Suppose D\D∗ is not connected. Recall that G[D] is either
a complete graph or has size at most 2s2 +s+2. In the first case, G[D\D∗ ] is connected.
Hence, the second case applies so D has size at most 2s2 + s + 2. Let v ∈ D \ D∗ . As
G is (sP1 + P5 )-free, G is also P5+2s -free. Hence, for each u ∈ D \ (D∗ ∪ {v}), any
connected vertex cover of G contains a path of at most 5 + 2s− 1 vertices that connects
u to v. We will guess all these u − v-paths (using only vertices from G − D∗ ) and add
their vertices to D. As the number of paths is at most 2s2 + s + 1, this branching
only adds a polynomial factor to our running time and increases our set D by only a
constant number of extra vertices. We have proven Claim 1.
Case 1. D∗ = ∅.
We compute a minimum vertex cover S ′ of G − D in polynomial time by Theorem 1.
Clearly S ′ ∪ D is a vertex cover of G. As D is a connected dominating set, S ′ ∪ D is
even a connected vertex cover of G. Let S∅ = S ′ ∪ D. As S ′ is a minimum vertex cover
of G − D, S∅ is a smallest connected vertex cover of G that contains all vertices of D.
We remember S∅ . Note that S∅ is found in polynomial time.
Case 2. 1 ≤ |D∗ | ≤ 2s2 + s + 2.
Recall that we are looking for a smallest connected vertex cover of G that contains
every vertex of D \ D∗ but does not contain any vertex of D∗ . Hence D∗ must be an
independent set and G− D∗ must be connected (if one of these conditions is false, then
we stop considering the guess D∗ ).Moreover, a vertex cover that contains no vertex of
D∗ must contain all vertices of NG (D∗ ). Hence we can safely contract not only any
edge between two vertices of D \D∗ , but also any edge between two vertices in NG (D∗ )
or between a vertex of D \ D∗ and a vertex in NG (D∗ ). We perform edge contractions
recursively and as long as possible while remembering all the edges that we contract.
Let G∗ be the resulting graph.
Note that the set D∗ still exists in G∗ , as we did not contract any edges with an
endpoint in D∗ . By Claim 1, the set D \ D∗ in G corresponds to exactly one vertex
of in G∗ . We denote this vertex by y. We observe the following equivalence, which is
obtained after uncontracting all the contracted edges.
Claim 2. Every smallest connected vertex cover of G∗ that contains y and that does
not contain any vertex of D∗ corresponds to a smallest connected vertex cover of G
that contains D \ D∗ and that does not contain any vertex of D∗ , and vice versa.
As we obtained G∗ in polynomial time, and we can uncontract all contracted edges in
polynomial time as well, Claim 2 tells us that we may consider G∗ instead of G. As
G is connected and (sP1 + P5 )-free, G∗ is connected and (sP1 + P5 )-free as well by
Lemma 1.
We write J ∗ = NG∗ (D∗ ) and note that y belongs to J ∗ as D is connected in G.
We now consider the graph G∗ − D∗ . As G − D∗ is connected, G∗ − D∗ is connected.
13

By Claim 2, our new goal is to find a smallest connected vertex cover of G∗ − D∗ that
contains J ∗ . By our procedure, J ∗ is an independent set of G∗ − D∗ . As D dominates
G, we find that D \ D∗ dominates every vertex of G − D∗ that is not adjacent to a
vertex of D∗ . Hence the vertex y, which corresponds to the set D \ D∗ , is adjacent to
every vertex of (G∗ − D∗ ) − J ∗ in the graph G∗ − D∗ .
Let J ⊆ J ∗ consist of y and those vertices in J ∗ whose neighbourhood in G∗ −D∗ is
an independent set. As y is adjacent to every vertex of (G∗ − D∗ ) − J ∗ in G∗ − D∗ , and
we can remember the set J \ J ∗ , we can apply Lemma 15 and remove J \ J ∗ . That is, it
suffices to find a smallest connected vertex cover of the graph G′ = (G∗ −D∗ )−(J ∗ \J)
that contains J.
As J ∗ is an independent set of G∗ − D∗ , we find that J is an independent set of G′ .
By definition, y ∈ J. As y is adjacent to every vertex of (G∗ − D∗ ) − J ∗ in G∗ − D∗ ,
we find that y is adjacent to every vertex in G′ − J. By definition, the neighbours of
each vertex in J \ {y} form an independent set in G′ − J. Hence the triple (G′ , J, y) is
cover-complete. This means that we can apply Theorem 3 to find in polynomial time
a smallest connected vertex cover S ′ of G′ that contains J.
We translate S ′ in polynomial time into a smallest connected vertex cover S ∗ of
∗
G − D∗ that contains J ∗ by adding J ∗ \ J to S ′ . We translate S ∗ in polynomial time
into a smallest connected vertex cover SD∗ of G that contains no vertex of D∗ by
uncontracting any contracted edges.
As mentioned, in the end we pick, in polynomial time, a smallest set of the sets
SD∗ . This set is then a minimum connected vertex cover of G, which is obtained in
polynomial time. We have not sought to optimize the running time of the algorithm
so do not provide a detailed analysis, but observe that, for sufficiently large s, it is
3
nO(s ) . The running time is dominated by obtaining a connected D \ D∗ (in Claim
2
1). As D \ D∗ has O(n2s +s+2 ) components and the paths required to join them each
3
have O(s) vertices, the time required to find them is nO(s ) . The correctness of our
algorithm follows immediately from the above case analysis and the description of the
cases.
⊓
⊔

5

Conclusions

We proved that Connected Vertex Cover is polynomial-time solvable for (sP1 +
P5 )-free graphs for every integer s ≥ 0. We finish our paper by posing the following
two open problems.
1. What is the complexity of Connected Vertex Cover for P6 -free graphs?
2. Does there exist an integer r such that Connected Vertex Cover is NPcomplete for Pr -free graphs?
For Question 1, it might be easier to consider first the class of (P2 + P3 )-free graphs,
for which we do not know the complexity of Connected Vertex Cover either.

References
1. G. Bacsó and Zs. Tuza, Dominating cliques in P5 -free graphs, Periodica Mathematica
Hungarica 21(1990) 303–308.
2. V. Balachandhran, P. Nagavamsi, C. Pandu Rangan, Clique transversal and clique independence on comparability graphs, Information Processing Letters 58 (1996) 181–184.
3. E. Balas and C. S. Yu, On graphs with polynomially solvable maximum-weight clique
problem, Networks 19 (1989) 247–253.

14

4. E. Camby, J. Cardinal, S. Fiorini and O. Schaudt, The price of connectivity for vertex
cover. Discrete Mathematics & Theoretical Computer Science 16 (2014) 207–224.
5. E. Camby and O. Schaudt, A new characterization of Pk -free graphs, Algorithmica 75
(2016), 205–217.
6. J. Cardinal and E. Levy, Connected vertex covers in dense graphs, Theoretical Computer
Science 411 (2010) 2581–2590.
7. N. Chiarelli, T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma, Minimum connected transversals in graphs: new hardness results and tractable cases using the price of
connectivity, Theoretical Computer Science 705 (2018) 75–83.
8. B. Escoffier, L. Gourvès and J. Monnot, Complexity and approximation results for the
connected vertex cover problem in graphs and hypergraphs, Theoretical Computer Science 8 (2010) 36–49.
9. H. Fernau and D. Manlove, Vertex and edge covers with clustering properties: complexity
and algorithms, Journal of Discrete Algorithms 7 (2009) 149–167.
10. M.R. Garey, D.S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM
Journal on Applied Mathematics 32 (1977) 826–834.
11. F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs
Journal of Combinatorial Theory, Series B 16 (1974) 47–56.
12. A. Grzesik, T. Klimošová, M. Pilipczuk, and M. Pilipczuk, Polynomial-time algorithm
for maximum weight independent set on P6 -free graphs, CoRR, abs/1707.05491, 2017.
13. V. Guruswami and C. Pandu Rangan, Algorithmic aspects of clique-transversal and
clique-independent sets, Discrete Applied Mathematics 100 (2000) 183–202.
14. T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma, The price of connectivity for
transversals, European Journal of Combinatorics 58 (2016) 203–224.
15. D. Král’, J. Kratochvı́l, Zs. Tuza, and G. J. Woeginger, Complexity of coloring graphs
without forbidden induced subgraphs, Proc. WG 2001, Lecture Notes in Computer Science 2204 (2001) 254–262.
16. Y. Li, Z. Yang and W. Wang, Complexity and algorithms for the connected vertex cover
problem in 4-regular graphs, Applied Mathematics and Computation 301 (2017) 107–114.
17. D. Lokshtanov, M. Vatshelle, and Y. Villanger, Independent set in P5 -free graphs in
polynomial time, Proc. SODA 2014, pages 570–581.
18. G.J. Minty, On maximal independent sets of vertices in claw-free graphs, Journal of
Combinatorial Theory, Series B 28 (1980) 284–304.
19. R. Mosca, Stable sets for (P6 , K2,3 )-free graphs, Discussiones Mathematicae Graph Theory 32 (2012) 387–401.
20. A. Munaro, Boundary classes for graph problems involving non-local properties, Theoretical Computer Science 692 (2017) 46–71.
21. S. Poljak, A note on stable sets and colorings of graphs, Commentationes Mathematicae
Universitatis Carolinae. 15 (1974) 307–309.
22. P.K. Priyadarsini and T. Hemalatha, Connected vertex cover in 2-connected planar graph
with maximum degree 4 is NP-complete, International Journal of Mathematical, Physical
and Engineering Sciences. 2 (2008) 51–54.
23. S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, A new algorithm for generating all
the maximal independent sets, SIAM Journal on Computing 6 (1977) 505–517.
24. N. Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe
sans étoile, Discrete Mathematics 29 (1980) 53–76.
25. 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 (1988) 355–360.
26. T. Wanatabe, S. Kajita and K. Onaga, Vertex covers and connected vertex covers in 3connected graphs, Proc. IEEE International Symposium on Circuits and Systems 1991,
1017–1020.

15

