Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
Ok, thanks, you can add your response as an answer to get best answer. –  ladaghini Dec 24 '10 at 3:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.