l-path vertex cover is easier than l-hitting set for small l

Abstract

In the $l$-path vertex cover problem the input is an undirected graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that $G-S$ does not contain a path with $l$ vertices. In this paper we give parameterized algorithms for $l$-path vertex cover for $l=5,6,7$, whose time complexities are $O^{\ast }(3.945^k)$, $O^{\ast }(4.947^k)$, and $O^{\ast }(5.951^k)$, respectively.

arXiv admin note: text overlap with arXiv:1901.07609