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.IPEC.2022.19
URN: urn:nbn:de:0030-drops-173758
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17375/
Go to the corresponding LIPIcs Volume Portal

Kellerhals, Leon ; Koana, Tomohiro ; Kunz, Pascal

Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

pdf-format:
LIPIcs-IPEC-2022-19.pdf (0.8 MB)

Abstract

Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several lower bounds on k are well-known, such as the maximum size of a matching. This has led to a line of research on parameterizations of Vertex Cover by the difference of the solution size k and a lower bound. The most prominent cases for such lower bounds for which the problem is FPT are the matching number or the optimal fractional LP solution. We investigate parameterizations by the difference between k and other graph parameters including the feedback vertex number, the degeneracy, cluster deletion number, and treewidth with the goal of finding the border of fixed-parameter tractability for said difference parameterizations. We also consider similar parameterizations of the Feedback Vertex Set problem.

BibTeX - Entry

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2022.19,
  author =	{Kellerhals, Leon and Koana, Tomohiro and Kunz, Pascal},
  title =	{{Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17375},
  URN =		{urn:nbn:de:0030-drops-173758},
  doi =		{10.4230/LIPIcs.IPEC.2022.19},
  annote =	{Keywords: parameterized complexity, vertex cover, feedback vertex set, above guarantee parameterization}
}

Keywords: parameterized complexity, vertex cover, feedback vertex set, above guarantee parameterization
Collection: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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