Reductions techniques for establishing equivalence between different classes of network and index coding problems
Alex Sprintson · 2014
Reductions, or transformations of one problem to the other, are a fundamental tool in complexity theory used for establishing the hardness of discrete optimization problems. Recently, there is a significant interest in using reductions for establishing relationships between different classes of problems related to network coding, index coding, and matroid theory. The goal of this paper is to survey the basic reduction techniques for proving equivalence between network coding and index coding, as well as the establishing relations between the index coding problem and the problem of finding a linear representation of a matroid. The paper reviews recent advances in the area and discusses open research problems.