Hypergraph-based Techniques for Pliable Index Coding

Abstract

The Index Coding problem is a well known problem setting in the field of coding theory. A variant of this, called Pliable Index Coding (PICOD), was introduced in [5]. It is called ”pliable” because there are multiple valid decoding choices whereas the index coding problem has only one valid decoding choice. Finding the optimal code length for both the index coding problem and the PICOD problem is computationally NP-hard. Hence various coding schemes have been proposed, with varying performance guarantees. Those coding schemes were designed by representing the PICOD problem in alternate ways. These achievability schemes upper bound the optimal length of the pliable index code. Lower bounds have also been obtained in prior literature by utilizing information-theoretic arguments. Following this trend, by representing the PICOD problem as a hypergraph, we obtain a new upper bound and lower bound. The parameter that obtains the lower bound is a novel parameter of the hypergraph representation of the PICOD problem, and an algorithm to obtain it from a given PICOD problem is also described. The upper bound parameter is the maximum degree of any vertex in the hypergraph representation of the PICOD problem, and it gives simple upper bound for the optimal length of the PICOD problem. These two bounds are shown to be tight for a class of PICOD problems. Another upper bound was also explored viz. Γ which is another parameter related to the hypergraph representation of the PICOD problem. Additionally, when this parameter is small, it is possible to categorize and analyze each class of the PICOD problem exhaustively, which was also done.