Pliable Index Coding via Conflict-Free Colorings of Hypergraphs

Krishnan, P. and Mathew, R. and Kalyanasundaram, S. (2021) Pliable Index Coding via Conflict-Free Colorings of Hypergraphs. In: 2021 IEEE International Symposium on Information Theory (ISIT), 12 July 2021 through 20 July 2021, Melbourne, Virtual.

[img] Text

Download (388kB)


In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the PICOD problem. A conflict-free coloring of a hypergraph is known from literature as an assignment of colors to its vertices so that each edge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as edges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new coloring variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Our achievable schemes based on hypergraph coloring include scalar as well as vector linear PICOD schemes. For the scalar case, using the correspondence with conflict-free coloring, we show the existence of an achievable scheme which has length O(\textbackslashlog⌃{2}\textbackslashGamma), where \textbackslashGamma refers to a parameter of the hypergraph that captures the maximum 'incidence' number of other edges on any edge. This result improves upon known achievability results in PICOD literature, in some parameter regimes. © 2021 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Mathew, Rogers
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Additional Information: ISSN: 2157-8095
Uncontrolled Keywords: Achievability; Conflict-Free Colorings; Graph-theoretic; Hypergraph coloring; Index coding; Multiple clients; Parameter regimes; Side information
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 19 May 2022 06:46
Last Modified: 19 May 2022 06:46
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9260 Statistics for this ePrint Item