Transitive reduction

In mathematics, a transitive reduction of a directed graph is a graph with as few edges as possible that has the same reachability relation as the given graph. Equivalently, the given graph and its transitive reduction should have the same transitive closure as each other, and its transitive reduction should have as few edges as possible among all graphs with this property. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.