DAG Transitive Reduction
Remove redundant arrows while preserving every directed reachability relation.
Free theory articleRemove redundant arrows while preserving every directed reachability relation.
Concept & interpretation
Transitive reduction of a directed acyclic graph (DAG) is a graph with the same vertices and the same reachability relation as the original, but with a minimal number of edges. An edge is redundant if there exists an alternative path of length greater than or equal to two between its endpoints.
Experiment
You can interactively explore transitive reduction using the module: https://riano.app/module/dag-transitive-reduction.
- Select the Graph "Diamond shortcut".
- Observe that the Original edges count is 5.
- The module calculates the Reduced edges as 4 and Removed edges as 1.
- Select Probe source 0. The reachable vertices from 0 are shown as
1, 2, 3. - Change the Graph to "Chain shortcuts". Here, edges like
(0,2), (0,4), (1,3)will be marked as redundant and removed.