Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03374537
Contributor : Ignasi Sau Connect in order to contact the contributor
Submitted on : Tuesday, October 12, 2021 - 10:56:19 AM
Last modification on : Wednesday, October 13, 2021 - 3:39:05 AM

File

Contractions-JCSS.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

8

Files downloads

2