Faster parameterized algorithms for two vertex deletion problems

In the l-PATH VERTEX COVER problem (resp., the l-COMPONENT ORDER CONNECTIVITY problem) the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices of size at most k whose deletion from G results in a graph that does not contain a path with l vertices (resp., does not contain a connected component with at least l vertices). In this paper we give a parameterized algorithm for l-PATH VERTEX COVER when l = 5, 6, 7, whose running times are O*(3.945k), O*(4.947k), and O*(5.951k), respectively. We also give an algorithm for l-COMPONENT ORDER CONNECTIVITY whose running time is O *((l - 1 - El)k) for every l > 4, where El > 0 for every l. (c) 2022 Elsevier B.V. All rights reserved.