Lima, Paloma T. ;
dos Santos, Vinicius F. ;
Sau, Ignasi ;
Souza, Uéverton S. ;
Tale, Prafullkumar
Reducing the Vertex Cover Number via Edge Contractions
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 socalled 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 NPhard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yesinstance 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 nonexplicit 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:169:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16867},
URN = {urn:nbn:de:0030drops168671},
doi = {10.4230/LIPIcs.MFCS.2022.69},
annote = {Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}
22.08.2022
Keywords: 

Blocker problems, edge contraction, vertex cover, parameterized complexity 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 