Bipartite index coding

Abstract

We analyze a generalized index coding problem that allows multiple users to request the same packet. For this problem we introduce a novel coding scheme called partition multicast. Our scheme can be seen as a natural generalization of clique cover for directed index coding problems. Further, partition multicast corresponds to an achievable scheme for the generalized bipartite index coding problem that we introduce in this paper. Our scheme partitions the nodes into groups and solves a multicasting problem within each group. We show that Partition Multicast is optimal for a few families of graphs and generalizes previous achievable schemes, namely directed cycle covers. We also show that finding the best partition is computationally intractable to compute in general.