LIPIcs.ESA.2022.65.pdf
- Filesize: 0.91 MB
- 14 pages
Document
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
Authors
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
Cite As Get BibTex
Monika Henzinger, Ami Paz, and A. R. Sricharan. Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.65
Abstract
A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions. Prior work has shown strong conditional lower bounds for general dynamic graphs, yet graph families that arise in practice often exhibit structural properties that the existing lower bound constructions do not possess. We study three specific graph families that are ubiquitous, namely constant-degree graphs, power-law graphs, and expander graphs, and give the first conditional lower bounds for them. Our results show that even when restricting our attention to one of these graph classes, any algorithm for fundamental graph problems such as distance computation or approximation or maximum matching, cannot simultaneously achieve a sub-polynomial update time and query time. For example, we show that the same lower bounds as for general graphs hold for maximum matching and (s,t)-distance in constant-degree graphs, power-law graphs or expanders. Namely, in an m-edge graph, there exists no dynamic algorithms with both O(m^{1/2 - ε}) update time and O(m^{1 -ε}) query time, for any small ε > 0. Note that for (s,t)-distance the trivial dynamic algorithm achieves an almost matching upper bound of constant update time and O(m) query time. We prove similar bounds for the other graph families and for other fundamental problems such as densest subgraph detection and perfect matching.
Subject Classification
ACM Subject Classification
- Theory of computation → Dynamic graph algorithms
Keywords
- Dynamic graph algorithms
- Expander graphs
- Power-law graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In FOCS, pages 477-486. IEEE Computer Society, 2016.
- Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. On dynamic approximate shortest paths for planar graphs with worst-case costs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 740-753. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch53.
- Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1199-1218, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2213977.2214084.
- William Aiello, Fan Chung Graham, and Linyuan Lu. A random graph model for power law graphs. Exp. Math., 10(1):53-66, 2001. URL: https://doi.org/10.1080/10586458.2001.10504428.
-
Panagiotis Charalampopoulos and Adam Karczmarz. Single-source shortest paths and strong connectivity in dynamic planar graphs. In ESA, volume 173 of LIPIcs, pages 31:1-31:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
- Julia Chuzhoy. Decremental all-pairs shortest paths in deterministic near-linear time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 626-639. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451025.
- Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2478-2496. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.147.
- Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. CoRR, abs/1602.06705, 2016. URL: http://arxiv.org/abs/1602.06705.
- Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2212-2228. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.132.
-
Fan Chung Graham. Large dynamic graphs: What can researchers learn from them? SIAM News, 37(3), 2004.
- Manoj Gupta and Richard Peng. Fully dynamic (1+ ε)-approximate matchings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548-557, 2013. URL: https://doi.org/10.1109/FOCS.2013.65.
-
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21-30. ACM, 2015.
-
Monika Henzinger, Andrea Lincoln, and Barna Saha. The complexity of average-case dynamic subgraph counting. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459-498. SIAM, 2022.
- Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3-23, 1997. URL: https://doi.org/10.1006/jcss.1997.1493.
- Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1108-1121. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055480.
- Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 313-322. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993679.
- Wenyu Jin and Xiaorui Sun. Fully dynamic c-edge connectivity in subpolynomial time. CoRR, abs/2004.07650, 2020. URL: http://arxiv.org/abs/2004.07650.
- P. N. Klein and S. Subramanian. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica, 22(3):235-249, November 1998. URL: https://doi.org/10.1007/PL00009223.
- Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 181-193, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384327.
- Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Thomas Lengauer, editor, Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, volume 726 of Lecture Notes in Computer Science, pages 372-383. Springer, 1993. URL: https://doi.org/10.1007/3-540-57273-2_72.