Document Open Access Logo

A Faster Parameterized Algorithm for Pseudoforest Deletion

Authors Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.7.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Hans L. Bodlaender
Hirotaka Ono
Yota Otachi

Cite AsGet BibTex

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A Faster Parameterized Algorithm for Pseudoforest Deletion. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.7

Abstract

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.
Keywords
  • pseudoforest deletion
  • graph class
  • width parameter
  • parameterized complexity

Metrics

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

References

  1. V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12:289-297, 1999. Google Scholar
  2. A. Becker and D. Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83:167-188, 1996. Google Scholar
  3. Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. Journal of Artificial Intelligence Research, 12:219-234, 2000. Google Scholar
  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In Proceedings of the 39th Annual Symposium on Theory of Computing, STOC 2007, pages 67-74, 2007. Google Scholar
  5. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305-1317, 1996. Google Scholar
  6. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. Google Scholar
  7. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction algorithms for graphs of small treewidth. Information and Computation, 167:86-119, 2001. Google Scholar
  8. 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 Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 150-159, 2011. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science, FOCS 2012, pages 470-479, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.62.
  10. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  11. Ljubomir Perković and Bruce Reed. An improved algorithm for finding tree decompositions of small width. International Journal of Foundations of Computer Science, 11:365-371, 2000. Google Scholar
  12. Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Generalized pseudoforest deletion: Algorithms and uniform kernel. In 40th International Symposium on Mathematical Foundations of Computer Science 2015, MFCS 2015, volume 9235 of Lecture Notes in Computer Science, pages 517-528. Springer Verlag, 2015. Google Scholar
  13. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms, 9(1):11, 2012. Google Scholar
  14. Johan M. M. van Rooij. Exact Exponential-Time Algorithms for Domination Problems in Graphs. PhD thesis, Utrecht University, 2011. URL: https://dspace.library.uu.nl/bitstream/handle/1874/205442/rooij.pdf.
  15. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009, pages 566-577. Springer Verlag, Lecture Notes in Computer Science, vol. 5757, 2009. 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 Imprint Privacy Contact