Document Open Access Logo

Faster FPT Algorithm for 5-Path Vertex Cover

Authors Radovan Červený , Ondřej Suchý

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.32.pdf
  • Filesize: 479 kB
  • 13 pages

Document Identifiers

Author Details

Radovan Červený
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
Ondřej Suchý
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

Funding

  • Červený, Radovan: Supported by grant 17-20065S of the Czech Science Foundation.
  • Suchý, Ondřej: The author acknowledges the support of the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16_019/0000765 "Research Center for Informatics".

Cite AsGet BibTex

Radovan Červený and Ondřej Suchý. Faster FPT Algorithm for 5-Path Vertex Cover. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.32

Abstract

The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G \ F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d >= 2. When parameterized by the size of the solution k, 5-PVC has direct trivial algorithm with O(5^kn^{O(1)}) running time and, since d-PVC is a special case of d-Hitting Set, an algorithm running in O(4.0755^kn^{O(1)}) time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in O(4^kn^{O(1)}) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • graph algorithms
  • Hitting Set
  • iterative compression
  • parameterized complexity
  • d-Path Vertex Cover

Metrics

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

Related Versions

References

  1. Boštjan Brešar, František Kardoš, Ján Katrenič, and Gabriel Semanišin. Minimum k-path vertex cover. Discrete Applied Mathematics, 159(12):1189-1195, 2011. URL: https://doi.org/10.1016/j.dam.2011.04.008.
  2. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  3. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  4. 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. URL: https://doi.org/10.1145/2629620.
  5. Stefan Fafianie and Stefan Kratsch. A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 299-310, 2015. URL: https://doi.org/10.1007/978-3-662-48054-0_25.
  6. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. Iterative compression and exact algorithms. Theor. Comput. Sci., 411(7-9):1045-1053, 2010. URL: https://doi.org/10.1016/j.tcs.2009.11.012.
  7. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact Algorithms via Monotone Local Search. J. ACM, 66(2):8:1-8:23, 2019. URL: https://doi.org/10.1145/3284176.
  8. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16533-7.
  9. Stefan Funke, André Nusser, and Sabine Storandt. On k-Path Covers and their applications. VLDB J., 25(1):103-123, 2016. URL: https://doi.org/10.1007/s00778-015-0392-3.
  10. Ján Katrenič. A faster FPT algorithm for 3-path vertex cover. Inf. Process. Lett., 116(4):273-278, 2016. URL: https://doi.org/10.1016/j.ipl.2015.12.002.
  11. John M. Lewis and Mihalis Yannakakis. The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  12. Marián Novotný. Design and Analysis of a Generalized Canvas Protocol. In Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices, 4th IFIP WG 11.2 International Workshop, WISTP 2010, Passau, Germany, April 12-14, 2010. Proceedings, pages 106-121, 2010. URL: https://doi.org/10.1007/978-3-642-12368-9_8.
  13. Yaron Orenstein, David Pellow, Guillaume Marçais, Ron Shamir, and Carl Kingsford. Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing. PLoS Computational Biology, 13(10), 2017. URL: https://doi.org/10.1371/journal.pcbi.1005777.
  14. Dekel Tsur. An O^*(2.619^k) algorithm for 4-path vertex cover. CoRR, abs/1811.03592, 2018. URL: http://arxiv.org/abs/1811.03592.
  15. Dekel Tsur. Parameterized algorithm for 3-path vertex cover. Theoretical Computer Science, 783:1-8, 2019. URL: https://doi.org/10.1016/j.tcs.2019.03.013.
  16. Jianhua Tu. A fixed-parameter algorithm for the vertex cover P₃ problem. Inf. Process. Lett., 115(2):96-99, 2015. URL: https://doi.org/10.1016/j.ipl.2014.06.018.
  17. Jianhua Tu and Zemin Jin. An FPT algorithm for the vertex cover P₄ problem. Discrete Applied Mathematics, 200:186-190, 2016. URL: https://doi.org/10.1016/j.dam.2015.06.032.
  18. Mingyu Xiao and Shaowei Kou. Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theor. Comput. Sci., 657:86-97, 2017. URL: https://doi.org/10.1016/j.tcs.2016.04.043.
  19. Mingyu Xiao and Shaowei Kou. Kernelization and Parameterized Algorithms for 3-Path Vertex Cover. In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 654-668, 2017 . URL: https://doi.org/10.1007/978-3-319-55911-7_47.
  20. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Inf. Comput., 255:126-146, 2017. URL: https://doi.org/10.1016/j.ic.2017.06.001.
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