The Transitive Reduction of a Directed Graph

Abstract

We consider economical representations for the path information in a directed graph. A directed graph $G^t $ is said to be a transitive reduction of the directed graph G provided that (i) $G^t $ has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than $G^t $ satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.