Reducing the vertex cover number via edge contractions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Journal of Computer and System Sciences Année : 2023

Reducing the vertex cover number via edge contractions

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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 Consultations
25 Téléchargements

Altmetric

Partager

More