In themathematical field ofgraph theory, atransitive reduction of adirected graphD is another directed graph with the samevertices and as few edges as possible, such that for all pairs of verticesv,w a (directed)path fromv tow inD existsif and only if such a path exists in the reduction. Transitive reductions were introduced byAho, Garey & Ullman (1972), who provided tight bounds on thecomputational complexity of constructing them.
More technically, the reduction is a directed graph that has the samereachability relation asD. Equivalently,D and its transitive reduction should have the sametransitive closure as each other, and the transitive reduction ofD should have as few edges as possible among all graphs with that property.
The transitive reduction of a finitedirected acyclic graph (a directed graph withoutdirected cycles) is unique and is asubgraph of the given graph. However, uniqueness fails for graphs with (directed) cycles, and for infinite graphs not even existence is guaranteed.
The closely related concept of aminimum equivalent graph is a subgraph ofD that has the same reachability relation and as few edges as possible.[1] The difference is that a transitive reduction does not have to be a subgraph ofD. For finitedirected acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs areNP-hard to construct, while transitive reductions can be constructed inpolynomial time.
Transitive reduction can be defined for an abstractbinary relation on aset, by interpreting the pairs of the relation as arcs in a directed graph.
The transitive reduction of a finitedirected graphG is a graph with the fewest possible edges that has the samereachability relation as the original graph. That is, if there is a path from a vertexx to a vertexy in graphG, there must also be a path fromx toy in the transitive reduction ofG, and vice versa. Specifically, if there is some path from x to y, and another from y to z, then there may be no direct edge from x to z in the transitive reduction.Transitivity for x, y, and z means that if x < y and y < z, then x < z. If for any path from y to z there is a path x to y, then there is a path x to z; however, it is not true that for any paths x to y and x to z that there is a path y to z, and therefore any edge between vertices x and z are excluded under a transitive reduction, as they represent walks which are not transitive. 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 finitedirected acyclic graphG is unique, and consists of the edges ofG that form the only path between their endpoints. In particular, it is always aspanning subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case.
In the mathematical theory ofbinary relations, any relationR on a setX may be thought of as adirected graph that has the setX as its vertex set and that has an arcxy for everyordered pair of elements that are related inR. In particular, this method letspartially ordered sets be reinterpreted as directed acyclic graphs, in which there is an arcxy in the graph whenever there is an order relationx < y between the given pair of elements of the partial order. When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates thecovering relation of the partial order, which is frequently given visual expression by means of aHasse diagram.
Transitive reduction has been used on networks which can be represented as directed acyclic graphs (e.g.citation graphs orcitation networks) to reveal structural differences between networks.[2]
In a finite graph that has cycles, the transitive reduction may not be unique: there may be more than one graph on the same vertex set that has a minimum number of edges and has the same reachability relation as the given graph. Additionally, it may be the case that none of these minimum graphs is a subgraph of the given graph. Nevertheless, it is straightforward to characterize the minimum graphs with the same reachability relation as the given graphG.[3] IfG is an arbitrary directed graph, andH is a graph with the minimum possible number of edges having the same reachability relation asG, thenH consists of
The total number of edges in this type of transitive reduction is then equal to the number of edges in the transitive reduction of the condensation, plus the number of vertices in nontrivial strongly connected components (components with more than one vertex).
The edges of the transitive reduction that correspond to condensation edges can always be chosen to be a subgraph of the given graphG. However, the cycle within each strongly connected component can only be chosen to be a subgraph ofG if that component has aHamiltonian cycle, something that is not always true and is difficult to check. Because of this difficulty, it isNP-hard to find the smallest subgraph of a given graphG with the same reachability (its minimum equivalent graph).[3]
Aho et al. provide the following example to show that ininfinite graphs, even when the graph is acyclic, a transitive reduction may not exist. Form a graph with a vertex for eachreal number, with an edge whenever as real numbers. Then this graph is infinite, acyclic, and transitively closed. However, in any subgraph that has the same transitive closure, each remaining edge can be removed without changing the transitive closure, because there still must remain a path from to through any vertex between them. Therefore, among the subgraphs with the same transitive closure, none of these subgraphs is minimal: there is no transitive reduction.[3]
As Aho et al. show,[3] when thetime complexity of graph algorithms is measured only as a function of the numbern of vertices in the graph, and not as a function of the number of edges, transitive closure and transitive reduction of directed acyclic graphs have the same complexity. It had already been shown that transitive closure andmultiplication ofBoolean matrices of sizen × n had the same complexity as each other,[4] so this result put transitive reduction into the same class. Thebest exact algorithms for matrix multiplication, as of 2023, take time O(n2.371552),[5] and this gives the fastest known worst-case time bound for transitive reduction in dense graphs, by applying it to matrices over the integers and looking at the nonzero entries in the result.
To prove that transitive reduction is as easy as transitive closure, Aho et al. rely on the already-known equivalence with Boolean matrix multiplication. They letA be theadjacency matrix of the given directed acyclic graph, andB be the adjacency matrix of its transitive closure (computed using any standard transitive closure algorithm). Then an edgeuv belongs to the transitive reduction if and only if there is a nonzero entry in rowu and columnv of matrixA, and there is a zero entry in the same position of the matrix productAB. In this construction, the nonzero elements of the matrixAB 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 graphG another graphH, in which each vertex ofG is replaced by a path of three vertices, and each edge ofG corresponds to an edge inH connecting the corresponding middle vertices of these paths. In addition, in the graphH, Aho et al. add an edge from every path start to every path end. In the transitive reduction ofH, there is an edge from the path start foru to the path end forv, if and only if edgeuv does not belong to the transitive closure ofG. Therefore, if the transitive reduction ofH can be computed efficiently, the transitive closure ofG can be read off directly from it.[3]
When measured both in terms of the numbern of vertices and the numberm 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 forsparse graphs. To do so, apply alinear timelongest 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 fromu tov. This O(nm) time bound matches the complexity of constructing transitive closures by usingdepth-first search orbreadth 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.
For a graph withn vertices,m edges, andr edges in the transitive reduction, it is possible to find the transitive reduction using anoutput-sensitive algorithm in an amount of time that depends onr in place ofm. The algorithm is:[6]
The ordering of the edges in the inner loop can be obtained by using two passes ofcounting sort or anotherstable sorting algorithm to sort the edges, first by the topological numbering of their end vertex, and secondly by their starting vertex. If the sets are represented asbit arrays, each set union operation can be performed in timeO(n), or faster usingbitwise operations. The number of these set operations is proportional to the number of output edges, leading to the overall time bound ofO(nr). The reachable sets obtained during the algorithm describe the transitive closure of the input.[6]
If the graph is given together with a partition of its vertices intok chains (pairwise-reachable subsets), this time can be further reduced toO(kr), by representing each reachable set concisely as a union of suffixes of chains.[7]