  Functional dependence graph (FDG) is an important class of directed graph
that captures the dominance relationship among a set of variables. FDG is
frequently used in calculating network coding capacity bounds. However, the
order of FDG is usually much larger than the original network and the
computational complexity of many bounds grows exponentially with the order of
FDG. In this paper, we introduce the concept of reduced FDG, which is obtained
from the original FDG by keeping only those "essential" edges. It is proved
that the reduced FDG gives the same capacity region/bounds with the original
FDG, but requiring much less computation. The applications of reduced FDG in
the algebraic formulation of scalar linear network coding is also discussed.
