We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

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

Author(s) from Durham


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≥1

. We give a polynomial-time algorithm to solve the problem for (sP 1 +P 5 )

  • free graphs for every integer s≥ 0

s≥ 0
. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.