An Equivalence between Network Coding and Index Coding

Abstract

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.

Additional details