Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function.
Show that given a directed graph (not necessarily DAG) $G^{'}$, we can calculate it's transitive closure, $G^{+}=(V, E^{+})$, in time complexity of $O(f(|V|, |E|) + |V| + |E^{+}|)$.
We can assume all the graphs are represented in adjacency matrices.
I don't have any idea for this one. I tried to read stuff about this topic, including in cormen's book, but it didn't lead me to any solution.


1 Answer 1


Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time.

The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the transitive closure of the metagraph.

Now to compute $G^+$:

  • if $u$ and $v$ are in the same SCC, that means there is an edge from $u$ to $v$ and from $v$ to $u$;
  • if $u\in C$ and $v\in C'$ where $C$ and $C'$ are two different SCC such that there is an edge from $C$ to $C'$ in the transitive closure of the metagraph, that means there is an edge from $u$ to $v$ (but not from $v$ to $u$).

All this can be done in the required complexity.


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.