Reducing Graph Transversals via Edge Contractions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2020

Reducing Graph Transversals via Edge Contractions


For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k, d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters 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, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2020-64.pdf (853.56 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02991812 , version 1 (06-11-2020)





Paloma T. Lima, Vinicius Fernandes dos Santos, Ignasi Sau, Uéverton dos Santos Souza. Reducing Graph Transversals via Edge Contractions. MFCS 2020 - 45th International Symposium on Mathematical Foundations of Computer Science, Aug 2020, Prague, Czech Republic. pp.64:1-64:15, ⟨10.4230/LIPIcs.MFCS.2020.64⟩. ⟨lirmm-02991812⟩
35 View
78 Download



Gmail Facebook X LinkedIn More