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:
- $P_1$: Messages held exclusively by Sender 1.
- $P_2$: Messages held exclusively by Sender 2.
- $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.
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.
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