DAG Transitive Reduction

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.

Worked Example

Consider a graph with 4 vertices and 5 edges: (0,1), (0,2), (1,3), (2,3), (0,3). This represents a "diamond" shape with a direct shortcut.

The edge (0,3) is examined.
We check if vertex 3 is reachable from 0 without using (0,3).
The path 0 → 1 → 3 exists.
Therefore, the edge (0,3) is redundant and removed.
No other alternative paths exist for the remaining edges.

The independently calculated expected result is a reduced edge set containing (0,1), (0,2), (1,3), (2,3). The transitive reduction is unique for DAGs.

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.

Limitations

The transitive reduction is unique only for Directed Acyclic Graphs (DAGs). If a graph contains cycles, the reduction into a subgraph is not uniquely defined without choosing an arbitrary representation of strongly connected components. This module rejects cyclic graphs, setting the Status to "DAG required" and returning "Unavailable" for edge reduction results.

References

The definition and logic for transitive reduction are standard graph theory concepts available in many algorithmic libraries.

NetworkX Transitive Reduction - Details the transitive reduction algorithm for DAGs.

DAG Transitive Reduction