On Kernels for d-Path Vertex Cover

In this paper we study the kernelization of $d$-Path Vertex Cover ($d$-PVC) problem. Given a graph $G$, the problem requires finding whether there exists a set of at most $k$ vertices whose removal from $G$ results in a graph that does not contain a path (not necessarily induced) of length $d$. It is known that $d$-PVC is NP-complete for $d \geq 2$. Since the problem generalizes to $d$-Hitting Set, it is known to admit a kernel of size $(2d-1)k^{d-1}+k$. We improve on this by giving better kernels. Specifically, we give $O(k^2)$ size (vertices and edges) kernels for the cases when $d = 4$ and $d = 5$. Further, we give an $O(k^3)$ size kernel for $d$-PVC.