As Aho et al. show, so this result put transitive reduction into the same class. The
best exact algorithms for matrix multiplication, as of 2023, take time O(
n2.371552), 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.
Computing the reduction using the closure 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 let
A be the
adjacency matrix of the given directed acyclic graph, and
B be the adjacency matrix of its transitive closure (computed using any standard transitive closure algorithm). Then an edge
uv belongs to the transitive reduction if and only if there is a nonzero entry in row
u and column
v of matrix
A, and there is a zero entry in the same position of the matrix product
AB. In this construction, the nonzero elements of the matrix
AB represent pairs of vertices connected by paths of length two or more.
Computing the closure using the reduction To prove that transitive reduction is as hard as transitive closure, Aho et al. construct from a given directed acyclic graph
G another graph
H, in which each vertex of
G is replaced by a path of three vertices, and each edge of
G corresponds to an edge in
H connecting the corresponding middle vertices of these paths. In addition, in the graph
H, Aho et al. add an edge from every path start to every path end. In the transitive reduction of
H, there is an edge from the path start for
u to the path end for
v, if and only if edge
uv does not belong to the transitive closure of
G. Therefore, if the transitive reduction of
H can be computed efficiently, the transitive closure of
G can be read off directly from it.
Computing the reduction in sparse graphs When measured both in terms of the number
n of vertices and the number
m 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 for
sparse graphs. To do so, apply a
linear time longest 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 from
u to
v. This O(
nm) time bound matches the complexity of constructing transitive closures by using
depth-first search or
breadth 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.
Output-sensitive For a graph with
n vertices,
m edges, and
r edges in the transitive reduction, it is possible to find the transitive reduction using an
output-sensitive algorithm in an amount of time that depends on
r in place of
m. The algorithm is: • For each vertex
v, in the reverse of a
topological order of the input graph: • Initialize a set of vertices reachable from
v, initially the singleton set {
v}. • For each edge
vw, in topological order by
w, test whether
w is in the reachable set of
v, and if not: • Output edge
vw as part of the transitive reduction. • Replace the set of vertices reachable from
v by its union with the reachable set of
w. The ordering of the edges in the inner loop can be obtained by using two passes of
counting sort or another
stable 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 as
bit arrays, each set union operation can be performed in time
O(
n), or faster using
bitwise operations. The number of these set operations is proportional to the number of output edges, leading to the overall time bound of
O(
nr). The reachable sets obtained during the algorithm describe the transitive closure of the input. If the graph is given together with a partition of its vertices into
k chains (pairwise-reachable subsets), this time can be further reduced to
O(
kr), by representing each reachable set concisely as a union of suffixes of chains. ==Notes==