Document Open Access Logo

On Fully Dynamic Strongly Connected Components

Authors Adam Karczmarz , Marcin Smulewicz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.68.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Adam Karczmarz
  • University of Warsaw, Poland
  • IDEAS NCBR, Warsaw, Poland
Marcin Smulewicz
  • University of Warsaw, Poland

Funding

  • Karczmarz, Adam: Partially supported by the ERC CoG grant TUgbOAT no 772346 and the National Science Centre (NCN) grant no. 2022/47/D/ST6/02184.

Cite AsGet BibTex

Adam Karczmarz and Marcin Smulewicz. On Fully Dynamic Strongly Connected Components. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.68

Abstract

We consider maintaining strongly connected components (SCCs) of a directed graph subject to edge insertions and deletions. For this problem, we show a randomized algebraic data structure with conditionally tight O(n^1.529) worst-case update time. The only previously described subquadratic update bound for this problem [Karczmarz, Mukherjee, and Sankowski, STOC'22] holds exclusively in the amortized sense. For the less general dynamic strong connectivity problem, where one is only interested in maintaining whether the graph is strongly connected, we give an efficient deterministic black-box reduction to (arbitrary-pair) dynamic reachability. Consequently, for dynamic strong connectivity we match the best-known O(n^1.407) worst-case upper bound for dynamic reachability [van den Brand, Nanongkai, and Saranurak FOCS'19]. This is also conditionally optimal and improves upon the previous O(n^1.529) bound. Our reduction also yields the first fully dynamic algorithms for maintaining the minimum strong connectivity augmentation of a digraph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • dynamic strongly connected components
  • dynamic strong connectivity
  • dynamic reachability

Metrics

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

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, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  2. Surender Baswana, Keerti Choudhary, and Liam Roditty. An efficient strongly connected components algorithm in the fault tolerant model. Algorithmica, 81(3):967-985, 2019. URL: https://doi.org/10.1007/s00453-018-0452-3.
  3. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. A new approach to incremental cycle detection and related problems. ACM Trans. Algorithms, 12(2):14:1-14:22, 2016. URL: https://doi.org/10.1145/2756553.
  4. Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 1836-1855. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.110.
  5. Aaron Bernstein, Aditi Dudeja, and Seth Pettie. Incremental SCC maintenance in sparse graphs. In 29th Annual European Symposium on Algorithms, ESA 2021, volume 204 of LIPIcs, pages 14:1-14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.14.
  6. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1123-1134. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00108.
  7. Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen. Decremental strongly-connected components and single-source reachability in near-linear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 365-376. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316335.
  8. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis. Decremental single-source reachability and strongly connected components in õ(m√n) total update time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 315-324. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.42.
  9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  10. Kapali P. Eswaran and Robert Endre Tarjan. Augmentation problems. SIAM J. Comput., 5(4):653-665, 1976. URL: https://doi.org/10.1137/0205044.
  11. Harold N. Gabow. Path-based depth-first search for strong and biconnected components. Inf. Process. Lett., 74(3-4):107-114, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00051-X.
  12. Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. Strong connectivity in directed graphs under failures, with applications. SIAM J. Comput., 49(5):865-926, 2020. URL: https://doi.org/10.1137/19M1258530.
  13. Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Trans. Algorithms, 8(1):3:1-3:33, 2012. URL: https://doi.org/10.1145/2071379.2071382.
  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 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  15. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  16. Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1108-1121. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055480.
  17. Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1643-1656. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520058.
  18. Jakub Łącki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Trans. Algorithms, 9(3):27:1-27:15, 2013. URL: https://doi.org/10.1145/2483699.2483707.
  19. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput., 37(5):1455-1471, 2008. URL: https://doi.org/10.1137/060650271.
  20. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In 45th Symposium on Foundations of Computer Science FOCS 2004, pages 509-517. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.25.
  21. Warren Schudy. Finding strongly connected components in parallel using o(log^2n) reachability queries. In SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 146-151. ACM, 2008. URL: https://doi.org/10.1145/1378533.1378560.
  22. Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. URL: https://doi.org/10.1006/jcss.1995.1078.
  23. M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1):67-72, 1981. URL: https://doi.org/10.1016/0898-1221(81)90008-0.
  24. Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: https://doi.org/10.1137/0201010.
  25. Jan van den Brand, Sebastian Forster, and Yasamin Nazari. Fast deterministic fully dynamic distance approximation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 1011-1022. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00099.
  26. Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 456-480. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00036.
  27. 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.
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