Document Open Access Logo

Parameterized Complexity of Feedback Vertex Sets on Hypergraphs

Authors Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.18.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Pratibha Choudhary
  • Indian Institute of Technology Jodhpur, Jodhpur, India
Lawqueen Kanesh
  • Institute of Mathematical Sciences, HBNI, Chennai, India
Daniel Lokshtanov
  • University of California Santa Barbara, Santa Barbara, USA
Fahad Panolan
  • Indian Institute of Technology Hyderabad, India
Saket Saurabh
  • Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway

Funding

  • Saurabh, Saket: Received funding from European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Acknowledgements

We thank the anonymous referees of an earlier version of the paper. Their comments helped us a lot in improving the paper.

Cite AsGet BibTex

Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized Complexity of Feedback Vertex Sets on Hypergraphs. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.18

Abstract

A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows - HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). - If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{𝒪(k³log k)}n^{𝒪(1)}. - If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{𝒪(k)}n^{𝒪(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • feedback vertex sets
  • hypergraphs
  • FPT
  • randomized algorithms

Metrics

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

References

  1. Faisal N. Abu-Khzam. A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci., 76(7):524-531, 2010. Google Scholar
  2. 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
  3. Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 1-13. Springer, 2016. Google Scholar
  4. 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
  5. 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
  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. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  10. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms, 13(3):43:1-43:22, 2017. Google Scholar
  11. 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
  12. 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
  13. 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
  14. 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
  15. Zhuo Diao and Zhongzheng Tang. On the feedback number of 3-uniform hypergraph. CoRR, abs/1807.10456, 2018. URL: http://arxiv.org/abs/1807.10456.
  16. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, 2012. Google Scholar
  17. J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag, 2006. Google Scholar
  18. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  19. Toshihiro Fujito. Approximating minimum feedback vertex sets in hypergraphs. Theoretical Computer Science, 246(1):107-116, 2000. Google Scholar
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  26. Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. Google Scholar
  27. 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
  28. 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
  29. 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
  30. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On parameterized independent feedback vertex set. Theor. Comput. Sci., 461:65-75, 2012. Google Scholar
  31. 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
  32. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms, 9(1):11:1-11:23, 2012. Google Scholar
  33. Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in sparse graphs and beyond. Theor. Comput. Sci., 770:62-68, 2019. Google Scholar
  34. 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