On Kernels for d-Path Vertex Cover
Authors
Červený, R.; Choudhary, P.; Suchý, O.
Year
2022
Published
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2022. p. 29:1-29:14. Leibniz International Proceedings in Informatics (LIPIcs). vol. 241. ISSN 1868-8969. ISBN 978-3-95977-256-3.
Type
Proceedings paper
Departments
Annotation
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^2) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with O(k^4d^{2d+9}) vertices and edges for general d.
Faster FPT algorithm for 5-path vertex cover
Authors
Červený, R.; Suchý, O.
Year
2019
Published
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 32:1-32:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 138. ISSN 1868-8969. ISBN 978-3-95977-117-7.
Type
Proceedings paper
Departments
Annotation
The problem of \textsc{$d$-Path Vertex Cover, $d$-PVC} lies in determining a subset~$F$ of vertices of a~given graph $G=(V,E)$ such that $G \setminus F$ does not contain a~path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the \textsc{$d$-PVC} problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, \textsc{5-PVC} has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since \textsc{$d$-PVC} is a special case of \textsc{$d$-Hitting Set}, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the \textsc{5-PVC} problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.