Skip to Main content Skip to Navigation
Conference papers

Reducing Graph Transversals via Edge Contractions

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Friday, November 6, 2020 - 10:35:38 AM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Sunday, February 7, 2021 - 6:30:19 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




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



Record views


Files downloads