Document Open Access Logo

On Diameter Approximation in Directed Graphs

Authors Amir Abboud , Mina Dalirrooyfard , Ray Li , Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.2.pdf
  • Filesize: 0.87 MB
  • 17 pages

Document Identifiers

Author Details

Amir Abboud
  • Weizmann Institute of Science, Rehovot, Israel
Mina Dalirrooyfard
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Ray Li
  • University of California Berkeley, CA, USA
Virginia Vassilevska Williams
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Abboud, Amir: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No 101078482). Additionally, Amir Abboud is supported by an Alon scholarship and a research grant from the Center for New Scientists at the Weizmann Institute of Science.
  • Dalirrooyfard, Mina: Partially supported by an Akamai Fellowship.
  • Li, Ray: Supported by the NSF Mathematical Sciences Postdoctoral Research Fellowships Program under Grant DMS-2203067, and a UC Berkeley Initiative for Computational Transformation award.
  • Vassilevska Williams, Virginia: Partially supported by the National Science Foundation Grant CCF-2129139.

Acknowledgements

We would like to thank Piotr Indyk, Karthik C.S., and the participants of the Fine-Grained Approximation Algorithms & Complexity Workshop (FG-APX 2019) at Bertinoro 2019 for many helpful discussions.

Cite AsGet BibTex

Amir Abboud, Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. On Diameter Approximation in Directed Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.2

Abstract

Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation trade-off that is quite close to the upper bounds. In directed graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since d(u,v) may not be the same as d(v,u), there are multiple ways to define the problem, the two most natural being the (one-way) diameter (max_(u,v) d(u,v)) and the roundtrip diameter (max_{u,v} d(u,v)+d(v,u)). In this paper we make progress on the outstanding open question for each of them. - We design the first algorithm for diameter in sparse directed graphs to achieve n^{1.5-ε} time with an approximation factor better than 2. The new upper bound trade-off makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication. - We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a 1.5-approximation in subquadratic time would refute the All-Nodes k-Cycle hypothesis, and any (2-ε)-approximation would imply a breakthrough algorithm for approximate 𝓁_∞-Closest-Pair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Graph algorithms analysis
Keywords
  • Diameter
  • Directed Graphs
  • Approximation Algorithms
  • Fine-grained complexity

Metrics

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

Related Versions

