In mathematics, a transitive reduction of a binary relation R on a set X is a minimal relation on X such that the transitive closure of is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then is unique. However, neither existence nor uniqueness of transitive reductions is guaranteed in general.
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 directed acyclic graph is unique.
Graph algorithms for transitive reduction
Here, denotes relation composition.
- they extend the computation of transitive reduction from transitive closure to deal with cycles;
- they give a construction to compute a graph's transitive closure from its transitive reduction;
- thus, transitive closure and transitive reduction have the same time complexity.
Incremental data structures
One of the most well-studied problemsTemplate:Cn 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 Jan 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.Template:Cn