# Algorithm for the transitive reduction of a DAG

I'm looking for an algorithm for the transitive reduction of a digraph (a DAG in fact).

The wikipedia article displays a formula R- = R - (R × R+) — where R- is the transitive reduction of R and R+ is the transitive closure of R — but that Cartesian product doesn't form an edge (unless I'm missing something), so how can I take away from R?

For example, say 3 depends on 2 and 1, and 2 depends on 1. The edges of this graph G are (2, 1), (3, 1), and (3, 2).

I'm expecting the reduction to be G' = {(2, 1), (3, 2)}. The transitive closure of G is G, right?

-
The product $\times$ is composition, i.e. $x (R \times R^+) y$ iff there is $z$ such that $x R z$ and $z R^+ y$. – Yuval Filmus Dec 24 '10 at 2:01