Document Open Access Logo

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

Authors Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, Nikos Parotsidis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.42.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Loukas Georgiadis
Thomas Dueholm Hansen
Giuseppe F. Italiano
Sebastian Krinninger
Nikos Parotsidis

Cite As Get BibTex

Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, and Nikos Parotsidis. Decremental Data Structures for Connectivity and Dominators in Directed Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.42

Abstract

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G \ w?", for any triple of vertices u, v, w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in O(m n log n) total time and O(n^2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e.
		
As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(m n log n) total time and O(n^2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m + n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.

Subject Classification

Keywords
  • dynamic graph algorithms
  • decremental algorithms
  • dominator tree
  • strong connectivity under failures

Metrics

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

References

  1. S. Allesina and A. Bodini. Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions. Journal of Theoretical Biology, 230(3):351-358, 2004. URL: http://dx.doi.org/10.1016/j.jtbi.2004.05.009.
  2. S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup. Dominators in linear time. SIAM Journal on Computing, 28(6):2117-21132, 1999. URL: http://dx.doi.org/10.1137/S0097539797317263.
  3. S. Alstrup and P. W. Lauridsen. A simple dynamic algorithm for maintaining a dominator tree. Technical Report 96-3, Department of Computer Science, University of Copenhagen, 1996. Google Scholar
  4. M. E. Amyeen, W. K. Fuchs, I. Pomeranz, and V. Boppana. Fault equivalence identification using redundancy information and static and dynamic extraction. In Proc. of the 19th IEEE VLSI Test Symposium, pages 124-130, 2001. URL: http://dx.doi.org/10.1109/VTS.2001.923428.
  5. S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant reachability for directed graphs. In Proc. of the 29th Int'l. Symposium on Distributed Computing (DISC), pages 528-543, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_35.
  6. S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant reachability subgraph: Generic and optimal. In Proc. of the 48th ACM Symposium on Theory of Computing (STOC), pages 509-518, 2016. URL: http://dx.doi.org/10.1145/2897518.2897648.
  7. A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook. Linear-time algorithms for dominators and other path-evaluation problems. SIAM Journal on Computing, 38(4):1533-1573, 2008. URL: http://dx.doi.org/10.1137/070693217.
  8. A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook. A new, simpler linear-time dominators algorithm. ACM Transactions on Programming Languages and Systems, 20(6):1265-1296, 1998. URL: http://dx.doi.org/10.1145/295656.295663.
  9. M. D. Carroll and B. G. Ryder. Incremental data flow analysis via dominator and attribute update. In Proc. of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 274-284, 1988. URL: http://dx.doi.org/10.1145/73560.73584.
  10. S. Chechik, T. D. Hansen, G. F. Italiano, J. Lacki, and N. Parotsidis. Decremental single-source reachability and strongly connected components in Õ(m√n) total update time. In Proc. of the 57th IEEE Symposium on Foundations of Computer Science(FOCS), pages 315-324, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.42.
  11. S. Cicerone, D. Frigioni, U. Nanni, and F. Pugliese. A uniform approach to semi-dynamic problems on digraphs. Theorical Computer Science, 203:69-90, August 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00288-0.
  12. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, 1991. URL: http://dx.doi.org/10.1145/115372.115320.
  13. W. Di Luigi, L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-connectivity in directed graphs: An experimental study. In Proc. of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 173-187, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.15.
  14. D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In M. J. Atallah and M. Blanton, editors, Algorithms and Theory of Computation Handbook, 2nd Edition, Vol. 1, pages 9.1-9.28. CRC Press, 2009. Google Scholar
  15. K. Gargi. A sparse algorithm for predicated global value numbering. SIGPLAN Not., 37(5):45-56, 2002. URL: http://dx.doi.org/10.1145/543552.512536.
  16. L. Georgiadis. Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In Proc. of the 37th Int'l. Coll. on Automata, Languages, and Programming (ICALP), pages 738-749, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_62.
  17. L. Georgiadis. Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. In Proc. of the 19th European Symposium on Algorithms (ESA), pages 13-24, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_2.
  18. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-vertex connectivity in directed graphs. In Proc. of the 42nd Int'l. Coll. on Automata, Languages, and Programming (ICALP), pages 605-616, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_49.
  19. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-edge connectivity in directed graphs. ACM Transactions on Algorithms, 13(1):9:1-9:24, 2016. URL: http://dx.doi.org/10.1145/2968448.
  20. L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. An experimental study of dynamic dominators. In Proc. of the 20th European Symposium on Algorithms (ESA), pages 491-502, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_43.
  21. L. Georgiadis, G. F. Italiano, and N. Parotsidis. Incremental strong connectivity and 2-connectivity in directed graphs. Manuscript, 2017. Google Scholar
  22. L. Georgiadis, G. F. Italiano, and N. Parotsidis. Strong connectivity in directed graphs under failures, with applications. In Proc. of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1880-1899, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.123.
  23. L. Georgiadis and R. E. Tarjan. Finding dominators revisited. In Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 869-878, 2004. Google Scholar
  24. M. Gomez-Rodriguez, L. Song, N. Du, H. Zha, and B. Schölkopf. Influence estimation and maximization in continuous-time diffusion networks. ACM Transactions on Information Systems, 34(2):9:1-9:33, 2016. URL: http://dx.doi.org/10.1145/2824253.
  25. M. Henzinger, S. Krinninger, and V. Loitzenbauer. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In Proc. of the 42nd Int'l. Coll. on Automata, Languages, and Programming (ICALP), pages 713-724, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_58.
  26. M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of the 47th ACM Symposium on Theory of Computing (STOC), pages 21-30, 2015. URL: http://dx.doi.org/10.1145/2746539.2746609.
  27. G. F. Italiano, L. Laura, and F. Santaroni. Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science, 447:74-84, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2011.11.011.
  28. R. Jaberi. Computing the 2-blocks of directed graphs. RAIRO - Theoretical Informatics and Applications, 49(2):93-119, 2015. URL: http://dx.doi.org/10.1051/ita/2015001.
  29. R. Jaberi. On computing the 2-vertex-connected components of directed graphs. Discrete Applied Mathematics, 204:164-172, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.10.001.
  30. J. Lacki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Transactions on Algorithms, 9(3):27, 2013. URL: http://dx.doi.org/10.1145/2483699.2483707.
  31. E. K. Maxwell, G. Back, and N. Ramakrishnan. Diagnosing memory leaks using graph mining on heap dumps. In Proc. of the 16th ACM SIGKDD Int'l. Con. on Knowledge Discovery and Data Mining (KDD), pages 115-124, 2010. URL: http://dx.doi.org/10.1145/1835804.1835822.
  32. M. Mihalák, P. Uznański, and P. Yordanov. Prime factorization of the Kirchhoff polynomial: Compact enumeration of arborescences. In Proc. of the SIAM Analytic Algorithmics and Combinatorics (ANALCO), pages 93-105, 2016. URL: http://dx.doi.org/10.1137/1.9781611974324.10.
  33. K. Patakakis, L. Georgiadis, and V. A. Tatsis. Dynamic dominators in practice. In Proc. of the 16th Panhellenic Conference on Informatics (PCI), pages 100-104, 2011. URL: http://dx.doi.org/10.1109/PCI.2011.28.
  34. L. Quesada, P. Van Roy, Y. Deville, and R. Collet. Using dominators for solving constrained path problems. In Proc. of the 8th International Conference on Practical Aspects of Declarative Languages (PADL), pages 73-87, 2006. URL: http://dx.doi.org/10.1007/11603023_6.
  35. G. Ramalingam and T. Reps. An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In Proc. of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 287-296, 1994. URL: http://dx.doi.org/10.1145/174675.177905.
  36. V. C. Sreedhar, G. R. Gao, and Y. Lee. Incremental computation of dominator trees. ACM Transactions on Programming Languages and Systems, 19:239-252, 1997. URL: http://dx.doi.org/10.1145/202529.202531.
  37. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
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