2026-07-23T06:32:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16827 2024-03-06T10:58:26Z ddc:004 open_access

On Kernels for d-Path Vertex Cover Červený, Radovan Choudhary, Pratibha Suchý, Ondřej Parameterized complexity Kernelization d-Hitting Set d-Path Vertex Cover Expansion Lemma 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 𝒪(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with 𝒪(k²) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with 𝒪(k⁴d^{2d+9}) vertices and edges for general d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radovan Červený and Pratibha Choudhary and Ondřej Suchý 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.29 urn:nbn:de:0030-drops-168279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.29 eng https://creativecommons.org/licenses/by/4.0/legalcode