An O^*(2.619^k) algorithm for 4-path vertex cover
classification
💻 cs.DS
keywords
pathvertexcoveralgorithmverticescomplexitycontainsdecide
read the original 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^*(2.619^k)$.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
l-path vertex cover is easier than l-hitting set for small l
Gives FPT algorithms for l-path vertex cover achieving bases 3.945, 4.947 and 5.951 for l=5,6,7.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.