Pliable Index Coding via Conflict-Free Colorings of Hypergraphs
Prasad Krishnan, Rogers Mathew, Subrahmanyam Kalyanasundaram · IEEE Transactions on Information Theory · 2024
We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting ofmmessages as vertices and the request-sets of thenclients as hyperedges. Aconflict-free coloringof a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict-free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with lengthO(log2Γ), where Γ is the maximum number of hyperedges overlapping with any hyperedge. For thet-request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Γ logm),O(tlogm)), under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in thet-request case are asymptotically optimal, up to a multiplicative factor of logt. Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability.