4
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ All vertices within a single strongly connected component are pairwise comparable. Thus a pair of incomparable vertices exists in a DG iff it exists in a condensation of this DG. So the existence of cycles must not affect the complexity. $\endgroup$ May 7, 2023 at 12:59
  • $\begingroup$ @Johntrik Thanks for the great improvement. Thanks also go to our dear caring omnipresent moderator D.W.! $\endgroup$
    – John L.
    May 8, 2023 at 12:37
  • $\begingroup$ Nice! Thank you for all the edits! $\endgroup$
    – D.W.
    May 8, 2023 at 16:42
  • $\begingroup$ not a linear time algorithm, but just so i understand the problem: if we found lowest common ancestor of the 2 nodes, the 2 nodes would be comparable iff one of the nodes is the ancestor right? $\endgroup$ May 8, 2023 at 16:46

3 Answers 3

6
$\begingroup$

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

  1. Do a topological sorting with a linear algorithm. (Yes, topological sorting is very helpful!).
  2. 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.
  3. 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.

  1. Compute the condensation of the given directed graph, which is a DAG. This can be done by, for example, Kosaraju and Sharir's algorithm.
  2. 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.

$\endgroup$
1
  • 2
    $\begingroup$ Step 1 and step 2 in the first algorithm can be performed together. Ditto for the second algorithm. $\endgroup$
    – John L.
    May 7, 2023 at 18:40
4
$\begingroup$

Observe that if there exists a vertex $u$ that is incomparable with another vertex $v$ in a DAG, then $u$'s order in a topological sort can be changed with respect to $v$. Equivalently, $u$'s position in the topological order is not fixed. Hence, to answer your problem, you just have to find if there is a vertex with no fixed position in a topological sort.

I think you can look at this previously posted problem that asks about getting all vertices with fixed index in their topological ordering of a DAG. Its solution is a modified topological sort algorithm that runs in linear time.

$\endgroup$
4
$\begingroup$

Compute a topological ordering $(v_1, v_2, …, v_n)$ of the DAG. Now consider the recursive following algorithm:

  • if $n = 1$, then there are no incomparable pairs of vertices;
  • if $(v_1, v_2)\notin E$, then $v_1$ and $v_2$ are incomparable (by definition of a topological ordering);
  • otherwise, assume $n\geqslant 2$ and $(v_1, v_2) \in E$. If there exists a vertex $u$ such that $v_1$ and $u$ are incomparable, then $v_2$ and $u$ are incomparable (because there is no path from $u$ to $v_2$, because $v_2$ appears before $u$ in the topological ordering, and there is no path from $v_2$ to $u$, otherwise there would be a path from $v_1$ to $u$). That means that you can make a recursive call on $(v_2, …, v_n)$ to check if there is an incomparable pair of vertices.
$\endgroup$

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.