TR04-034 Authors: April Rasala Lehman, Eric Lehman

Publication: 13th April 2004 17:31

Downloads: 2814

Keywords:

We consider the general network information flow problem, which was

introduced by Ahlswede et. al. We show a periodicity effect: for

every integer m greater than 1, there exists an instance of the

network information flow 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 doubly exponential in m.

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 that has size only

exponential in m. In light of these results, we suggest that a more

appropriate model would assume that the network operates at slightly

under capacity.