3
$\begingroup$

I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph G(V, E) and is the time complexity not O(|V|+|E|):

Use Kosaraju's to compute SCCs (strongly connected components) -- O(|V| + |E|)

Create a DAG from the SCCs as (super)nodes -- O(|V| + |E|)

In a single supernode, reachability of all nodes is the same and equal to the union of the nodes in the containing supernode plus the reachable supernodes in the DAG -- O(|V| + |E|) to compute reachability in the DAG and O(|V| * |V|) total to compute reachability sets for all nodes

These reachability sets do constitute the transitive closure of the graph wholly, right?
But there aren't any O(|V| + |E|) transitive closure algorithms around.
What am I missing?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your algorithm is known as Purdom's algorithm. There are two versions of transitive closure:

  • Calculate the transitive closure as a relation. This cannot run in time $O(|V|+|E|)$, since the output could be bigger than that (consider a directed path, for example).
  • Calculate enough information to be able to answer oracle queries to the transitive closure in $O(1)$. Even in this case, the algorithm doesn't seem to run in time $O(|V|+|E|)$. Hopefully the link would make it clear why.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot. This pretty much answers it. Just a couple of things: 1. What exactly is, the transitive closure as a relation? -- shortest paths between all nodes? And, are those oracle queries, limited to, is u reachable from v, or do they include other queries? $\endgroup$
    – user2268997
    Commented Jun 5, 2019 at 15:58
  • $\begingroup$ By “transitive closure” as a relation, I mean all pairs of points $(x,y)$ such that $y$ is reachable from $x$. Regarding oracle queries, you’re probably correct, but I suggest reading the link. $\endgroup$
    – Yuval Filmus
    Commented Jun 5, 2019 at 16:01
  • $\begingroup$ So the above algorithm runs in O(|E|+|V|^2) according to the link. And given this, the reachability set for each node can be computed in O(|V|), which would give us O(|V|^2) for computing reachability sets for all nodes, i.e the transitive closure. This gives us a O(|E|+|V|^2) transitive closure computation. $\endgroup$
    – user2268997
    Commented Jun 5, 2019 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.