LIPIcs.ICALP.2017.74.pdf
- Filesize: 0.71 MB
- 14 pages
Document
All-Pairs 2-Reachability in O(n^w log n) Time
Authors
-
Part of:
Volume:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-07-07
Cite As Get 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.
Subject Classification
Keywords
- 2-reachability
- All Dominator Trees
- Directed Graphs
- Boolean Matrix Multiplication
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- 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.
- 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.
- 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.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927.
- 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.
- 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.
- 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.