Document Open Access Logo

A Randomized Polynomial Kernel for Subset Feedback Vertex Set

Authors Eva-Maria C. Hols, Stefan Kratsch

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2016.43.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • parameterized complexity
  • kernelization
  • subset feedback vertex set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Eva-Maria C. Hols and Stefan Kratsch. A Randomized Polynomial Kernel for Subset Feedback Vertex Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.43

Author Details

Eva-Maria C. Hols
Stefan Kratsch

References

  1. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The undirected feedback vertex set problem has a poly(k) kernel. In IWPEC 2006, volume 4169 of LNCS, pages 192-202. Springer, 2006. URL: http://dx.doi.org/10.1007/11847250_18.
  2. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS 2011, pages 150-159. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  3. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math., 27(1):290-309, 2013. URL: http://dx.doi.org/10.1137/110843071.
  4. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23:1-23:27, 2014. URL: http://dx.doi.org/10.1145/2629620.
  5. Reinhard Diestel. Graph theory. Graduate texts in mathematics, 2005. Google Scholar
  6. Guy Even, Joseph Naor, and Leonid Zosin. An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput., 30(4):1231-1252, 2000. URL: http://dx.doi.org/10.1137/S0097539798340047.
  7. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In SODA 2014, pages 142-151. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.10.
  8. Tibor Gallai. Maximum-minimum sätze und verallgemeinerte faktoren von graphen. Acta Mathematica Hungarica, 12(1-2):131-173, 1961. Google Scholar
  9. Eva-Maria C. Hols and Stefan Kratsch. A randomized polynomial kernel for subset feedback vertex set. CoRR, abs/1512.02510, 2015. URL: http://arxiv.org/abs/1512.02510.
  10. Ken-ichi Kawarabayashi and Yusuke Kobayashi. Fixed-parameter tractability for the subset feedback set problem and the s-cycle packing problem. J. Comb. Theory, Ser. B, 102(4):1020-1034, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.12.001.
  11. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. URL: http://dx.doi.org/10.1016/j.ipl.2014.05.001.
  12. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In FOCS 2012, pages 450-459. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.46.
  13. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. In ICALP 2015, volume 9134 of LNCS, pages 935-946. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_76.
  14. László Lovász. Flats in matroids and geometric graphs. Combinatorial surveys, pages 45-86, 1977. Google Scholar
  15. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.07.027.
  16. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms, 9(4):30, 2013. URL: http://dx.doi.org/10.1145/2500119.
  17. Hazel Perfect. Applications of Menger’s graph theorem. J. Math. Anal. Appl., 22:96-111, 1968. Google Scholar
  18. Alexander Schrijver. A short proof of Mader’s sigma-paths theorem. J. Comb. Theory, Ser. B, 82(2):319-321, 2001. URL: http://dx.doi.org/10.1006/jctb.2000.2029.
  19. Stéphan Thomassé. A 4k^2 kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2), 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
  20. Po Tong, Eugene L. Lawler, and Vijay V. Vazirani. Solving the weighted parity problem for gammoids by reduction to graphic matching. Computer Science Division, University of California, 1982. Google Scholar
  21. Magnus Wahlström. Half-integrality, lp-branching and FPT algorithms. In SODA 2014, pages 1762-1781. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.128.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact