Document Open Access Logo

Hitting Long Directed Cycles Is Fixed-Parameter Tractable

Authors Alexander Göke, Dániel Marx, Matthias Mnich

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.59.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Alexander Göke
  • Technische Universität Hamburg, Germany
Dániel Marx
  • Max Planck Institut für Informatik, Saarland Informatics Campus, Saarbrücken, Germany
Matthias Mnich
  • Technische Universität Hamburg, Germany

Funding

  • Göke, Alexander: Supported by DFG grant MN 59/1-1.
  • Marx, Dániel: Supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 725978).
  • Mnich, Matthias: Supported by DFG grant MN 59/4-1.

Cite AsGet BibTex

Alexander Göke, Dániel Marx, and Matthias Mnich. Hitting Long Directed Cycles Is Fixed-Parameter Tractable. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.59

Abstract

In the Directed Long Cycle Hitting Set problem we are given a directed graph G, and the task is to find a set S of at most k vertices/arcs such that G-S has no cycle of length longer than ℓ. We show that the problem can be solved in time 2^O(ℓ^6 + ℓ k^3 log k + k^5 log k log ℓ) ⋅ n^O(1), that is, it is fixed-parameter tractable (FPT) parameterized by k and ℓ. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of Mixed Graph Feedback Vertex Set [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) Feedback Vertex Set and the Directed Feedback Vertex Set problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles of length longer than ℓ and can be seen as an exact version of the approximation algorithm following from the Erdős-Pósa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015].

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Graph algorithms
Keywords
  • Directed graphs
  • directed feedback vertex set
  • circumference

Metrics

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

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. The Erdős-Pósa property for directed graphs, 2016. URL: http://arxiv.org/abs/1603.02504.
  3. Jørgen Bang-Jensen and Tilde My Larsen. DAG-width and circumference of digraphs. J. Graph Theory, 82(2):194-206, 2016. Google Scholar
  4. Paul Bonsma and Daniel Lokshtanov. Feedback vertex set in mixed graphs. In Proc. WADS 2011, volume 6844 of Lecture Notes Comput. Sci., pages 122-133. Springer, 2011. Google Scholar
  5. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: new measure and new structures. Algorithmica, 73(1):63-86, 2015. Google Scholar
  6. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. System Sci., 74(7):1188-1198, 2008. Google Scholar
  7. 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):Art. 21, 19, 2008. Google Scholar
  8. Rajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi, and Dániel Marx. Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms, 11(4):Art. 28, 28, 2015. Google Scholar
  9. Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In Proc. SODA 2012, pages 1713-1725, 2012. Google Scholar
  10. 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 (extended abstract). In Proc. FOCS 2011, pages 150-159. IEEE, 2011. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Proc. SODA 2014, pages 142-151, 2014. Google Scholar
  12. Alexander Göke, Dániel Marx, and Matthias Mnich. Parameterized algorithms for generalizations of directed feedback vertex set. In Proc. CIAC 2019, volume 11485 of Lecture Notes Comput. Sci., pages 249-261, 2019. Google Scholar
  13. 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. System Sci., 72(8):1386-1396, 2006. Google Scholar
  14. Thor Johnson, Neil Robertson, P.D. Seymour, and Robin Thomas. Directed tree-width. J. Combinat. Theory, Series B, 82(1):138-154, 2001. Google Scholar
  15. Ken-ichi Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In Proc. STOC 2015, pages 655-664, 2015. Google Scholar
  16. Shiva Kintali. Directed width parameters and circumference of digraphs. Theoret. Comput. Sci., 659:83-87, 2017. Google Scholar
  17. Daniel J. Kleitman and Joel Spencer. Families of k-independent sets. Discrete Math., 6:255-262, 1973. Google Scholar
  18. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inform. Process. Lett., 114(10):556-560, 2014. Google Scholar
  19. Mordechai Lewin. On maximal circuits in directed graphs. J. Combinatorial Theory, Ser. B, 18(2):175-179, 1975. Google Scholar
  20. Jason Li and Jesper Nederlof. Detecting feedback vertex sets of size k in O^*(2.7^k) time. In Proc. SODA 2020, pages 971-989, 2018. Google Scholar
  21. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurab, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. In Proc. SODA 2020, pages 2181-2200, 2020. Google Scholar
  22. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices. In Proc. SODA 2018, pages 1916-1933, 2018. Google Scholar
  23. B. Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. Google Scholar
  24. Rian Neogi, M. S. Ramanujan, Saket Saurabh, and Roohani Sharma. On the parameterized complexity of deletion to ℋ-free strong components, 2020. Personal communication. Google Scholar
  25. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In Proc. ISAAC 2002, pages 241-248, 2002. Google Scholar
  26. Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  27. Bruce Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299-301, 2004. Google Scholar
  28. Neil Robertson and Paul D. Seymour. Graph minors XIII. The disjoint paths problem. J. Combinat. Theory, Series B, 63(1):65-110, 1995. Google Scholar
  29. Meirav Zehavi. A randomized algorithm for long directed cycle. Inform. Process. Lett., 116(6):419-422, 2016. 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