Reducing the Vertex Cover Number via Edge Contraction - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2022

Reducing the Vertex Cover Number via Edge Contraction


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).
Fichier principal
Vignette du fichier
VC-MFCS-camera-ready.pdf (828.93 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03772619 , version 1 (08-09-2022)



Paloma T. Lima, Vinicius Fernandes dos Santos, Ignasi Sau, Uéverton dos Santos Souza, Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contraction. MFCS 2022 - 47th International Symposium on Mathematical Foundations of Computer Science, Aug 2022, Vienna, Austria. pp.69:1-69:14, ⟨10.4230/LIPIcs.MFCS.2022.69⟩. ⟨lirmm-03772619⟩
30 View
49 Download



Gmail Facebook X LinkedIn More