On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint

Yuki TAKEDA  Yuichi KAJI  Minoru ITO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.12   pp.2211-2217
Publication Date: 2016/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.2211
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Networks and Network Coding
Keyword: 
information flow problem,  network coding,  computational complexity,  hierarchy constraint,  mesh network,  

Full Text: PDF>>
Buy this Article



Summary: 
An information flow problem is a graph-theoretical formalization of the transportation of 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 linear solvability of information flow problems, which is to decide if there is a linear network code that is a solution to the given information flow problem. Lehman et al. characterize the linear 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 linear solvability of information flow problems 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.