On Kernels for d-Path Vertex Cover

2021/07/26 by Červený, Radovan, Choudhary, Pratibha, Suchý, Ondřej
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2107.12245

Abstract

In this paper we study the kernelization of the 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) with d vertices. It is known that d-PVC is NP-complete for d≥ 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k²) vertices and edges for the cases when d=4 and d=5. Further, we give a kernel with O(k⁴d^2d+9) vertices and edges for general d.

Related

• Faster FPT Algorithm for 5-Path Vertex Cover
• Linear-Vertex Kernel for the Problem of Packing r-Stars into a Graph without Long Induced Paths
• Generating faster algorithms for d-Path Vertex Cover
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Towards optimal kernel for connected vertex cover in planar graphs