The transitive reduction of a binary relation 
on a finite set 
is a relation 
on 
with the fewest ordered pairs
having the same transitive closure as 
. For a strict
order, the reduction is unique and satisfies 
iff 
and there is no 
such that 
and 
.
The transitive reduction of a finite directed graph 
has the fewest arcs
among directed graphs on the same vertex
set with the same reachability. When directed cycles
are present, it need not be unique or a subgraph of
(Aho et al. 1972, pp. 131-133).
