Reducing the vertex cover number via edge contractions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Computer and System Sciences Year : 2023

Reducing the vertex cover number via edge contractions

Abstract

Given a graph G on n vertices and two integers k and d, the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(vc) admits an XP algorithm running in time f (d) • n O(d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) 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. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(vc) is NP-hard even when k = d. (iii) Contraction(vc) can be solved in time 2 O(d) • n k−d+O(1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k = d, Contraction(vc) is FPT parameterized by d (or by k).
Fichier principal
Vignette du fichier
VC-long.pdf (1.2 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04107607 , version 1 (26-05-2023)

Identifiers

Cite

Paloma Thomé de Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton dos Santos Souza, Prafullkumar Tale. Reducing the vertex cover number via edge contractions. Journal of Computer and System Sciences, 2023, 136, pp.63-87. ⟨10.1016/j.jcss.2023.03.003⟩. ⟨lirmm-04107607⟩
36 View
21 Download

Altmetric

Share

More