On the computational complexity of the solvability of information flow problem with hierarchy constraint

An information flow problem discusses how to transport information over a complicated network. It is known that a linear network code plays an essential role in a certain type of information flow problems, but it is not understood clearly how contributing linear network codes are for other types of information flow problems. One basic problem concerning this aspect is the solvability of information flow problems, which is to decide if there is a linear network code that can be a solution to the given information flow problem. Lehman et al. characterize the solvability of information flow problems in terms of constraints on the sets of source and sink nodes. As an extension of Lehman´s investigation, this study introduces a hierarchy constraint of messages, and discusses the computational complexity of the solvability of an information flow problem with the hierarchy constraints. Nine classes of problems are newly defined, and classified to one of three categories that were discovered by Lehman et al.