dc.contributor.author | Lima, Paloma T. | |
dc.contributor.author | dos Santos, Vinicius F. | |
dc.contributor.author | Sau, Ignasi | |
dc.contributor.author | Souza, Uéverton S. | |
dc.date.accessioned | 2021-06-07T11:31:49Z | |
dc.date.available | 2021-06-07T11:31:49Z | |
dc.date.created | 2020-09-22T16:31:28Z | |
dc.date.issued | 2020 | |
dc.Published | Leibniz International Proceedings in Informatics. 2020, 170:64 1-15. | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2758197 | |
dc.description.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 ℋ 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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl, Leibniz-Zentrum für Informatik | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Reducing Graph Transversals via Edge Contractions | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza | en_US |
dc.source.articlenumber | 64 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.MFCS.2020.64 | |
dc.identifier.cristin | 1832261 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.40 | 170:64 | |
dc.source.pagenumber | 1-15 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2020, 170, 1-15, 64. | en_US |
dc.source.volume | 170 | en_US |