Document Open Access Logo

Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set

Authors Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, Roohani Sharma

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.2.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Akanksha Agrawal
Sushmita Gupta
Saket Saurabh
Roohani Sharma

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.2

Abstract

In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.

Subject Classification

Keywords
  • independent feedback vertex set
  • fixed parameter tractable
  • exact algorithm
  • enumeration

Metrics

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

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective. In Proc. of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16), volume 47 of LIPIcs, pages 7:1-7:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.7.
  2. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3):289-297, 1999. Google Scholar
  3. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73(1):63-86, 2015. Google Scholar
  4. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences, 74(7):1188-1198, 2008. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał 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), pages 150-159, 2011. Google Scholar
  7. Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. On group feedback vertex set parameterized by the size of the cutset. Algorithmica, 74(2):630-642, 2016. Google Scholar
  8. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. SIAM Journal of Discrete Mathematics, 27(1):290-309, 2013. Google Scholar
  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. Rod G. Downey and Michael R. Fellows. Parameterized complexity. Springer-Verlag, 1997. Google Scholar
  11. Paola Festa, Panos M. Pardalos, and Mauricio G. C. Resende. Feedback set problems. In Handbook of combinatorial optimization, Supplement Vol. A, pages 209-258. Kluwer Acad. Publ., Dordrecht, 1999. Google Scholar
  12. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  13. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC'16), pages 764-775, 2016. Google Scholar
  14. Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52(2):293-307, 2008. Google Scholar
  15. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A Measure & Conquer approach for the analysis of exact algorithms. Journal of ACM, 56(5), 2009. Google Scholar
  16. Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger. Enumerating minimal subset feedback vertex sets. Algorithmica, 69(1):216-231, 2014. Google Scholar
  17. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. An EATCS Series: Texts in Theoretical Computer Science. Google Scholar
  18. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. Google Scholar
  19. G. R. Grimmett. An upper bound for the number of spanning trees of a graph. Discrete Mathematics, 16(4):323-324, 1976. Google Scholar
  20. Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61-71, 2011. Google Scholar
  21. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  22. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters, 114(10):556-560, 2014. Google Scholar
  23. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP, volume 9134, pages 935-946, 2015. Google Scholar
  24. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65-75, 2012. Google Scholar
  25. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. Journal of Combinatorial Optimization, 24(2):131-146, 2012. Google Scholar
  26. J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23-28, 1965. Google Scholar
  27. Rolf Niedermeier. Invitation to fixed-parameter algorithms, 2006. Google Scholar
  28. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms, 2(3):403-415, 2006. Google Scholar
  29. Igor Razgon. Exact computation of maximum induced forest. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), volume 4059, pages 160-171, 2006. Google Scholar
  30. Yinglei Song. An improved parameterized algorithm for the independent feedback vertex set problem. Theoretical Computer Science, 535:25-30, 2014. Google Scholar
  31. Yuma Tamura, Takehiro Ito, and Xiao Zhou. Algorithms for the independent feedback vertex set problem. IEICE Transactions, 98-A(6):1179-1188, 2015. Google Scholar
  32. Shuichi Ueno, Yoji Kajitani, and Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1):355-360, 1988. Google Scholar
  33. Magnus Wahlström. Half-integrality, LP-branching and FPT algorithms. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1762-1781, 2014. 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