Reduced Functional dependence graphs and their applications

Functional dependence graphs (FDG) are an important class of directed graph that capture the functional dependence relationship among a set of random variables. FDGs are frequently used in characterizing and calculating network coding capacity bounds. However, the order of an FDG is usually much larger than the original network and the complexity of computing bounds grows exponentially with the order of an FDG. In this paper, we introduce graph pre-processing techniques which deliver reduced FDGs. These reduced FDGs are obtained from the original FDG by removing nodes that are not “essential”. We show that the reduced FDGs give the same capacity region/bounds obtained using original FDGs, but require much less computation. The application of reduced FDGs for algebraic formulation of scalar linear network coding is also discussed.