Document Open Access Logo

Algorithms and Hardness for Diameter in Dynamic Graphs

Authors Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.13.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Bertie Ancona
  • MIT, Cambridge, MA, USA
Monika Henzinger
  • University of Vienna, Austria
Liam Roditty
  • Bar Ilan University, Ramat Gan, Israel
Virginia Vassilevska Williams
  • MIT, Cambridge, MA, USA
Nicole Wein
  • MIT, Cambridge, MA, USA

Funding

  • Henzinger, Monika: The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506.
  • Williams, Virginia Vassilevska: Supported by an NSF CAREER Award, NSF Grants CCF-1417238, CCF-1528078 and CCF-1514339, a BSF Grant BSF:2012338 and a Sloan Research Fellowship.
  • Wein, Nicole: Supported by an NSF Graduate Fellowship and NSF Grant CCF-1514339.

Acknowledgements

The authors would like to thank Roei Tov for discussions.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.13

Abstract

The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported. This paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Some of the highlights include: - Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP. - Nearly optimal partially dynamic (incremental/decremental) algorithms can be achieved via efficient reductions to (incremental/decremental) maintenance of Single-Source Shortest Paths. For instance, a nearly (3/2+epsilon)-approximation to Diameter in directed or undirected n-vertex, m-edge graphs can be maintained decrementally in total time m^{1+o(1)}sqrt{n}/epsilon^2. This nearly matches the static 3/2-approximation algorithm for the problem that is known to be conditionally optimal.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • fine-grained complexity
  • graph algorithms
  • dynamic algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. Google Scholar
  2. 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
  3. R. Albert, H. Jeong, and A.L. Barabasi. Diameter of the world wide web. Nature, 401:130-131, 1999. Google Scholar
  4. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17:209-223, 1997. Google Scholar
  5. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and Hardness for Diameter in Dynamic Graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.12527.
  6. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards Tight Approximation Bounds for Graph Diameter and Eccentricities. In Proceedings of STOC'18, page to appear, 2018. Google Scholar
  7. 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
  8. 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
  9. Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In STOC, page to appear, 2019. Google Scholar
  10. Camil Demetrescu and Giuseppe F. Italiano. A New Approach to Dynamic All Pairs Shortest Paths. Journal of the ACM, 51(6):968-992, 2004. Announced at STOC'03. URL: http://dx.doi.org/10.1145/1039488.1039492.
  11. Shimon Even and Yossi Shiloach. An On-Line Edge-Deletion Problem. Journal of the ACM, 28(1):1-4, 1981. URL: http://dx.doi.org/10.1145/322234.322235.
  12. Monika Henzinger and Valerie King. Fully Dynamic Biconnectivity and Transitive Closure. In Symposium on Foundations of Computer Science (FOCS), pages 664-672, 1995. URL: http://dx.doi.org/10.1109/SFCS.1995.492668.
  13. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. In Symposium on Foundations of Computer Science (FOCS), pages 146-155, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.24.
  14. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Symposium on Theory of Computing (STOC), pages 21-30, 2015. URL: http://dx.doi.org/10.1145/2746539.2746609.
  15. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.26.
  16. R. Impagliazzo, R. Paturi, and F. Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  17. 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
  18. Moshe Lewenstein, Seth Pettie, and Virginia Vassilevska Williams. Open Problems from Dagstuhl Seminar 16451: Structure and Hardness in P, 2016. Google Scholar
  19. S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. Google Scholar
  20. Seth Pettie and Vijaya Ramachandran. A Shortest Path Algorithm for Real-Weighted Undirected Graphs. SIAM J. Comput., 34(6):1398-1431, 2005. Google Scholar
  21. 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, 2013. Google Scholar
  22. R. Seidel. On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. Google Scholar
  23. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 887-898. ACM, 2012. Google Scholar
  24. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, page to appear, 2018. Google Scholar
  25. R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
  26. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664-673, 2014. Google Scholar
  27. 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
  28. 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: http://dx.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