Complexity classification of network information flow problems

ABSTRACT

We address the network information flow problem, in which messages available to a set of sources must be passed through a network to a set of sinks with specified demands. This differs from traditional multicommodity flow, because information can be duplicated and encoded. Previous work has focused on the special case of multicasting using linear coding. In this paper, we explore the applicability of network coding to a breadth of problems and consider the greater potential of nonlinear coding techniques. Our main contribution is a taxonomy of network information flow problems. We establish a three-way partition consisting of problems solvable without resorting to network coding, problems requiring network coding that are polynomial-time solvable, and problems for which obtaining a linear network coding solution is NP-hard. We also demonstrate limitations of linear coding: for multicasting, nonlinear codes may employ a smaller alphabet than any linear code and, more generally, there exist solvable information flow problems that do not admit a linear solution.

REFERENCES

• 1: Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204--1216, July 2000.
• 2: Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
• 3: Tracey Ho, David Karger, Muriel Médard, and Ralf Koetter. Network coding from a network flow perspective. In IEEE International Symposium on Information Theory, 2003.
• 4: Ralf Koetter and Muriel Médard. Beyond routing: An algebraic approach to network coding. In INFOCOM, 2002.
• 5: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 6: Shuo-Yen Robert Li, Raymond W. Yeung, and Ning Cai. Linear network coding. IEEE/ACM Transactions on Information Theory, 49:371--381, 2003.
• 7: Peter Sanders, Sebastian Egner, and Ludo Tolhuizen. Polynomial time algorithms for network information flow.