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

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

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
• Public URL: https://durham-repository.worktribe.com/output/1294673