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

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

doi:10.1007/s00453-019-00601-9

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

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

Authors

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

G. Paesani

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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 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.

Citation

Johnson, M., Paesani, G., & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica, 82(1), 20-40. https://doi.org/10.1007/s00453-019-00601-9

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
DOI	https://doi.org/10.1007/s00453-019-00601-9

Files

Accepted Journal Article (397 Kb)
PDF

Copyright Statement
This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-019-00601-9