2026-07-21T11:11:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7451 2024-03-06T10:40:25Z ddc:004 open_access

All-Pairs 2-Reachability in O(n^w log n) Time Georgiadis, Loukas Graf, Daniel Italiano, Giuseppe F. Parotsidis, Nikos Uznanski, Przemyslaw 2-reachability All Dominator Trees Directed Graphs Boolean Matrix Multiplication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Daniel Graf and Giuseppe F. Italiano and Nikos Parotsidis and Przemyslaw Uznanski 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.74 urn:nbn:de:0030-drops-74510 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.74 eng https://creativecommons.org/licenses/by/3.0/legalcode