1
$\begingroup$

As part of pre-processing my (very large) directed acyclic graph, I want to eliminate as many unnecessary edges as possible. By "unnecessary" I mean an edge that could be absent from the transitive reduction of the graph. For example, in the graph {(1 -> 2), (2 -> 3), (1 -> 3)}, edge (1 -> 3) is considered unnecessary.

As far as I know, there is no way to exactly compute transitive reduction faster than corresponding matrix multiplication which is why I'm looking for an approximation.

Is there a practical algorithm that can remove most of unnecessary edges in linear time? The algorithm must preserve reachability but may leave more edges than needed.

$\endgroup$
1
  • $\begingroup$ I clarified the question. By "unnecessary" I mean an edge that could be absent from the transitive reduction of the graph. $\endgroup$ Sep 8 at 16:27

0

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.