Finding three transmissions is hard
Arash Saber Tehrani, Alexandros G. Dimakis · 2012
We investigate a fundamental wireless broadcast problem called Index coding. We focus on binary linear scalar index coding problems when it is a-priori known that the optimal solution requires three transmissions. For this case, we characterize the relation of the clique cover number of the side information graph G and the optimal index code. This allows us to show that even when there is a-priori knowledge that three transmissions can solve a given index coding problem, finding these transmissions is NP-hard. Another implication of our results is that for three solvable undirected problems, the benefit of interference alignment solutions is at most one compared to a simple clique cover.