2026-08-11T03:30:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12734 2024-03-06T10:50:41Z ddc:004 open_access

Reducing Graph Transversals via Edge Contractions Lima, Paloma T. dos Santos, Vinicius F. Sau, Ignasi Souza, Uéverton S. blocker problem edge contraction graph transversal parameterized complexity vertex cover feedback vertex set odd cycle transversal 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 ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paloma T. Lima and Vinicius F. dos Santos and Ignasi Sau and Uéverton S. Souza 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.64 urn:nbn:de:0030-drops-127346 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.64 eng https://creativecommons.org/licenses/by/3.0/legalcode