Reducing graph transversals via edge contractions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Computer and System Sciences Year : 2021

Reducing graph transversals via edge contractions

Abstract

For a graph invariant π, the Contraction(π) problem consists of, given a graph G and positive integers k, d, deciding whether one can contract k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] studied the case where π is the size of a minimum dominating set. We focus on graph invariants defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, in particular implying that Contraction(π) is co-NP-hard for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.
Fichier principal
Vignette du fichier
Contractions-JCSS.pdf (893.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03374537 , version 1 (12-10-2021)

Identifiers

Cite

Paloma T Lima, Vinicius F dos Santos, Ignasi Sau, Uéverton S Souza. Reducing graph transversals via edge contractions. Journal of Computer and System Sciences, 2021, 120, pp.62-74. ⟨10.1016/j.jcss.2021.03.003⟩. ⟨lirmm-03374537⟩
25 View
39 Download

Altmetric

Share

Gmail Facebook X LinkedIn More