Given a directed graph $G = (V, E)$, the goal is to decide whether there exists a path between $u$ and $v$ for every pair $(u, v) \in V \times V$ of two vertices. Of course, we can do that by the Floyd-Warshall algorithm in time $\mathcal{O}(n^3)$. But that gives us extra information which is not asked for: We have computed for every pair of vertices the shortest path, if there is one. That's not relevant, because the question is: Is there one pair $(u, v) \in V \times V$ of vertices with no between between $u$ and $v$ or is the whole graph a strongly connected component?Notice: I read this thread (https://stackoverflow.com/questions/3517524/best-known-transitive-closure-algorithm-for-graph) and the time complexity may be improved by matrix multiplication algorithms. But I'm actually sure that I don't want to have a solution involving the Coppersmith-Winograd algorithm, because it's useless in practice.Is it possible to decide this decision problem in a more efficient way?
Deciding whether a directed graph is a transitive closure
algorithms;graphs;time complexity