Transitive reduction

Summary

In the mathematical field of graph theory, a transitive reduction of a directed graph $D$ is another directed graph with the same vertices and as few edges as possible, such that for all pairs $v$, $w$ of vertices, a (directed) path from $v$ to $w$ in $D$ exists if and only if such a path exists in the reduction. Transitive reductions were introduced by (Aho Garey Ullman 1972), who provided tight bounds on the computational complexity of constructing them.