Linear network coding, linear index coding and representable discrete polymatroids

Abstract

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field F_q, with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over F_q exists for a network if and only if the network is matroidal with respect to a matroid representable over Fq. We define a discrete polymatroidal network and show that a linear fractional solution over a field F_q exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over F_q. An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over F_q for the discrete polymatroid, results in a linear fractional solution over F_q for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X = {x₁, x₂, . . . x_q}, and a set of receivers R, which demand messages. A receiver R ∈ R is specified by the tuple (x, H), where x ∈ X is the message demanded by R and H ⊆ X \ {x} is the side information possessed by R. We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.