All-pairs 2-reachability in O(n^ n) time

DOI10.4230/LIPICS.ICALP.2017.74zbMATH Open1441.68183arXiv1612.08075OpenAlexW2741640338MaRDI QIDQ5111405FDOQ5111405

Loukas Georgiadis, Nikos Parotsidis, Przemysław Uznański, Daniel Graf, Giuseppe F. Italiano

Publication date: 27 May 2020

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 a 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 $mathcalO(n^{omega}logn)$ time, where $n$ is the number of vertices and $omega$ 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 $mathcalO(n^2)$ additional time, which in turn enables us to answer various connectivity queries in $mathcalO(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$.

Full work available at URL: https://arxiv.org/abs/1612.08075

Recommendations

• 2-vertex connectivity in directed graphs
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• 2-vertex connectivity in directed graphs
• Incremental 2-edge-connectivity in directed graphs
• 2-Edge Connectivity in Directed Graphs

zbMATH Keywords

directed graphsBoolean matrix multiplication2-reachabilityall-dominator trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cited In (3)

• An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: All-pairs 2-reachability in \(\mathcal{O}(n^\omega\log n)\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111405)