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 prove that it is also polynomial-time solvable for (sP1+ P5) -free graphs for every integer s≥0.
Connected vertex cover for (sP1+ P5) -Free graphs / Johnson, M.; Paesani, G.; Paulusma, D.. - 11159:(2018), pp. 279-291. ( International Workshop on Graph-Theoretic Concepts in Computer Science Cottbus, Germania ) [10.1007/978-3-030-00256-5_23].
Connected vertex cover for (sP1+ P5) -Free graphs
Paesani G.;
2018
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 prove that it is also polynomial-time solvable for (sP1+ P5) -free graphs for every integer s≥0.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
