All-Pairs 2-Reachability in O(n^w log n) Time

Authors Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, Przemyslaw Uznanski



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.74.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Loukas Georgiadis
Daniel Graf
Giuseppe F. Italiano
Nikos Parotsidis
Przemyslaw Uznanski

Cite AsGet BibTex

Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemyslaw Uznanski. All-Pairs 2-Reachability in O(n^w log n) Time. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.74

Abstract

In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair of vertices u and v. In this paper, we present an algorithm that computes 2-reachability information for all pairs of vertices in O(n^w log n) time, where n is the number of vertices and w is the matrix multiplication exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.
Keywords
  • 2-reachability
  • All Dominator Trees
  • Directed Graphs
  • Boolean Matrix Multiplication

Metrics

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

References

  1. N. Alon, Z. Galil, O. Margalit, and M. Naor. Witnesses for boolean matrix multiplication and for shortest paths. In Proc. of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pages 417-426. IEEE, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267748.
  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. 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.
  4. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001. Google Scholar
  6. M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In Proc. of the 12th Annual Symposium on Switching and Automata Theory (SWAT), pages 129-131. IEEE, 1971. URL: http://dx.doi.org/10.1109/SWAT.1971.4.
  7. W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. Finding dominators via disjoint set union. Journal of Discrete Algorithms, 23:2-20, 2013. URL: http://dx.doi.org/10.1016/j.jda.2013.10.003.
  8. 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.
  9. 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.
  10. 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.
  11. R. Jin, Y. Xiang, N. Ruan, and H. Wang. Efficiently answering reachability queries on very large directed graphs. In Proc. of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 595-608, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1376616.1376677.
  12. V. King and G. Sagert. A fully dynamic algorithm for maintaining the transitive closure. Journal of Computer and System Sciences, 65(1):150-167, 2002. URL: http://dx.doi.org/10.1006/jcss.2002.1883.
  13. F. Le Gall. Powers of tensors and fast matrix multiplication. In Proc. of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296-303, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2608628.2608664.
  14. T. Lengauer and R. E. Tarjan. A Fast Algorithm for Finding Dominators in a Flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-41, 1979. URL: http://dx.doi.org/10.1145/357062.357071.
  15. K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927. Google Scholar
  16. R. E. Tarjan. Finding dominators in directed graphs. SIAM Journal on Computing, 3(1):62-89, 1974. URL: http://dx.doi.org/10.1137/0203006.
  17. V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 887-898, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214056.
  18. R. Yuster. All-pairs disjoint paths from a common ancestor in Õ(n^ω) time. Theoretical Computer Science, 396(1):145-150, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.01.032.
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