9

Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon>0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying ...


7

It looks like that $\Omega(n^2)$ is the best known lower bound, since any lower bound implies a lower bound for boolean matrix multiplication. We know that transitivity check can be achieved using one boolean matrix multiplication, that is, $G$ is transitive if and only if $G = G^2$.


6

Compact reachability oracles exist for planar graphs, Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004) but are "hard" for general graphs (even sparse graphs) Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011) Nevertheless, ...


4

I'll answer your question partially: there seem to be some reasons why such a construction may be hard to obtain. Suppose that given any n-node m-edge directed graph you could preprocess it in T(m,n) time so that reachability queries can be answered in q(m,n) time. Then, for instance, you could find a triangle in an n-node m-edge graph in $T(O(m),O(n))+n q(...


4

Figuring if a DAG is transitive is as hard as deciding if a general digraph is transitive (which bring us back to your previous question :) ). Assume you have an algorithm running in time $O(f(n))$ for deciding if a DAG is transitive. Given a directed graph $G$, you can use the following randomized algorithm to decide if $G$ is transitive in time $O(f(n)\...


1

I think this should be feasible in linear time, i.e. $O(n+m)$ where $n$ is the number of vertices and $m$ the number of edges. Maybe by adapting some graph traversal scheme to the directed setting? A starting point could be the LexBFS / LexDFS described here; for directed graphs it seems that we should use topological sorting rather than DFS, so maybe it's ...


1

Due to [Aho, Garey, and Ullman, The transitive reduction of a directed graph, 1972]; $G^t = G - GG^+$, where $G^t$ is the transitive reduction of $G$. In this particular case, $G = G^+$. So, we can conclude $G^t = G - G^2$. Although this result does not lead to a linear non-approximate algorithm, I hope such an observation would be helpful in this context.


Only top voted, non community-wiki answers of a minimum length are eligible