Hardness of Linear Index Coding on Perturbed Instances
Dror Chawin, Ishay Haviv · IEEE Transactions on Information Theory · 2023
The index coding problem is concerned with the amount of information that a sender has to transmit to multiple receivers in a way that enables each of them to retrieve its requested data relying on prior side information. For linear index coding, the problem is characterized by the minrank parameter of a graph that represents the side information map of the receivers. Previous work has shown that it is$\mathsf {NP}$-hard to determine the minrank parameter of graphs. In this work, we study the computational complexity of the minrank parameter on perturbed instances, obtained from worst-case instances by a random extension of the side information available to the receivers. This setting is motivated by applications of index coding, in which the side information is accumulated via repeated transmissions that suffer from loss of data due to noisy communication or storage capacity. We prove that determining the minrank parameter remains computationally hard on perturbed instances. Our contribution includes an extension of several hardness results of the minrank parameter to the perturbed setting as well as a general technique for deriving the hardness of the minrank parameter on perturbed instances from its hardness on worst-case instances.