On the Broadcast Rate and Fractional Clique Cover of Single Unicast Index Coding Problems

摘要

The broadcast rate β of an index coding problem is the minimum number of index code symbols required to transmit to satisfy the demands of all the receivers. The linear broadcast rate β(l) of an index coding problem is the minimum number of index code symbols obtained by linear encoding by using a encoding matrix. Blasiak et al. defined the fractional clique cover number of an undirected graph and used it to bound the broadcast rate of an index coding problem. Lubetzky et al. proved that nonlinear codes can outperform linear codes. In this paper, we find the fractional clique cover number of two classes of symmetric index coding problems. For single unicast index coding problems with symmetric consecutive and neighboring side-information, we prove that broadcast rate is equal to the fractional clique cover number. We define m-dimensional vector index code of an index coding problem by using disjunctive product of side-information graph. We prove that if linear broadcast rate is equal to fractional clique cover number, then, linear broadcast rate is equal to broadcast rate.