License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.29
URN: urn:nbn:de:0030-drops-168279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16827/
Go to the corresponding LIPIcs Volume Portal

Červený, Radovan ; Choudhary, Pratibha ; Suchý, Ondřej

On Kernels for d-Path Vertex Cover

pdf-format:
LIPIcs-MFCS-2022-29.pdf (0.9 MB)

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 ?(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.

BibTeX - Entry

@InProceedings{cerveny_et_al:LIPIcs.MFCS.2022.29,
  author =	{\v{C}erven\'{y}, Radovan and Choudhary, Pratibha and Such\'{y}, Ond\v{r}ej},
  title =	{{On Kernels for d-Path Vertex Cover}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16827},
  URN =		{urn:nbn:de:0030-drops-168279},
  doi =		{10.4230/LIPIcs.MFCS.2022.29},
  annote =	{Keywords: Parameterized complexity, Kernelization, d-Hitting Set, d-Path Vertex Cover, Expansion Lemma}
}

Keywords: Parameterized complexity, Kernelization, d-Hitting Set, d-Path Vertex Cover, Expansion Lemma
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI