Skip to Main content Skip to Navigation
New interface
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 : Thursday, October 6, 2022 - 9:32:06 AM
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 T. Lima, Vinicius Fernandes dos Santos, Ignasi Sau Valls, 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⟩



Record views


Files downloads