1
$\begingroup$

I have a DAG and I want to list all pairs of vertices that are not comparable (there is no path from the first to the second or the second to the first).

In this image (taken from this StackOverflow question):

enter image description here

The output would this:

{B,C}
{B,D}

The output can be $O(n^2)$ so that's a lower bound. My current best algorithm is:

  • For each vertex X,
    • Run a search in the graph and note all reachable vertices, then do the same with the direction of arrows reversed.
    • Output {X,Y} for each vertex Y that you did not reach this way.

But that appears to be $O(nm + n^2)$.

I'm interested in either a faster algorithm or a proof that a faster algorithm doesn't exist.

I tried maintaining a list of predecessors in each node and going through the graph layer-by-layer with a BFS, but the existence of either edges within layers (if I layer by shortest path) or of shortcut edges (such as possibly from A to D in the example above) kept that from working.

$\endgroup$
1
  • $\begingroup$ There has been extensive research on its complementary problem, computing the transitive closure of a directed acyclic graph. We can also search for "reachability". $\endgroup$ – John L. Dec 16 '19 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.