The transitive reduction of a binary relation on a set is the minimum relation on with the same transitive closure as . Thus for any elements and of , provided that and there exists no element of such that and .
The transitive reduction of a graph is the smallest graph such that , where is the transitive closure of (Skiena 1990, p. 203).