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 sP2-free graphs for any integer s≥ 1. We give a polynomial-time algorithm to solve the problem for (sP1+ P5) -free graphs for every integer s≥0. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.
Connected Vertex Cover for (sP1+ P5) -Free Graphs / Johnson, M.; Paesani, G.; Paulusma, D.. - In: ALGORITHMICA. - ISSN 0178-4617. - 82:1(2020), pp. 20-40. [10.1007/s00453-019-00601-9]
Connected Vertex Cover for (sP1+ P5) -Free Graphs
Paesani G.;
2020
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 sP2-free graphs for any integer s≥ 1. We give a polynomial-time algorithm to solve the problem for (sP1+ P5) -free graphs for every integer s≥0. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
