Italiano, Giuseppe F.
- Conference Paper
Rights / licenseCreative Commons Attribution 3.0 Unported
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. Show more
Book title44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Journal / seriesLeibniz International Proceedings in Informatics
Pages / Article No.
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Subject2-reachability; All dominator trees; Directed graphs; Boolean matrix multiplication
Organisational unit03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
MoreShow all metadata