Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.
The following image displays drawings of graphs corresponding to a non-transitive binary relation (on the left) and its transitive reduction (on the right).
The transitive reduction of a finite directed acyclic graph G is unique, and consists of the edges of G that form the only path between their endpoints.
For this reason, the transitive reduction coincides with the minimum equivalent graph in this case.
When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates the covering relation of the partial order, which is frequently given visual expression by means of a Hasse diagram.
The edges of the transitive reduction that correspond to condensation edges can always be chosen to be a subgraph of the given graph G. However, the cycle within each strongly connected component can only be chosen to be a subgraph of G if that component has a Hamiltonian cycle, something that is not always true and is difficult to check.
In this construction, the nonzero elements of the matrix AB represent pairs of vertices connected by paths of length two or more.
[3] To prove that transitive reduction is as hard as transitive closure, Aho et al. construct from a given directed acyclic graph G another graph H, in which each vertex of G is replaced by a path of three vertices, and each edge of G corresponds to an edge in H connecting the corresponding middle vertices of these paths.
[3] When measured both in terms of the number n of vertices and the number m of edges in a directed acyclic graph, transitive reductions can also be found in time O(nm), a bound that may be faster than the matrix multiplication methods for sparse graphs.
To do so, apply a linear time longest path algorithm in the given directed acyclic graph, for each possible choice of starting vertex.
From the computed longest paths, keep only those of length one (single edge); in other words, keep those edges (u,v) for which there exists no other path from u to v. This O(nm) time bound matches the complexity of constructing transitive closures by using depth-first search or breadth first search to find the vertices reachable from every choice of starting vertex, so again with these assumptions transitive closures and transitive reductions can be found in the same amount of time.
The reachable sets obtained during the algorithm describe the transitive closure of the input.