An O^*(2.619^k) algorithm for 4-path vertex cover

Abstract

In the 4-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 every path with 4 vertices in $G$ contains at least one vertex of $S$. In this paper we give a parameterized algorithm for 4-path vertex cover whose time complexity is $O^{\ast }(2.619^k)$.

References in corpus (1)

• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover

Cited by in corpus (1)

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