On the Optimal Broadcast Rate of the Two-Sender Unicast Index Coding Problem With Fully-Participated Interactions

Chinmayananda Arunachala, Vaneet Aggarwal, B. Sundar Rajan

Abstract

This paper addresses the Two-Sender Unicast Index Coding Problem (TUICP) specifically under "fully-participated interactions." By leveraging a graph-theoretic decomposition strategy, the authors characterize the optimal broadcast rates for complex interaction types. The study effectively reduces the two-sender problem to a combination of three single-sender sub-problems, providing exact solutions for cases that previously lacked tight bounds.

Introduction

The Index Coding Problem (ICP) is a fundamental challenge in information theory where a sender aims to deliver specific messages to receivers who already possess some side-information. The goal is to minimize the broadcast rate—the total number of transmissions required. The Two-Sender variant (TUICP) introduces a distributed setting where messages are split between two senders.

This research focuses on "fully-participated interactions," a class of problems where side-information dependencies are uniform across message groups. While prior work established optimal rates for acyclic interaction digraphs, this paper extends the characterization to cases involving cycles (Case II) and improves achievable rates for specific acyclic configurations (Case I).

Methodology: Sub-problem Decomposition

The core of the authors' approach is the decomposition of the interaction digraph $D$ into three distinct single-sender sub-problems. Messages are partitioned based on their availability:

  1. $P_1$: Messages held exclusively by Sender 1.
  2. $P_2$: Messages held exclusively by Sender 2.
  3. $P_3$: Messages held by both senders.

This partitioning induces three sub-digraphs ($D_1, D_2, D_3$), as illustrated in the following figure.

Decomposition of the interaction digraph into sub-problems $D_1, D_2$, and $D_3$.

By analyzing these sub-problems using confusion graphs and specialized two-sender graph coloring techniques, the authors determine the total broadcast rate as a function of the individual sub-problem rates ($\beta(D_i)$).

Key Results and Optimal Rates

The primary contribution of this work is the exact characterization of the optimal broadcast rate $\beta(D^{k,P})$ for all Case II interaction types. The results demonstrate that the optimal rate is often determined by the "bottleneck" sub-problems.

Summary of optimal broadcast rates for various interaction cases.

As shown in the table above, the optimal rates for Case II-C and II-D are defined by the sum of one sub-problem rate and the maximum of the remaining two. For the most complex cyclic case, II-E, the rate is the maximum of the pairwise sums of the three sub-problem rates: $$\beta(D^{k,P}) = \max\{\beta(D^{k,P}_1) + \beta(D^{k,P}_2), \beta(D^{k,P}_1) + \beta(D^{k,P}_3), \beta(D^{k,P}_2) + \beta(D^{k,P}_3)\}$$

Additionally, for six specific sub-cases of Case I (acyclic), the authors established the first non-trivial achievable rates by exploiting symmetries in the confusion graph to optimize the coloring process.

Conclusion and Future Directions

This work provides a structural reduction that simplifies the TUICP under fully-participated interactions to the well-studied single-sender ICP. While the single-sender problem remains NP-Hard, this reduction provides a clear path to calculating optimal rates for multi-sender scenarios.

Future research is needed to address "partially-participated" interactions, where side-information is not uniform, and to extend these results to scenarios involving three or more senders, which present significantly higher combinatorial complexity.

Summary updated

Abstract

The problem of two-sender unicast index coding consists of two senders and a set of receivers. Each receiver demands a unique message not demanded by any other receiver and has a subset of messages as its side information. Every demanded message is available with at least one of the senders. The senders avail the knowledge of the side information at all the receivers to reduce the total number of transmissions required to satisfy the demands of all the receivers. The objective is to find the minimum total of number of transmissions per message length (known as the optimal broadcast rate with finite length messages) and its limiting value as the message length tends to infinity (called the optimal broadcast rate). Achievable broadcast rates are provided for a class of the two-sender unicast index coding problem based on a special graph coloring technique called two-sender graph coloring. This result illustrates the utility of graph products in the two-sender unicast index coding problem for the first time in the literature. For another class, achievable broadcast rates are provided based on the optimal broadcast rates of three single-sender sub-problems with finite message length. This employs a code construction for the two-sender unicast index coding problem using optimal codes (including non-linear codes) of the sub-problems. Optimal broadcast rates are provided for a special class of the TUICP for which only an upper bound was known prior to this work. The optimal broadcast rates presented in this work also consider non-linear coding schemes at the two senders.
BibTeX
@article{arunachala2018optimal,
  author = {Chinmayananda Arunachala and Vaneet Aggarwal and B. Sundar Rajan},
  title = {{On the Optimal Broadcast Rate of the Two-Sender Unicast Index Coding Problem With Fully-Participated Interactions}},
  journal = {IEEE Trans. Communications},
  year = {2018},
  doi = {10.1109/tcomm.2019.2941470},
}
Figure