An Equivalence Between Network Coding and Index Coding
Michelle Effros, Salim El Rouayheb, Michael L. Langberg · IEEE Transactions on Information Theory · 2015
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and nonlinear codes. Specifically, we present a reduction that maps a network coding instance to an index coding instance while preserving feasibility, i.e., the network coding instance has a feasible solution if and only if the corresponding index coding instance is feasible. In addition, we show that one can determine the capacity region of a given network coding instance with colocated sources by studying the capacity region of a corresponding index coding instance. Previous connections between network and index coding were restricted to the linear case.