# Approximate/iterative algorithm for transitive reduction of DAG

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.

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