Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

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?

Here is a linear-time algorithm that decides whether a DAG contains at least one incomparable pair of nodes.

• Do a topological sorting with a linear algorithm. (Yes, topological sorting is very helpful!).

• For each pair of adjacent nodes in the topological order obtained, check if there is an edge between them. If there isn't, return TRUE.

• Return FALSE.

Why is this algorithm correct?

For a DAG, no incomparable pair of nodes is equivalent to the uniqueness of a topological order, which in turn is equivalent to a unique Hamiltonian path in the DAG.

In the general case of a directed graph, either acyclic or cyclic, here is a linear-time algorithm.

• Compute the condensation of the given directed graph, which is a DAG. This can be done by, for example, Kosaraju and Sharir's algorithm.

• Run the algorithm above on the DAG obtained. Return what it returns.

Why is this algorithm correct?

As Vladislav Bezhentsev commented, a pair of incomparable nodes exists in a directed graph iff it exists in a condensation of that graph.

StackExchange Computer Science Q#160031, answer score: 6