We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Connected vertex cover for (sP1+P5)-free graphs.

Johnson, M. and Paesani, G. and Paulusma, D. (2020) 'Connected vertex cover for (sP1+P5)-free graphs.', Algorithmica., 82 (1). pp. 20-40.


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 s P2-free graphs for any integer s ≥ 1. We give a polynomial-time algorithm to solve the problem for (s P1 + P5)-free graphs for every integer s ≥ 0. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at:
Date accepted:12 June 2019
Date deposited:13 June 2019
Date of first online publication:20 June 2019
Date first made open access:20 June 2020

Save or Share this output

Look up in GoogleScholar