In graph theory, any binary relation R on a set X may be thought of as a directed graph (V, A), where V = X is the vertex set and A = R is the set of arcs of the graph. The transitive reduction of a graph is sometimes referred to as its minimal representation. 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 acyclic graph is unique. For a graph with nontrivial strongly connected components, each such component will become a cycle in any transitive reduction of that graph. More formally, suppose we have a graph G and we form an acyclic graph G' by contracting each strongly connected component to a vertex. If we take the unique transitive reduction of G', then expand each vertex back out to a cycle containing the vertices contracted to form it, attaching incident edges at any vertex in the cycle, the result will be a minimal transitive reduction regardless of how this expansion is performed.
In 1972, it was shown by Aho, Garey, and Ullman that algorithms for transitive reduction have the same time complexity as algorithms for transitive closure.
One of the most well-studied problems in computational graph theory is that of incrementally keeping track of the transitive closure of a graph while performing a sequence of insertions and deletions of vertices and edges. In 1987, J.A. La Poutré and J. van Leeuwen described in their well-cited Maintenance Of Transitive Closures And Transitive Reductions Of Graphs an algorithm for simultaneously keeping track of both the transitive closure and transitive reduction of a graph in this incremental fashion.
The algorithm uses
time for a sequence of consecutive edge insertions and
time for a sequence of consecutive edge deletions, where Eold is the edge set prior to the insertions or deletions and Enew is the edge set afterwards. For acyclic graphs, the deletion algorithm requires only
time. These times are still best-known, as more recent research has preferred to focus on transitive closure.