An Equivalence between Network Coding and Index Coding
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and non-linear 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.
© 2015 IEEE. This material is based upon work supported by ISF grant 480/08, BSF grant 2010075, and NSF grants CCF-1018741 and CCF-1016671. The work was done while Michael Langberg was visiting the California Institute of Technology. S. El Rouayheb would like to thank Prof. Vincent Poor for his continuous support, and Curt Schieler for interesting discussions on the index coding problem.