Network coding is highly non-approximable

We address the network coding problem, in which messages available to a set of sources must be passed through a network to a set of sinks with specified demands. It is known that the problem of deciding whether the demands can be met using a linear code is NP-hard [Lehman and Lehman, SODA ´04]. Such a result is not known if we allow general (=non-linear) codes to be used. Despite this, network coding is believed to be a very hard problem both when restricting to linear codes, and when considering general codes. In the current paper we give some evidence for this hardness. Call a sink happy if it receives all of the data it demands. We show that the problem of maximizing the number of happy sinks by a general network code is NP-hard to approximate to within a multiplicative factor of n^1-¿, for any ¿ > 0. Here, n is the number of sinks. To our knowledge, this is the first hardness result known for general network coding. The same holds for maximizing the number of happy sources. Let n_s be the number of sinks. We also prove a stronger result about linear codes: that given a network that can be satisfied by a linear code, it is NP-hard to find a linear code that makes at least 22 sinks happy. In particular, this means that the problem of maximizing the number of happy sinks in a linear code cannot be approximated to any factor better than n_s/22, even for arbitrarily large n_s - this is the harshest kind of inapproximability possible.