This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | |||

research:workshop2016 [2016/12/07 17:05] etscheid |
research:workshop2016 [2016/12/07 17:06] (current) etscheid |
||
---|---|---|---|

Line 140: | Line 140: | ||

The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph G=(V,E), a subset S of 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. | The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph G=(V,E), a subset S of 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. In a first step we show that 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 Wahlström (FOCS '12) that for example were used to obtain a polynomial kernel for s-Multiway Cut. 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. | + | We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization. In a first step we show that Subset Feedback Vertex Set has a randomized polynomial kernel parameterized by |S|+k with O(|S|² * k) vertices. For this we use the matroid-based tools of Kratsch and Wahlström (FOCS '12) that for example were used to obtain a polynomial kernel for s-Multiway Cut. 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. |