Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to determine if a digraph is transitive or not?
Transitivity check vs. Transitive Closure
graph theory;directed acyclic graph;transitive closure