References

  1. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci., 127:29-40, 2022. URL: https://doi.org/10.1016/j.jcss.2022.01.005.
  2. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Trans. Algorithms, 17(4):30:1-30:40, 2021. URL: https://doi.org/10.1145/3469834.
  3. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681-1697, 2015. Google Scholar
  4. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377-391, 2016. Google Scholar
  5. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 239-252, 2018. Google Scholar
  6. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. Google Scholar
  7. N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci., 54(2):255-262, 1997. Google Scholar
  8. N. Alon, R. Yuster, and U. Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  9. Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, and Virginia Vassilevska Williams. Distributed distance approximation. In Quentin Bramas, Rotem Oshman, and Paolo Romano, editors, 24th International Conference on Principles of Distributed Systems, OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference), volume 184 of LIPIcs, pages 30:1-30:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2020.30.
  10. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  11. Alexandr Andoni, Dorian Croitoru, and Mihai Patrascu. Hardness of nearest neighbor under l-infinity. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 424-433, 2008. URL: https://doi.org/10.1109/FOCS.2008.89.
  12. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 267-280. ACM, 2018. Google Scholar
  13. Édouard Bonnet. 4 vs 7 sparse undirected unweighted diameter is seth-hard at time n^4/3. In Proc. ICALP, pages 34:1-34:15, 2021. Google Scholar
  14. Édouard Bonnet. Inapproximability of diameter in super-linear time: Beyond the 5/3 ratio. In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 17:1-17:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  15. Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A Kosters, Andrea Marino, and Frank W Takes. Fast diameter and radius bfs-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Theoretical Computer Science, 586:59-80, 2015. Google Scholar
  16. Karl Bringmann and Bhaskar Ray Chaudhury. Polyline simplification has cubic complexity. J. Comput. Geom., 11(2):94-130, 2020. URL: https://doi.org/10.20382/jocg.v11i2a5.
  17. Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363-376, 2016. Google Scholar
  18. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. On the exact complexity of evaluating quantified k-cnf. In Venkatesh Raman and Saket Saurabh, editors, Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of Lecture Notes in Computer Science, pages 50-59. Springer, 2010. Google Scholar
  19. Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1041-1052, 2014. Google Scholar
  20. Shiri Chechik and Gur Lifshitz. Optimal girth approximation for dense directed graphs. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 290-300. SIAM, 2021. Google Scholar
  21. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Constant girth approximation for directed graphs in subquadratic time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1010-1023. ACM, 2020. Google Scholar
  22. Lenore Cowen and Christopher G. Wagner. Compact roundtrip routing for digraphs. In Robert Endre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA, pages 885-886. ACM/SIAM, 1999. Google Scholar
  23. Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino. On computing the diameter of real-world directed (weighted) graphs. In Ralf Klasing, editor, Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings, pages 99-110, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  24. Mina Dalirrooyfard and Jenny Kaufmann. Approximation algorithms for min-distance problems in dags. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 60:1-60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  25. Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs. In Proc. FOCS, FOCS'2021, pages 1021-1032, 2021. Google Scholar
  26. Mina Dalirrooyfard and Virginia Vassilevska Williams. Conditionally optimal approximation algorithms for the girth of a directed graph. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 35:1-35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  27. Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation algorithms for min-distance problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  28. Mina Dalirrooyfard and Nicole Wein. Tight conditional lower bounds for approximating diameter in directed graphs. In Proc. STOC, STOC'2021, pages 1697-1710, 2021. Google Scholar
  29. Ofer Grossman, Seri Khoury, and Ami Paz. Improved hardness of approximation of diameter in the CONGEST model. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 19:1-19:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.19.
  30. R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  31. Piotr Indyk. On approximate nearest neighbors under l-infinity norm. Journal of Computer and System Sciences, 63(4):627-638, 2001. Google Scholar
  32. Haim Kaplan, Micha Sharir, and Elad Verbin. Colored intersection searching via sparse rectangular matrix multiplication. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 52-60, 2006. Google Scholar
  33. Karthik C. S. and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. Comb., 40(4):539-573, 2020. URL: https://doi.org/10.1007/s00493-019-4113-1.
  34. Ray Li. Improved seth-hardness of unweighted diameter. CoRR, abs/2008.05106v1, 2020. URL: https://arxiv.org/abs/2008.05106.
  35. Ray Li. Settling seth vs. approximate sparse directed unweighted diameter (up to (nu)nseth). In Proc. STOC, STOC'2021, pages 1684-1696, 2021. Google Scholar
  36. T. C. Lin, M. J. Wu, W. J. Chen, and B. Y. Wu. Computing the diameters of huge social networks. In 2016 International Computer Symposium (ICS), pages 6-11, 2016. Google Scholar
  37. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. 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 1236-1252. SIAM, 2018. Google Scholar
  38. 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
  39. David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392 of Lecture Notes in Computer Science, pages 660-672. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_58.
  40. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 153-166, 2020. Google Scholar
  41. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pages 515-524, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2488608.2488673.
  42. Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1260-1268. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188916.
  43. Aviad Rubinstein and Virginia Vassilevska Williams. Seth vs approximation. ACM SIGACT News, 50(4):57-76, 2019. Google Scholar
  44. R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. Google Scholar
  45. Frank W. Takes and Walter A. Kosters. Determining the diameter of small world networks. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, CIKM '11, pages 1191-1196, 2011. Google Scholar
  46. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  47. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM, 49(3):289-317, 2002. Announced at FOCS'98. URL: https://doi.org/10.1145/567112.567114.
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