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 all pairs v, w of vertices, a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D. Equivalently, D and its transitive reduction should have the same transitive closure as each other, and the transitive reduction of D should have as few edges as possible among all graphs with that property. The transitive reduction of a finite directed acyclic graph (a directed graph without directed cycles) is unique and is a subgraph 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 a minimum equivalent graph is a subgraph of D that has the same reachability relation and as few edges as possible. The difference is that a transitive reduction does not have to be a subgraph of D; it can contain edges not in the original D. For finite directed acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are NP-hard to construct, while transitive reductions can be constructed in polynomial time. Transitive reduction can be defined for an abstract binary relation on a set, by interpreting the pairs of the relation as arcs in a directed graph.
Classes of graphs
In directed acyclic graphs The transitive reduction of a finite directed graph G is a graph with the fewest possible edges that has the same reachability relation as the original graph. That is, if there is a path from a vertex x to a vertex y in graph G, there must also be a path from x to y in the transitive reduction of G, 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 finite directed acyclic graph G is unique, and consists of the edges of G that form the only path between their endpoints. In particular, it is always a spanning subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case. In the mathematical theory of binary relations, any relation R on a set X may be thought of as a directed graph that has the set X as its vertex set and that has an arc xy for every ordered pair of elements that are related in R. In particular, this method lets partially ordered sets be reinterpreted as directed acyclic graphs, in which there is an arc xy in the graph whenever there is an order relation x < 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 the covering relation of the partial order, which is frequently given visual expression by means of a Hasse diagram. Transitive reduction has been used on networks which can be represented as directed acyclic graphs (e.g. citation graphs or citation networks) to reveal structural differences between networks.
In graphs with cycles 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 graph G. If G is an arbitrary directed graph, and H is a graph with the minimum possible number of edges having the same reachability relation as G, then H consists of
A directed cycle for each strongly connected component of G, connecting together the vertices in this component An edge xy for each edge XY of the transitive reduction of the condensation of G, where X and Y are two strongly connected components of G that are connected by an edge in the condensation, x is any vertex in component X, and y is any vertex in component Y. The condensation of G is a directed acyclic graph that has a vertex for every strongly connected component of G and an edge for every two components that are connected by an edge in G. In particular, because it is acyclic, its transitive reduction can be defined as in the previous section. 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 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. Because of this difficulty, it is NP-hard to find the smallest subgraph of a given graph G with the same reachability (its minimum equivalent graph).
… excerpt ends here. Continue reading the full article.
