2015/04/25 by Fatemeh Arbabjolfaei, Arbabjolfaei, Fatemeh, Young-Han Kim +1 · 1 citation
Computer Science · Engineering · #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1504.06760
openalex publication_date 2015/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The question of under what condition some side information for index coding can be removed without affecting the capacity region is studied, which was originally posed by Tahmasbi, Shahrasbi, and Gohari. To answer this question, the notion of unicycle for the side information graph is introduced and it is shown that any edge that belongs to a unicycle is critical, namely, it cannot be removed without reducing the capacity region. Although this sufficient condition for criticality is not necessary in general, a partial converse is established, which elucidates the connection between the notion of unicycle and the maximal acylic induced subgraph outer bound on the capacity region by Bar-Yossef, Birk, Jayram, and Kol.