Document Open Access Logo

Improved FPT Algorithms for Deletion to Forest-Like Structures

Authors Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.34.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Kishen N. Gowda
  • IIT Gandhinagar, India
Aditya Lonkar
  • IIT Madras, India
Fahad Panolan
  • Department of Computer Science and Engineering, IIT Hyderabad, India
Vraj Patel
  • IIT Gandhinagar, India
Saket Saurabh
  • Institute of Mathematical Sciences, Chennai, India

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 819416) and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Cite AsGet BibTex

Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh. Improved FPT Algorithms for Deletion to Forest-Like Structures. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.34

Abstract

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V(G) of size at most k such that G-S is a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed a randomized algorithm for the problem running in time 𝒪^⋆(2.7^k). In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G-S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k,𝓁 ∈ ℕ, and the objective is to test whether there exists a vertex subset S of size at most k, such that G-S is 𝓁 edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algorithms for all these problems. In particular we obtain following randomized algorithms. 1) Independent Feedback Vertex Set can be solved in time 𝒪^⋆(2.7^k). 2) Pseudo Forest Deletion can be solved in time 𝒪^⋆(2.85^k). 3) Almost Forest Deletion can be solved in 𝒪^⋆(min{2.85^k ⋅ 8.54^𝓁, 2.7^k ⋅ 36.61^𝓁, 3^k ⋅ 1.78^𝓁}).

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Independent Feedback Vertex Set
  • PseudoForest
  • Almost Forest
  • Cut and Count
  • Treewidth

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma. Improved algorithms and combinatorial bounds for independent feedback vertex set. In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63, pages 2:1-2:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  2. Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous feedback vertex set: A parameterized perspective. TOCT, 10(4):18:1-18:25, 2018. Google Scholar
  3. 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
  4. Hans L. Bodlaender. On disjoint cycles. In Gunther Schmidt and Rudolf Berghammer, editors, WG '91, volume 570 of LNCS, pages 230-238. Springer, 1992. Google Scholar
  5. Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A faster parameterized algorithm for pseudoforest deletion. Discret. Appl. Math., 236:42-56, 2018. URL: https://doi.org/10.1016/j.dam.2017.10.018.
  6. Yixin Cao. A naive algorithm for feedback vertex set. In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA, volume 61, pages 1:1-1:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. 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. 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 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159. IEEE Computer Society, 2011. 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. CoRR, abs/1103.0534, 2011. URL: http://arxiv.org/abs/1103.0534.
  11. 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. Google Scholar
  12. 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
  13. Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness. In Complexity Theory: Current Research, pages 191-225. Cambridge University Press, 1992. Google Scholar
  14. Paola Festa, Panos M. Pardalos, and Mauricio G.C. Resende. Feedback set problems. In Handbook of Combinatorial Optimization, pages 209-258. Kluwer Academic Publishers, 1999. Google Scholar
  15. Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh. Improved fpt algorithms for deletion to forest-like structures, 2020. URL: http://arxiv.org/abs/2009.13949.
  16. 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
  17. Yoichi Iwata and Yusuke Kobayashi. Improved analysis of highest-degree branching for feedback vertex set. In 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, pages 22:1-22:11, 2019. Google Scholar
  18. 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
  19. Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. 0/1/all CSPs, half-integral a-path packing, and linear-time FPT algorithms. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 462-473. IEEE Computer Society, 2018. Google Scholar
  20. 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. Google Scholar
  21. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discrete Math., 23:407-427, January 2009. URL: https://doi.org/10.1137/080715482.
  22. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  23. Jason Li and Jesper Nederlof. Detecting feedback vertex sets of size k in O*(2.7^k) time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 971-989, 2020. Google Scholar
  24. Shaohua Li and Marcin Pilipczuk. An improved FPT algorithm for independent feedback vertex set. In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159, pages 344-355. Springer, 2018. Google Scholar
  25. Mugang Lin, Qilong Feng, Jianxin Wang, Jianer Chen, Bin Fu, and Wenjun Li. An improved FPT algorithm for almost forest deletion problem. Inf. Process. Lett., 136:30-36, 2018. URL: https://doi.org/10.1016/j.ipl.2018.03.016.
  26. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. ACM Trans. Algorithms, 14(1):7:1-7:37, 2018. Google Scholar
  27. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On parameterized independent feedback vertex set. Theor. Comput. Sci., 461:65-75, 2012. Google Scholar
  28. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. J. Comb. Optim., 24(2):131-146, 2012. Google Scholar
  29. Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Generalized pseudoforest deletion: Algorithms and uniform kernel. SIAM J. Discret. Math., 32(2):882-901, 2018. URL: https://doi.org/10.1137/16M1100794.
  30. Ashutosh Rai and Saket Saurabh. Bivariate complexity analysis of almost forest deletion. Theor. Comput. Sci., 708:18-33, 2018. URL: https://doi.org/10.1016/j.tcs.2017.10.021.
  31. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In ISAAC, volume 2518 of Lecture Notes in Computer Science, pages 241-248. Springer, 2002. Google Scholar
  32. Junjie Ye. A note on finding dual feedback vertex set. CoRR, abs/1510.00773, 2015. URL: http://arxiv.org/abs/1510.00773.
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 Imprint Privacy Contact