Network Coding: Does the Model Need Tuning?
April Rasala Lehman, Eric Lehman · Symposium on Discrete Algorithms · 2004
We consider the general network information flow problem, which was introduced by Ahlswede et. al[1]. We show a periodicity effect: for every integer m ≥ 2, there exists an instance of the network information ow problem that admits a solution if and only if the alphabet size is a perfect mth power. Building on this result, we construct an instance with O(m) messages and O(m) nodes that admits a solution if and only if the alphabet size is an enormous 2exp(Ω(m1/3)). In other words, if we regard each message as a length-k bit string, then k must be exponential in the size of the network. For this same instance, we show that if edge capacities are slightly increased, then there is a solution with a modest alphabet size of O(2m). In light of these results, we suggest that a more appropriate model would assume that the network operates at slightly under capacity.