 License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-168671
URL:

; ; ; ;

### Reducing the Vertex Cover Number via Edge Contractions

 pdf-format:

### 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-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},
DROPS-Home | Fulltext Search | Imprint | Privacy 