Vertex Cover at Distance on H-Free Graphs

The question of characterizing graphs H such that the VERTEX COVER problem is solvable in polynomial time in the class of H-free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distance-based generalization of vertex cover called distance-k vertex cover, for any positive integer k. In this problem the task is to determine, given a graph G and an integer l, whether G contains a set of at most l vertices such that each edge of G is at distance at most k from a vertex in the set. We show that for all k >= 1 and all graphs H, the distance-k vertex cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of P2k+2 + sP(max{k,2}) for some s >= 0, and NP-complete otherwise.