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

Lima, Paloma T. ; dos Santos, Vinicius F. ; Sau, Ignasi ; Souza, Uéverton S. ; Tale, Prafullkumar

Reducing the Vertex Cover Number via Edge Contractions

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

Abstract

The Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results:
- Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative.
- It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem.
- Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).

BibTeX - Entry

@InProceedings{lima_et_al:LIPIcs.MFCS.2022.69,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S. and Tale, Prafullkumar},
  title =	{{Reducing the Vertex Cover Number via Edge Contractions}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{69:1--69: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/16867},
  URN =		{urn:nbn:de:0030-drops-168671},
  doi =		{10.4230/LIPIcs.MFCS.2022.69},
  annote =	{Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}

Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity
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