Document Open Access Logo

Linear-Time Kernelization for Feedback Vertex Set

Author Yoichi Iwata

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.68.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Yoichi Iwata

Cite As Get BibTex

Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.68

Abstract

In this paper, we give an algorithm that, given an undirected graph G of m edges and an integer k, computes a graph G' and an integer k' in O(k^4 m) time such that (1) the size of the graph G' is O(k^2), (2) k' \leq k, and (3) G has a feedback vertex set of size at most k if and only if G' has a feedback vertex set of size at most k'. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is 2k^2+k vertices and 4k^2 edges, which is smaller than the previous best of 4k^2 vertices and 8k^2 edges. Thus, we improve the size and the running time simultaneously. We note that under the assumption of NP \not\subseteq coNP/poly, Feedback Vertex Set does not admit an O(k^{2-\epsilon})-size kernel for any \epsilon>0.

Our kernel exploits k-submodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of k-submodular relaxation of Feedback Vertex Set can be seen as a half-integral variant of A-path packing, and to obtain the linear-time complexity, we give an efficient augmenting-path algorithm for this problem. We believe that this combinatorial algorithm is of independent interest.

A solver based on the proposed method won first place in the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge.

Subject Classification

Keywords
  • FPT Algorithms
  • Kernelization
  • Path Packing
  • Half-integrality

Metrics

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

References

  1. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289-297, 1999. Google Scholar
  2. Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res., 12:219-234, 2000. Google Scholar
  3. Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167-188, 1996. Google Scholar
  4. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  5. Hans L. Bodlaender and Thomas C. van Dijk. A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst., 46(3):566-597, 2010. Google Scholar
  6. 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, pages 192-202, 2006. Google Scholar
  7. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73(1):63-86, 2015. Google Scholar
  8. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. Google Scholar
  9. Benny Chor, Mike Fellows, and David W. Juedes. Linear kernels in linear time, or how to save k colors in O(n²) steps. In WG 2004, pages 257-269, 2004. Google Scholar
  10. 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, 2011. Google Scholar
  11. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An O(2^O(k)n³) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst., 41(3):479-492, 2007. Google Scholar
  12. 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. Google Scholar
  13. Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness. In Complexity Theory: Current Research, pages 191-225, 1992. Google Scholar
  14. Michael Etscheid and Matthias Mnich. Linear kernels and linear-time algorithms for finding large cuts. In ISAAC 2016, pages 31:1-31:13, 2016. Google Scholar
  15. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci., 72(8):1386-1396, 2006. Google Scholar
  16. Torben Hagerup. Simpler linear-time kernelization for planar dominating set. In IPEC 2011, pages 181-193, 2011. Google Scholar
  17. Yoichi Iwata. Linear-time kernelization for feedback vertex set. CoRR, abs/1608.01463, 2016. Full version of this paper. URL: https://arxiv.org/abs/1608.01463.
  18. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In SODA 2014, pages 1749-1761, 2014. Google Scholar
  19. Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, LP-branching and FPT algorithms. SIAM J. Comput., 45(4):1377-1411, 2016. Google Scholar
  20. Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. Linear-time FPT algorithms via half-integral non-returning A-path packing. CoRR, abs/1704.02700, 2017. Google Scholar
  21. Iyad A. Kanj, Michael J. Pelsmajer, and Marcus Schaefer. Parameterized algorithms for feedback vertex set. In IWPEC 2004, pages 235-247, 2004. Google Scholar
  22. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  23. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. Google Scholar
  24. G. Nemhauser and L. Trotter. Vertex Packing: Structural Properties and Algorithms. Math. Program., 8:232-248, 1975. Google Scholar
  25. Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Paths, flowers and vertex cover. In ESA 2011, pages 382-393, 2011. Google Scholar
  26. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Trans. Algorithms, 2(3):403-415, 2006. Google Scholar
  27. M. S. Ramanujan and Saket Saurabh. Linear time parameterized algorithms via skew-symmetric multicuts. In SODA 2014, pages 1739-1748, 2014. Google Scholar
  28. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2), 2010. Google Scholar
  29. René van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129-147, 2014. Google Scholar
  30. René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, and Mathias Weller. Linear-time computation of a linear problem kernel for dominating set on planar graphs. In IPEC 2011, pages 194-206, 2011. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact