Connected Vertex Cover for $(sP_1+P_5)$-Free Graphs

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. On the other hand, the problem is known to be polynomial-time solvable for $sP_2$-free graphs for any integer $s\ge 1$. We prove that it is also polynomial-time solvable for $(sP_1+P_5)$-free graphs for every integer $s\ge ~0$.

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

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A set S of vertices in a graph G forms a vertex cover of G if every edge of G is incident with a vertex of S. The set S is an independent set if no two vertices in S are adjacent. These definitions lead to two classical graph problems, which are both NP-complete: 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 $\ell$ for a given integer $\ell$. A set S of at least k vertices of a graph G on n vertices is a vertex cover if and only if $V_G\setminus 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.

In 1977, Garey and Johnson [9] proved that Connected Vertex Cover is NP-complete for planar graphs of maximum degree 4. More recently, Priyadarsini and Hemalatha [18] and Fernau and Manlove [8] strengthened this result to 2-connected planar graphs of maximum degree 4 and planar bipartite graphs of maximum degree 4, respectively. Wanatabe et al. [22] proved that Connected Vertex Cover is NP-complete even for 3-connected graphs. Very recently, Munaro [16] proved the same for line graphs of planar cubic bipartite graphs and for planar bipartite graphs of arbitrarily large girth, and Li et al. [13] showed NP-completeness for 4-regular graphs.

We now turn to tractable cases. Ueno et al. [21] proved that Connected Vertex Cover is polynomial-time solvable for graphs of maximum degree at most 3. Escoffier et al. [7] proved the same result for chordal graphs. As Vertex Cover is also polynomial-time solvable for chordal graphs [10], the authors of [7] 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?

This question was addressed by Chiarelli et al. [6] who considered classes of graphs characterized by a single forbidden induced subgraph H. Such graphs are called H-free. They observed that the results of Munaro [16] imply that Connected Vertex Cover is NP-complete for H-free graphs if H contains a cycle or a claw. Using Poljak’s construction [17], 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 [15, 20]. Hence, there exist graphs H such that Connected Vertex Cover and Vertex Cover have different complexities when restricted to H-free graphs (assuming $\mathsf{P}\ne \mathsf{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 $P_r$) 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 $P_r$-free graphs. Lokshtanov et al. [14] proved that Independent Set, and thus Vertex Cover, is polynomial-time solvable for $P_5$-free graphs. Recently, Grzesik et al. [11] extended this to $P_6$-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 $(P_1+H)$-free graphs. This follows from the folklore observation that to solve the complementary problem of Independent Set on a $(P_1+H)$-free graph one solves the problem on each H-free graph obtained by removing a vertex and all its neighbours.

Theorem 1

([11]). For every $s\ge 0$, Vertex Cover can be solved in polynomial time for $(sP_1+P_6)$-free graphs.

By using the concept of the price of connectivity [3, 5, 12], Chiarelli et al. [6] proved that Connected Vertex Cover is polynomial-time solvable for $sP_2$-free graphs for any integer $s\ge 1$. For Vertex Cover this follows by combining two classical results [2, 19] (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 [6, 7] and prove the following result, which includes polynomial-time solvability for $P_5$-free graphs.

Theorem 2

For every $s\ge 0$, Connected Vertex Cover can be solved in polynomial time for $(sP_1+P_5)$-free graphs.

Our Method. It is easy to construct graphs with a minimum connected vertex cover that do not contain a minimum vertex cover; see the graph $G_1$ in Fig. 1. We also note that the difference between a minimum vertex cover and a minimum connected vertex cover in an $(sP_1+P_5)$- free graph is at most 3 if $s=0$ and at most $3s+10$ if $s\ge 1$ [12]. We cannot exploit this property directly as that would require an algorithm to enumerate all minimum vertex covers in polynomial time. Moreover, the graph $G_2$ in Fig. 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 $(sP_1+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 $(sP_1+P_5)$-free graphs using a characterization of $P_5$-free graphs due to Bacsó 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 $(sP_1+P_5)$-free graphs). We show how to do this in Sect. 3 and then show how to use this result to prove Theorem 2 in Sect. 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 $K_{1,n-k}$ on $n-k+1$ vertices as a contraction.

Fig. 1.

An example of a $P_5$-free graph $G_1$ 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 left-hand drawing). The graph $G_2$ is an example of a $(P_1+P_5)$-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

Let $G=(V,E)$ be a graph. For a set $S\subseteq 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\setminus S]$, and if $S=\{u\}$ we may simply write $G-u$. For a vertex $u\in V$, we write $N_G(u)=\{v \;|\; uv\in E\}$ to denote the neighbourhood of u. For a set $S\subseteq V$, we write $N_G(S)=(\bigcup _{u\in S}N_G(u)) \setminus S$. A subset $D\subseteq V$ is a dominating set of G if every vertex of $V\setminus 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\in E$ is the operation that replaces u and v by a new vertex adjacent to precisely those vertices of $V \setminus \{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 $(V_G\,\cup \, V_H, E_G\,\cup \, E_H)$. 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.

Lemma 1

Let G be a connected $(sP_1+P_5)$-free graph for some $s\ge 0$. The graph obtained from G after contracting an edge is also connected and $(sP_1+P_5)$-free.

We will use the following result of Bacsó and Tuza [1] as a lemma.

Lemma 2

([1]). Every connected $P_5$-free graph G has a dominating set D, computable in $O(n^3)$ time, that induces either a $P_3$ or a complete graph.

Note that it is not difficult to compute the set D in polynomial time; this also follows from a more general result of Camby and Schaudt [4] for $P_r$-free graphs ($r\ge 1$).

Proofs of some lemmas are omitted due to space restrictions.

3 An Auxiliary Problem

In this section we prove that a variant of Connected Vertex Cover can be solved in polynomial time for $(sP_1+P_5)$-free graphs for every integer $s\ge 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 $(sP_1+P_5)$-free graphs for every $s\ge 0$. We introduce the variant by first describing its input. Let G be a connected graph, let $J\subseteq V_G$ 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 Fig. 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\setminus \{y\}$ form an independent set in $G-J$.

We now describe the problem.

We will show how to solve this problem in polynomial time for $(sP_1+P_5)$-free graphs for any $s\ge 0$.

Let (G, J, y) be a cover-complete triple, where G is a connected $(sP_1+P_5)$-free graph. For a vertex $w\in N_G(J\setminus \{y\})$, we write $J_w= N_G(w)\cap J$. Note that, by (B), $y\in J_w$. Let $G'$ be the graph obtained from G by contracting every edge of $G[J_w\,\cup \, \{w\}]$. As $G[J_w\,\cup \, \{w\}]$ is connected, contracting its edges reduces it to a single vertex which we denote $y_w$. We say that we have set-contracted G into $G'$ via w and that we contracted $J_w\,\cup \, \{w\}$ into $y_w$.

Fig. 2.

An example of a cover-complete triple (G, J, y) and the cover-complete triple $(G',J',y_w)$ obtained from set-contracting G via vertex w. The sets $J'=(J\setminus J_w)\,\cup \,\{y_w\}$, $L=N_G(J\setminus \{y\})$ and $L'=N_{G'}(J'\setminus \{y_w\})$ are also displayed (the latter two sets will be formally introduced later).

Lemma 3

Let (G, J, y) be a cover-complete triple, where G is a connected $(sP_1+P_5)$-free graph for some $s\ge 0$. Let $w\in N_G(J\setminus \{y\})$, and let $G'$ be the graph obtained from G after set-contracting via w. Let $J'=(J\setminus J_w))\,\cup \, \{y_w\}$ and $y'=y_w$. Then the following hold:

• 1. $G'$ is a connected $(sP_1+P_5)$-free graph;

• 2. $(G',J',y')$ is a cover-complete triple;

• 3. A set $S\subseteq V_G$ is a (smallest) connected vertex cover of G that contains $J\,\cup \, \{w\}$ if and only if $(S\setminus (J\,\cup \, \{w\})\,\cup \, J'$ is a (smallest) connected vertex cover of $G'$ that contains $J'$.

Let (G, J, y) be a cover-complete triple. We define $L_J=N_G(J\setminus \{y\})$. If there is no ambiguity, we will just write $L=L_J$. 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 property (C).

Lemma 4

Let (G, J, y) be a cover-complete triple. If $w_1$ and $w_2$ are two adjacent vertices in L, then no vertex of $J\setminus \{y\}$ is adjacent to both $w_1$ and $w_2$.

We introduce two key definitions. Two vertices $w_1,w_2\in L$ form a pseudo-dominating pair if $w_1$ and $w_2$ are non-adjacent; $w_1$ has a neighbour $x_1\in J$ not adjacent to $w_2$; and $w_2$ has a neighbour $x_2\in J$ not adjacent to $w_1$. Three vertices $w_1,w_2,w_3\in L$ form a pseudo-dominating triple if $w_1$ is adjacent to neither $w_2$ nor $w_3$; $w_2$ and $w_3$ are adjacent; J contains two distinct vertices $x_1$ and $x_2$ such that $x_1\in N_G(w_1)\setminus N_G(\{w_2,w_3\})$ and $x_2\in (N_G(w_1)\cap N_G(w_2))\setminus N_G(w_3)$. See the illustrations in Fig. 3, from which we also observe that no pseudo-dominating pair or pseudo-dominating triple can be found in a $P_5$-free graph.

Fig. 3.

Examples, on the left, of a pseudo-dominating pair $(w_1,w_2)$, and, on the right, of a pseudo-dominating triple $(w_1,w_2,w_3)$. As easily seen, the presence of either implies the existence of at least one induced $P_5$.

Let S be a connected vertex cover of G that contains J. Recall that J is an independent set. A subset $L^*\subseteq L\cap S$ is a connector of S if $J\,\cup \, L^*$ is connected.

Lemma 5

Let (G, J, y) be a cover-complete triple, where G is an $(sP_1+P_5)$-free graph for some $s\ge 0$. Let S be a connected vertex cover of G that contains J. If S contains both vertices of a pseudo-dominating pair $w_1$, $w_2$, then S has a connector of size at most $s+1$ that contains both $w_1$ and $w_2$.

Lemma 6

Let (G, J, y) be a cover-complete triple, where G is an $(sP_1+P_5)$-free graph for some $s\ge 0$. Let S be a connected vertex cover of G that contains J. If S contains all three vertices of a pseudo-dominating triple $w_1,w_2,w_3$, then S has a connector of size at most $s+2$ that contains $\{w_1,w_2,w_3\}$.

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 vertex 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 $(sP_1+P_5)$-free graph for some $s\ge 0$. Then it is possible to compute a smallest connected vertex cover of G that contains y in polynomial time.

Using Lemmas 5–7, we can now prove the following lemma.

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.

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 holds:

• 1. If G is $(sP_1+P_5)$-free and connected, then $G'$ is $(sP_1+P_5)$-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\cap N_{G}(w_1)\cap N_{G}(w_2)$ for some pseudo-dominating pair $(w_1,w_2)$.

Rule 2. For any vertex $w_5\in L$ that is not adjacent to any vertex of a clique of four vertices $w_1,w_2,w_3,w_4$ in L, delete $w_5$ and set-contract via u for every $u\in L\cap N_G(w_5)$.

Lemma 9

Rules 1 and 2 are safe.

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 $(P_1+K_4)$-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 $(sP_1+P_5)$-free and connected, then $G'$ is $(sP_1+P_5)$-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.

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.

Lemma 11

Let (G, J, y) be a free cover-complete triple that has a pseudo-dominating pair $(w_1,w_2)$. Then every minimal connector $L^*$ of every type 2 connected vertex cover S of G has size at most 5.

Lemma 12

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\subseteq L$ with $N_{G}(K)\cap J=J$.

We are now ready to prove the following theorem.

Theorem 3

For every $s\ge 0$, Connected Vertex Cover Completion can be solved in polynomial time for $(sP_1+P_5)$-free graphs.

Proof

Let $s\ge 0$ and let (G, J, y) be a cover-complete triple, where G is an $(sP_1+P_5)$-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 $(sP_1+P_5)$-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. (By guess, we mean choose a set of up to 5 vertices and test to see if they form a minimal connector. We eventually look at all such sets.) If we obtain an instance of the form $(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 11, 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(n^5)$ guesses, we find $S'$ in polynomial time. We compare $S'$ and $S^*$ and choose the smaller of the two.

Now suppose that $G'$ has no pseudo-dominating pair. Let $L'=N_{G'}(J'\setminus \{y'\})$. By Lemma 12, we can obtain in polynomial time a clique $K\subseteq L'$ with $N_{G'}(K)\cap J'=J'$. Let $K=\{w_1,\ldots ,w_r\}$ for some $r\ge 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'\,\cup \, K$, and then we will find in polynomial time, for $i=1,\ldots ,r$, a smallest connected vertex cover of $G'$ that contains $J'\,\cup \, (K\setminus \{w_i\})$ and that does not contain $w_i$. 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'\,\cup \, 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 $S_K$ of $G'$ that contains $J'\,\cup \, K$.

We now show how to compute, in polynomial time, a smallest connected vertex cover of $G'$ that contains $J'\,\cup \, (K\setminus \{w_1\})$ and that does not contain $w_1$. The case $i\ge 2$ is done in the same way.

Let $A=L'\setminus N_{G'}(w_1)$ consist of all non-neighbours of $w_1$ in $L'$. As $G'[L']$ is $(K_4+P_1)$-free by definition, we find that $G'[A]$ is $K_4$-free. As $w_1$ is not in the connected vertex cover we are looking for we remove $w_1$, and we set-contract via each neighbour of $w_1$ in L. By Lemma 3, we may now consider the resulting cover-complete triple $(G'',J'',y'')$ where $G''$ is connected and $(sP_1+P_5)$-free. As $G'$ had no pseudo-dominating pairs, we have that $G''$ has no pseudo-dominating pairs. We write $L''=N_{G''}(J''\setminus \{y''\})$. As $L''\subseteq A$, we find that $G''[L'']$ is $K_4$-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 $K_4$-free. Suppose instead that $L^*$ is not a clique. Then $L^*$ contains two non-adjacent vertices $w_1$ and $w_2$. As $L^*$ is a minimal connector, $w_1$ has a neighbour in $J''$ not adjacent to $w_2$, and vice versa. But then $(w_1,w_2)$ is a pseudo-dominating 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 $S_{w_1}$ of $G'$ that contains $J'\,\cup \, (K\setminus \{w_1\})$ and that does not contain $w_1$.

As mentioned, we pick the smallest one out of the connected vertex covers $S_K$ and $S_{w_i}$, $1\le i\le 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.    $\square$

4 Our Main Result

In this section we prove Theorem 2. We need two more lemmas (we use Lemma 2 to prove the first one).

Lemma 13

Let $s\ge 0$ and let G be a connected $(sP_1+P_5)$-free graph. Then G has a connected dominating set D that is either a clique or has size at most $2s^2+s+3$. Moreover, D can be found in $O(n^{2s^2+s+3})$ time.

Lemma 14

Let J be an independent set in 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\setminus \{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\setminus J'$ is a connected vertex cover of $G-J'$ that contains $J\setminus J'$.

We are now ready to prove our main result.

Theorem 2 (Restated). For every $s\ge 0$, Connected Vertex Cover can be solved in polynomial time for $(sP_1+P_5$)-free graphs.

Proof

Let G be an $(sP_1+P_5)$-free graph for some $s\ge 0$. We may assume without loss of generality that G is connected. By Lemma 13 we can first compute in $O(n^{2s^2+s+3})$ time a connected dominating set D that either has size at most $2s^2+s+3$ or is a clique. We note that, if D is a clique, any vertex cover of G contains all but at most one vertex of D. This leads to a case analysis where we guess the subset $D^*\subseteq D$ of vertices not in a minimum connected vertex cover of G. Because $|D^*|\le 2s^2+s+3$, the number of guesses is polynomial. For each guess of $D^*$, we compute a smallest connected vertex cover $S_{D^*}$ that contains all vertices of $D\setminus D^*$ and no vertex of $D^*$. Then, in the end, we return one that has minimum size overall.

Let $D^*$ be a guess. We first show the following claim (proof omitted).

Claim 1

We may assume without loss of generality that $D\setminus D^*$ is connected.

Case 1. $D^*=\emptyset$.

We compute a minimum vertex cover $S'$ of $G-D$ in polynomial time by Theorem 1. Clearly $S'\,\cup \, D$ is a vertex cover of G. As D is a connected dominating set, $S'\,\cup \, D$ is a connected vertex cover of G. Let $S_\emptyset =S'\,\cup \, D$. As $S'$ is a minimum vertex cover of $G-D$, $S_\emptyset$ is a smallest connected vertex cover of G that contains all vertices of D. We remember $S_\emptyset$, which we found in polynomial time.

Case 2. $1\le |D^*|\le |D|$ (recall that $|D|\le 2s^2+s+3$).

Recall that we are looking for a smallest connected vertex cover of G that contains every vertex of $D\setminus 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 $N_G(D^*)$. Hence we can safely contract not only any edge between two vertices of $D\setminus D^*$, but also any edge between two vertices in $N_G(D^*)$ or between a vertex of $D\setminus D^*$ and a vertex in $N_G(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\setminus D^*$ in G corresponds to exactly one vertex of $G^*$. We denote this vertex by y. We observe the following equivalence.

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\setminus 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 $(sP_1+P_5)$-free, $G^*$ is connected and $(sP_1+P_5)$-free as well by Lemma 1.

We write $J^*=N_{G^*}(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. 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\setminus 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\setminus D^*$, is adjacent to every vertex of $(G^*-D^*)-J^*$ in the graph $G^*-D^*$.

Let $J\subseteq 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^*\setminus J$, we can apply Lemma 14 and remove $J^*\setminus J$. That is, it suffices to find a smallest connected vertex cover of the graph $G'=(G^*-D^*)-(J^*\setminus 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\in 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 \setminus \{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^*\setminus J$ to $S'$. We translate $S^*$ in polynomial time into a smallest connected vertex cover $S_{D^*}$ 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 $S_{D^*}$. 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 $n^{O(s^3)}$. The running time is dominated by obtaining a connected $D \setminus D^*$ (in Claim 1). As $D \setminus D^*$ has $O(n^{2s^2+s+3})$ components and the paths required to join them each have O(s) vertices, the time required to find them is $n^{O(s^3)}$. The correctness of our algorithm follows immediately from the above case analysis and the description of the cases.    $\square$

5 Future Work

We pose two open problems. First, determine the complexity of Connected Vertex Cover for $P_6$-free graphs. Second, is there an integer r such that Connected Vertex Cover is NP-complete for $P_r$-free graphs?