This question already has an answer here:

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?


merged by Artem Kaznatcheev Mar 13 '14 at 21:12

This question was merged with Transitivity check vs. Transitive Closure because it is an exact duplicate of that question.

  • $\begingroup$ By virgi's answer to your other question it's probably worths to merge this with the previous one. $\endgroup$ – Saeed Mar 13 '14 at 12:39