On the Conjectures on Optimality of Index Codes from Interlinked Cycle Cover Scheme

The interlinked cycle (IC) structure, that generalizes cycles and cliques was defined by Thapa, Ong and Johnson. Interlinked-cycle-cover (ICC) scheme that leverages IC structures in digraphs to construct scalar linear index codes was proposed. Thapa et. al. conjectured that for any IC structure, the ICC scheme is optimal. It was also conjectured that for any digraph, the ICC scheme performs at least as well as the partial-clique-cover scheme. In this paper, we disprove both the conjectures. We also show that for a specific class of symmetric index coding problems, the performance of ICC scheme is equal to that of the partial-clique-cover scheme