Document Open Access Logo

Chordless Cycle Packing Is Fixed-Parameter Tractable

Author Dániel Marx

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.71.pdf
  • Filesize: 0.53 MB
  • 19 pages

Document Identifiers

Author Details

Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Funding

Supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

Acknowledgements

The author is very grateful to O-joung Kwon and Eun Jung Kim for helpful comments on the manuscript.

Cite As Get BibTex

Dániel Marx. Chordless Cycle Packing Is Fixed-Parameter Tractable. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.71

Abstract

A chordless cycle or hole in a graph G is an induced cycle of length at least 4. In the Hole Packing problem, a graph G and an integer k is given, and the task is to find (if exists) a set of k pairwise vertex-disjoint chordless cycles. Our main result is showing that Hole Packing is fixed-parameter tractable (FPT), that is, can be solved in time f(k)n^O(1) for some function f depending only on k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Graph algorithms analysis
Keywords
  • chordal graphs
  • packing
  • fixed-parameter tractability

Metrics

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

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Trans. Algorithms, 15(1):11:1-11:28, 2019. URL: https://doi.org/10.1145/3284356.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernel bounds for path and cycle problems. Theor. Comput. Sci., 511:117-136, 2013. URL: https://doi.org/10.1016/j.tcs.2012.09.006.
  4. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
  5. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. URL: https://doi.org/10.1007/s00453-015-0014-x.
  6. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5):21:1-21:19, 2008. URL: https://doi.org/10.1145/1411509.1411511.
  7. Bruno Courcelle. Graph rewriting: an algebraic and logic approach. In Handbook of theoretical computer science, Vol. B, pages 193-242. Elsevier, Amsterdam, 1990. Google Scholar
  8. Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2020. URL: http://arxiv.org/abs/2001.06867.
  9. 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.
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. P. Erdős and L. Pósa. On independent circuits contained in a graph. Canad. J. Math., 17:347-352, 1965. Google Scholar
  12. Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. On the parameterized complexity of graph modification to first-order logic properties. Theory Comput. Syst., 64(2):251-271, 2020. URL: https://doi.org/10.1007/s00224-019-09938-8.
  13. Fedor V. Fomin, Saket Saurabh, and Neeldhara Misra. Graph modification problems: A modern perspective. In Jianxin Wang and Chee-Keng Yap, editors, Frontiers in Algorithmics - 9th International Workshop, FAW 2015, Guilin, China, July 3-5, 2015, Proceedings, volume 9130 of Lecture Notes in Computer Science, pages 3-6. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19647-3_1.
  14. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New York, 1980. Google Scholar
  15. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Automated generation of search tree algorithms for hard graph modification problems. Algorithmica, 39(4):321-347, 2004. URL: https://doi.org/10.1007/s00453-004-1090-5.
  16. Bart M. P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. SIAM J. Discrete Math., 32(3):2258-2301, 2018. URL: https://doi.org/10.1137/17M112035X.
  17. Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. Packing cycles through prescribed vertices. J. Comb. Theory, Ser. B, 101(5):378-381, 2011. URL: https://doi.org/10.1016/j.jctb.2011.03.004.
  18. Ken-ichi Kawarabayashi and Bruce A. Reed. Odd cycle packing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 695-704. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806785.
  19. Ken-ichi Kawarabayashi, Bruce A. Reed, and Paul Wollan. The graph minor algorithm with parity conditions. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 27-36. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.52.
  20. Eun Jung Kim and O-joung Kwon. Erdős-pósa property of chordless cycles and its applications. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1665-1684. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.109.
  21. 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.
  22. Dániel Marx. Chordal deletion is fixed-parameter tractable. Algorithmica, 57(4):747-768, 2010. URL: https://doi.org/10.1007/s00453-008-9233-8.
  23. M. Pontecorvi and Paul Wollan. Disjoint cycles intersecting a set of vertices. J. Comb. Theory, Ser. B, 102(5):1134-1141, 2012. URL: https://doi.org/10.1016/j.jctb.2012.05.004.
  24. Bruce A. Reed. Mangoes and blueberries. Combinatorica, 19(2):267-296, 1999. URL: https://doi.org/10.1007/s004930050056.
  25. Bruce A. Reed, Neil Robertson, Paul D. Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. URL: https://doi.org/10.1007/BF01271272.
  26. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: https://doi.org/10.1016/j.orl.2003.10.009.
  27. Donald J. Rose, Robert Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput., 5(2):266-283, 1976. URL: https://doi.org/10.1137/0205021.
  28. Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math., 24(1):146-157, 2010. URL: https://doi.org/10.1137/070697781.
  29. Stéphan Thomassé. A 4k^2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, 2010. URL: https://doi.org/10.1145/1721837.1721848.
  30. Mihalis Yannakakis. Edge-deletion problems. SIAM J. Comput., 10(2):297-309, 1981. URL: https://doi.org/10.1137/0210021.
  31. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM J. Comput., 10(2):310-327, 1981. URL: https://doi.org/10.1137/0210022.
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