License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.43
URN: urn:nbn:de:0030-drops-57448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5744/
Hols, Eva-Maria C. ;
Kratsch, Stefan
A Randomized Polynomial Kernel for Subset Feedback Vertex Set
Abstract
The SUBSET FEEDBACK VERTEX SET problem generalizes the classical FEEDBACK VERTEX SET problem and asks, for a given undirected graph G=(V,E), a set S subseteq V, and an integer k, whether there exists a set X of at most k vertices such that no cycle in G-X contains a vertex of S. It was independently shown by Cygan et al. (ICALP'11, SIDMA'13) and Kawarabayashi and Kobayashi (JCTB'12) that SUBSET FEEDBACK VERTEX SET is fixed-parameter tractable for parameter k. Cygan et al. asked whether the problem also admits a polynomial kernelization.
We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where S is a set of edges. In a first step we show that EDGE SUBSET FEEDBACK VERTEX SET has a randomized polynomial kernel parameterized by |S|+k with O(|S|^2k) vertices. For this we use the matroid-based tools of Kratsch and Wahlstrom (FOCS'12). Next we present a preprocessing that reduces the given instance (G,S,k) to an equivalent instance (G',S',k') where the size of S' is bounded by O(k^4). These two results lead to a polynomial kernel for SUBSET FEEDBACK VERTEX SET with O(k^9) vertices.
BibTeX - Entry
@InProceedings{hols_et_al:LIPIcs:2016:5744,
author = {Eva-Maria C. Hols and Stefan Kratsch},
title = {{A Randomized Polynomial Kernel for Subset Feedback Vertex Set}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {43:1--43:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5744},
URN = {urn:nbn:de:0030-drops-57448},
doi = {10.4230/LIPIcs.STACS.2016.43},
annote = {Keywords: parameterized complexity, kernelization, subset feedback vertex set}
}
Keywords: |
|
parameterized complexity, kernelization, subset feedback vertex set |
Collection: |
|
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
16.02.2016 |