Reduced functional dependence graphs

Functional dependence graph (FDG) is an important class of directed graph that captures the functional dependence relationships of a set of random variables and it is frequently used in characterising network coding capacity bounds. Since the computational complexity of such bounds usually grows exponentially with the order of the FDG, it is desirable to find an FDG with the smallest size possible. To this end, some systematic graph reduction techniques are introduced in this study. The first reduction technique is performed on the original networks, where 'non-essential' edges are identified and eliminated. This is equivalent to node reduction in the corresponding FDG. Besides, the authors show that certain edges in the FDG may also be removed without affecting the functional dependence relationships of the random variables. The removal of the edges in the FDG may create new opportunities to reduce the order of the FDG. It is proved that the reduced FDGs give the same network coding capacity region/bounds as that obtained by using the original FDGs and yet much less computation is required.