Skip to main content

Research Repository

Advanced Search

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

Johnson, M.; Paesani, G.; Paulusma, D.

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


G. Paesani


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.


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

Journal Article Type Article
Acceptance Date Jun 12, 2019
Online Publication Date Jun 20, 2019
Publication Date Jan 31, 2020
Deposit Date Jun 12, 2019
Publicly Available Date Jun 20, 2020
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 82
Issue 1
Pages 20-40


You might also like

Downloadable Citations