2026-07-22T08:36:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16867 2024-03-06T10:58:32Z ddc:004 open_access

Reducing the Vertex Cover Number via Edge Contractions Lima, Paloma T. dos Santos, Vinicius F. Sau, Ignasi Souza, Uéverton S. Tale, Prafullkumar Blocker problems edge contraction vertex cover parameterized complexity 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paloma T. Lima and Vinicius F. dos Santos and Ignasi Sau and Uéverton S. Souza and Prafullkumar Tale 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.69 urn:nbn:de:0030-drops-168671 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.69 eng https://creativecommons.org/licenses/by/4.0/legalcode