I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes.
Two nodes $u$, $v$ are said to be incomparable if there is neither a path from $u$ to $v$ nor a path from $v$ to $u$.
I can't see a linear solution to this. We can do a DFS for each pair $(u,v)$ and $(v,u)$ as in here. However, this approach does not lead to linear complexity.
The fact that it is a DAG hints topological order but is this useful?
Can this also be done with linear time complexity for directed cyclic graphs?