Transitive reduction

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 every pair of vertices v and w, a directed path from v to w exists in D if and only if such a path exists in the reduction. In other words, it keeps the same reachability while removing every edge that is not needed. Transitive reductions were introduced by Aho, Garey and Ullman in 1972, who provided tight bounds on the computational complexity of constructing them, which is why the topic is studied as an algorithmic problem as well as a graph concept.