文章基本信息

标题：Reducing Graph Transversals via Edge Contractions
本地全文：下载
作者：Paloma T. Lima ; Vinicius F. dos Santos ; Ignasi Sau 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：64:1-64:15
DOI：10.4230/LIPIcs.MFCS.2020.64
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：blocker problem; edge contraction; graph transversal; parameterized complexity; vertex cover; feedback vertex set; odd cycle transversal