Differences

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

Link to this comparison view

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.
  
  

Page Tools