Document Open Access Logo

Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph

Authors Mina Dalirrooyfard, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.35.pdf
  • Filesize: 0.75 MB
  • 20 pages

Document Identifiers

Author Details

Mina Dalirrooyfard
  • MIT, Cambridge, MA, USA
Virginia Vassilevska Williams
  • MIT, Cambridge, MA, USA

Funding

  • Dalirrooyfard, Mina: Partially supported by an NSF CAREER award and NSF Grant CCF-1514339.
  • Vassilevska Williams, Virginia: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.

Acknowledgements

The authors would like to thank the anonymous reviewers for their insightful comments.

Cite As Get BibTex

Mina Dalirrooyfard and Virginia Vassilevska Williams. Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.35

Abstract

The girth is one of the most basic graph parameters, and its computation has been studied for many decades. Under widely believed fine-grained assumptions, computing the girth exactly is known to require mn^{1-o(1)} time, both in sparse and dense m-edge, n-node graphs, motivating the search for fast approximations. Fast good quality approximation algorithms for undirected graphs have been known for decades. For the girth in directed graphs, until recently the only constant factor approximation algorithms ran in O(n^ω) time, where ω < 2.373 is the matrix multiplication exponent. These algorithms have two drawbacks: (1) they only offer an improvement over the mn running time for dense graphs, and (2) the current fast matrix multiplication methods are impractical. The first constant factor approximation algorithm that runs in O(mn^{1-ε}) time for ε > 0 and all sparsities m was only recently obtained by Chechik et al. [STOC 2020]; it is also combinatorial. 
It is known that a better than 2-approximation algorithm for the girth in dense directed unweighted graphs needs n^{3-o(1)} time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in O(mn^{1-ε}) time (by Chechik et al.) is 3. Is the true answer 2 or 3?
The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least mn^{1-o(1)} time for some sparsity m if it achieves a (2-ε)-approximation for any ε > 0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in Õ(mn^{3/4}) time, and a (2+ε)-approximation algorithm (for any ε > 0) that works in weighted graphs and runs in Õ(m√ n) time. Our algorithms are combinatorial. 
We also obtain a (4+ε)-approximation of the girth running in Õ(mn^{√2-1}) time, improving upon the previous best Õ(m√n) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5+ε)-approximate roundtrip spanner on Õ(n^{1.5}/ε²) edges in Õ(m√n/ε²) time. This improves upon the previous approximation factor (8+ε) of Chechik et al. for the same running time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Graph algorithms analysis
Keywords
  • Shortest cycle
  • Girth
  • Graph algorithms
  • Approximation algorithms
  • Fine-grained complexity
  • Roundtrip Spanner

Metrics

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

Related Versions

References

  1. N. Alon, R. Yuster, and U. Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17:209-223, 1997. Google Scholar
  3. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In Proceedings of ICALP, page to appear, 2019. Google Scholar
  4. A. Bondy and M. Simonovits. Cycles of even length in graphs. Journal of Combinatorial Theory, 16:97-105, 1974. Google Scholar
  5. Ruoxu Cen and Ran Duan. Roundtrip spanners with (2k-1) stretch. CoRR, abs/1911.12411, 2019. URL: http://arxiv.org/abs/1911.12411.
  6. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Improved girth approximation and roundtrip spanners. CoRR, abs/1907.10779, 2019. URL: http://arxiv.org/abs/1907.10779.
  7. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Improved girth approximation and roundtrip spanners. In Proceedings of STOC, page to appear, 2020. Google Scholar
  8. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM, 62(4):28:1-28:30, September 2015. Google Scholar
  9. Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In Proceedings of STOC 2019, page to appear, 2019. Google Scholar
  10. Mina Dalirrooyfard and Virginia Vassilevska Williams. Conditionally optimal approximation algorithms for the girth of a directed graph. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.11445.
  11. A.V. Goldberg. Scaling algorithms for the shortest paths problem. In Proc. SODA, pages 222-231, 1993. Google Scholar
  12. A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413-423, 1978. Google Scholar
  13. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. Google Scholar
  14. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252, 2018. Google Scholar
  15. Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. 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 1374-1392. SIAM, 2018. Google Scholar
  16. Maximilian Probst, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proceedings of STOC, page to appear, 2020. Google Scholar
  17. Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 180-189. IEEE Computer Society, 2011. Google Scholar
  18. Liam Roditty and Virginia Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 833-845. SIAM, 2012. Google Scholar
  19. R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. JCSS, 51:400-403, 1995. Google Scholar
  20. V. Vassilevska. Efficient algorithms for path problems. Ph.D. Thesis in Computer Science, Carnegie Mellon University, 2008. Google Scholar
  21. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. FOCS, pages 645-654, 2010. Google Scholar
  22. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898, 2012. Google Scholar
  23. R. Yuster and U. Zwick. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In Proc. SODA, pages 247-253, 2004. Google Scholar
  24. U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. 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