DRAFT

1

Structural Characteristics of Two-Sender Index
Coding

arXiv:1711.08150v1 [cs.IT] 22 Nov 2017

Chandra Thapa, Lawrence Ong, Sarah J. Johnson, and Min Li

Abstract
This paper studies index coding with two senders. In this setup, source messages are distributed
among the senders (possibly with overlapping of messages). In addition, there are multiple receivers,
where each receiver having some messages a priori, known as side-information, is requesting one
unique message such that each message is requested by only one receiver. Index coding in this setup
is called two-sender unicast index coding (TSUIC). The main goal is to find the shortest aggregate
encoded messages while allowing all receivers to decode their requested messages. Firstly, we form three
independent sub-problems of a TSUIC problem based on whether the requested messages by receivers
of those sub-problems are available only in one of the senders or in both senders. Then we express
the optimal broadcast rate (the shortest normalized codelength) of the TSUIC problem as a function of
the optimal broadcast rates of those independent sub-problems. In this way, we devise the structural
characteristics of TSUIC. For the proofs of our results, we apply the notion of confusion graphs and
a code-forming technique. To color a confusion graph in TSUIC, we introduce a new graph-coloring
approach (different from the normal graph coloring), called two-sender graph coloring, and propose
a way of grouping the vertices to analyze the number of colors used. Finally, we determine a class
of TSUIC instances where a certain type of side-information can be removed without affecting their
optimal broadcast rates.

I. I NTRODUCTION
Consider a communication scenario over a noiseless channel where a sender is required
to broadcast messages to multiple receivers, each caching some messages requested by other
receivers a priori. The messages cached at each receiver is known as its side-information. In this
scenario, if the sender is informed about the side-information available at all receivers, then it
The authors are with the School of Electrical Engineering and Computing, The University of Newcastle, Callaghan,
NSW 2308, Australia (email: chandra.thapa@uon.edu.au, lawrence.ong@newcastle.edu.au, sarah.johnson@newcastle.edu.au,
min.li@newcastle.edu.au).

November 23, 2017

DRAFT

DRAFT

2

can leverage that information while encoding to reduce the required number of transmissions in
comparison with a naive approach of transmitting all requested messages uncoded and separately.
Such an encoding process, where the messages are encoded into a sequence of coded messages
by utilizing the knowledge of side-information available at each receiver (in such a way that each
receiver is able to decode its required message upon receiving all transmitted coded messages and
utilizing its side-information) is called index coding. The sequence of coded messages broadcast
by the sender is known as an index code. The main aim of index coding is to find an index code
with the optimal (shortest) codelength for an index-coding instance. Index coding was introduced
by Birk and Kol [1], [2], and further studied in subsequent works [3]–[12].
Most of the earlier works on index coding deal only with a single sender, capturing scenarios
with centralized transmissions. However, many communication scenarios such as the following
have messages distributed among multiple senders:
•

Macro-cell networks with caching helpers [13] — cellular networks deploying special nodes,
called helpers, with large storage capacity instead of femto-cell access points to offload its
backhaul,

•

cooperative data exchange [14] — peer-to-peer networks with data exchange within a group
of closely-located wireless nodes, and

•

distributed storage — storage networks where data are distributed over multiple storage
devices/locations.

In addition, each sender can be constrained to know only a subset of total messages because
of various reasons such as limited storage, or error while receiving some messages over noisy
channels, or server failure. In this case, distributed transmissions are required (more than one
sender broadcasts messages to the receivers), and we aim to minimize the total number of
transmissions from all senders in such a way that all receivers’ demands will be fulfilled. As this
problem is more general than an index-coding problem with a single sender, and is of practical
interest (e.g., reducing delay in content delivery, and energy efficient broadcasting), it is a useful
research avenue to study index-coding problems with multiple senders, known as multi-sender
index-coding problems.
A. Prior works
In multi-sender index coding, based on the problem formulation, we broadly group the problems
into two categories, viz., (i) broadcast rate formulation, and (ii) capacity region formulation. In the

November 23, 2017

DRAFT

DRAFT

3

broadcast rate formulation of the problems, the senders are connected to receivers via noiseless
broadcast links (orthogonal to each other) with flexible capacities, and we aim to characterize
the total transmitted bits per received message bits of those problems. On the other hand, in the
capacity region formulation of the problems, the senders are connected to receivers via noiseless
broadcast links of arbitrary fixed capacities, and we aim to characterize the closure of the set of
all achievable rate tuples1 of messages of those problems.
The multi-sender index-coding problem was first studied by Ong et al. [15]. They considered
the broadcast rate formulation of the problems, and presented results by implementing a graphtheoretic approach (which requires finite length messages). At the senders’ end, they considered
multiple senders each knowing only a subset of the messages. At the receivers’ end, they
considered a single-uniprior message setting, meaning each receiver knows only one message
requested by some other receiver a priori, one message is known to only one receiver, and one
receiver may request multiple messages. For this setup, they devised lower and upper bounds on
the optimal broadcast rate.2 The results were established using information-flow graphs, which
represent receivers’ request, and message graphs, which represent senders’ message setting.
Furthermore, they showed that their upper and lower bounds coincide for a class of problem
instances where no two senders have messages in common. In another work, Thapa et al. [16],
considered a similar model (to the model considered by Ong et al.) but with a unicast message
setting, meaning each message is requested by only one receiver, each receiver requests only one
message, and each receiver knows a subset of messages requested by other receivers a priori.
Based on a graph-theoretic approach, they established upper bounds on the optimal broadcast
rate. In particular, they focused on the two-sender case, called two-sender unicast index coding
(TSUIC). They extended existing single-sender index-coding schemes, namely the cycle-cover
scheme [17], [18], the clique-cover scheme [1], [2] and the local-chromatic scheme [10] to the
corresponding schemes in TSUIC.
So far, works on the capacity region formulation of the problems use a random-coding approach
(which requires infinitely long messages). Inner and outer bounds on the capacity region have
1

Consider a message xi of ti bits requested by receiver i. A rate tuple of messages is achievable if there exists an index

code such that each rate Ri in the tuple is less than or equal to the respective message bits ti per total transmitted bits.
2

The total transmitted bits per received message bits is referred to as the broadcast rate. The optimal broadcast rate is the

minimum over all possible broadcast rates for an index coding instance. It is also the reciprocal of the symmetric capacity, the
supremum of equal achievable rates.

November 23, 2017

DRAFT

DRAFT

4

been developed. The first general inner bound is due to Sadeghi et al. [19] and is attained by a
partitioned distributed-composite-coding scheme, which is built on the single-sender compositecoding scheme (an existing single-sender scheme that is based on a random-coding approach,
[7]). This scheme is further enhanced to a fractional distributed-composite-coding scheme by Liu
et al. [20]. Preliminary and improved polymatroidal outer bounds were also developed in the
work by Sadeghi et al. [19] and Liu et al. [20], respectively. As a result, the capacity region
is established for all problem instances up to 3 receivers, and the sum capacity is established
for all instances with 4 receivers and with unit link capacity from each sender. Independent of
and in parallel with the work by Liu et al. [20], Li et al. [21] proposed two new achievable
schemes that can strictly improve partitioned distributed-composite-coding scheme. In particular,
they introduced techniques of joint link-and-sender partitioning and cooperative compression of
composite messages, and developed a new multi-sender cooperative composite-coding scheme.
B. Our work and contributions
Different approaches have been attempted to solve the multi-sender index-coding problems.
However, the problems are more difficult and computationally complex than its single-sender
counterparts, and we know very little about the characteristics of the problems. This paper studies
the broadcast rate formulation of TSUIC problems by implementing a graph-theoretic approach.
More precisely, in the same spirit of studying structural properties of index-coding capacity in
single-sender case by Arbabjolfaei et al. [8], we examine the structural characteristics of TSUIC
problems. This kind of study embraces the "divide-and-conquer" approach, and provides us an
insight about the problems where we can solve a big problem by solving its smaller sub-problems.
Note that in the work by Arbabjolfaei et al. [8], [22], the capacity region of a given single-sender
index-coding problem is shown to be a simple function of the capacity regions of its independent
sub-problems by generalizing the notion of lexicographic graph product. In TSUIC setup, due to
the distributed message setting among senders, we can not directly implement the notion of graph
products and the existing approaches of single-sender index coding. In this work, we consider
interactions between three independent sub-problems at a time in TSUIC setup. By applying
the notion of confusion graphs in index coding [23] along with the introduction of a two-sender
graph coloring and a code-forming technique, we bound the optimal broadcast rate (tight for
some classes of TSUIC instances) in both asymptotic and non-asymptotic regimes. Moreover,
even for the single-sender cases, the non-asymptotic cases (especially index coding in non-linear

November 23, 2017

DRAFT

DRAFT

5

finite fields) are less explored. For an index coding instance in the unicast message setting and
the non-asymptotic regime in the message size, our techniques in this paper can be used to upper
bound the optimal broadcast rate of this instance by a function of the optimal broadcast rates of
its sub-instances in single-sender unicast index coding.
This study helps us answer some basic questions as follows:
•

Given a TSUIC instance, what is its optimal rate of transmission?

•

Under what conditions distributed encoding in TSUIC achieves the same optimal broadcast
rate of centralized encoding?

•

Which side-information are not useful in the sense that we can remove it without changing
the optimal broadcast rate of TSUIC problems?

In particular, this paper contributes the following for TSUIC:
1) Introducing two-sender graph coloring of confusion graphs in TSUIC (Definition 8,
Section V): In TSUIC problems, as the two senders (encoders) contain some messages in
common, the standard way of graph coloring of the confusion graph may not lead us to an
index code. In this regard, we need a different kind of coloring function in TSUIC, and
thus, in this paper, we propose a novel way of coloring dedicated especially to color the
confusion graphs in TSUIC.
2) Presenting a way of grouping the vertices of confusion graphs in TSUIC (Section VI):
By exploiting the symmetry of the confusion graph, we propose a way of grouping its
vertices for analysis purposes mainly in its two-sender graph coloring. In particular, this
grouping helps us to analyze the number of colors used in two-sender graph coloring of a
confusion graph.
3) Deriving the optimal broadcast rates of TSUIC problems as a function of the optimal
broadcast rates of its sub-problems (Theorem 4–9): We divide a TSUIC problem into
three independent sub-problems based on the requested messages by receivers, whether
the messages are present in only one of the senders or in both senders. Now in TSUIC,
considering the interactions between these three independent sub-problems, we derive the
optimal broadcast rate (in both asymptotic and non-asymptotic regimes in the message size)
of the problem as a function of the optimal broadcast rates of its sub-problems. Moreover,
we bound the optimal broadcast rate, and show that the bounds are tight for classes of
TSUIC instances (sometimes with conditions). Besides, we find a class of TSUIC instances

November 23, 2017

DRAFT

DRAFT

6

where a TSUIC scheme can achieve the same optimal broadcast rate as the same instances
when the two senders form a single sender having all messages.
4) Characterizing a class of TSUIC instances where a certain type of side-information
are not critical (Corollary 1): For a class of TSUIC instances, we prove that certain
interactions (defined by side-information available at the receivers) between the three
independent sub-problems can be removed without affecting its optimal broadcast rate (in
the asymptotic regime). This means that those interactions are not critical.
II. P ROBLEM D EFINITIONS AND G RAPHICAL R EPRESENTATION
A. Problem setup
In this paper, we consider the following unicast index-coding instance. There are N independent
messages M = {x1 , x2 , . . . , xN }, where xi ∈ {0, 1}t for all i ∈ {1, 2 . . . , N } and some integer
t ≥ 1, i.e., each message consists of t binary bits. There are N receivers {1, 2, . . . , N }, where
each receiver r ∈ {1, 2, . . . , N } requests a message xr , and has an ordered set Hr ⊆ M \ {xr } of
messages as its side-information a priori. This paper deals with the following two types of unicast
index coding (UIC) based on the number of senders: (i) Single-sender unicast index coding
(SSUIC) — it has only one sender, denoted S, having all N messages M, and (ii) two-sender

unicast index coding (TSUIC) — it has two senders, denoted by S1 and S2 , having (ordered3 )
message sets M1 ⊆ M and M2 ⊆ M, respectively, such that M1 ∪ M2 = M (i.e., each
message is available at some sender(s)). In other words, the total messages are distributed over
the two senders in TSUIC. Fig. 1 illustrates an example of TSUIC problems with four receivers.
Given an index-coding problem, a two-sender index code is defined as follows:
Definition 1 (Two-sender index code): A two-sender index code ({Fs }, {Gr }), for s ∈ {1, 2},
r ∈ {1, 2, . . . , N }, is defined by

i) an encoding function for each sender Ss , Fs : {0, 1}|Ms |×t → {0, 1}ps such that Cs =
Fs (Ms ), and

2

ii) a decoding function for every receiver r, Gr : {0, 1}(Σs=1 ps +|Hr |×t) → {0, 1}t such that
xr = Gr (C1 , C2 , Hr ).

3

The elements are ordered in increasing indices.

November 23, 2017

DRAFT

DRAFT

7

M1 = {x1 , x2 , x3 }

M2 = {x3 , x4 }

S1

Senders

S2

C1

Receivers

H1

1

= {x2 , x4 }

H2

C2

2

= {x1 , x4 }

x1

H3

3

= {x1 , x2 }

x2

H4

4

= {x1 , x2 }

x3

x4

Fig. 1. An example of a TSUIC problem with four receivers: The total message set M = M1 ∪ M2 is distributed among two
senders S1 and S2 . Each sender is connected to all receivers via a noiseless broadcast channel. Each receiver, r ∈ {1, 2, 3, 4},
having some side-information, which is represented by a set Hr , requests a unique message xr . We assume that each sender
Ss , s ∈ {1, 2}, is broadcasting a sub-codeword Cs of length |Cs |, and they cooperate with each other to reduce their aggregate
transmissions. Precisely, we aim to find a two-sender index code with the minimum sum of lengths |C1 | + |C2 |.

This means each sender Ss encodes its known messages to a ps -bit sub-codeword, for some
non-negative integer ps . We assume that each receiver r receives sub-codewords from both of
the two senders without any noise, and decodes xr from the received sub-codewords and Hr .
Now we define the minimum encoding length, which measures the performance of a code
(C1 , C2 ), in the following.
Definition 2 (Broadcast rate or index codelength): The broadcast rate of an index code (with
single sender or two senders) is the total number of transmitted bits (if two senders, then it is a
sum of transmitted bits by both senders) per received message bits. In TSUIC, it is denoted by
`TSUIC , and `TSUIC ,

(p1 +p2 )
t

for an index code ({Fs }, {Gr }). It is referred to as the codelength

of the index code. We say that ` is achievable for a UIC problem if there exists an index code
of length `.
Definition 3 (Optimal broadcast rate): The optimal broadcast rate for a given index-coding
problem with t-bit messages is βt , min `, where E = F for SSUIC and E = {Fs } for TSUIC.
E,{Gr }

The optimal broadcast rate over all t is defined as β , inf βt = lim βt . The limit exists and
t

t→∞

equal to the infimum due to the subadditivity of tβt = p1 + p2 and Fekete’s lemma [24].
Remark 1: With the (optimal) broadcast rate as a performance metric, we can treat SSUIC as
a special case of TSUIC when M1 = M or M2 = M. Furthermore, for this case, the sender
with M alone will be responsible to fulfill the demands made by all receivers.

November 23, 2017

DRAFT

DRAFT

8

B. Representation of the receivers’ side-information and the senders’ message setting of TSUIC
problems
An index-coding problem can be modeled by graphs, which are defined as follows:
Definition 4 (Directed graphs and undirected graphs): A directed graph is an ordered pair
D = (V (D), A(D)), where V (D) is a set of vertices, and A(D), usually called an arc set, is
a set of ordered pairs of vertices. An undirected graph is an ordered pair G = (V (G), E(G)),
where V (G) is a set of vertices, and E(G), usually called an edge set, is a set of unordered
pairs of vertices.
From now on in this paper, we call directed graphs simply digraphs, and undirected graphs
simply graphs.
The receivers’ message setting of a UIC problem is represented by a side-information digraph
D = (V (D), A(D)), where V (D) = {1, 2, . . . , N } represents the N receivers, and the arc
set A(D) represents the side-information available at each receiver. More precisely, an arc
(i, j) ∈ A(D) exists from vertex i to vertex j if and only if receiver i has packet xj (the
message requested by receiver j) in its side-information. So, in a side-information digraph,
Hi , {xj : j ∈ ND+ (i)}, where ND+ (i) is the out-neighborhood of a vertex i in D. In this paper,
for convenience, a receiver i is also referred to as a vertex i, and vice versa. We also use the
compact form of representation of an instance of UIC problems as used by Arbabjolfaei et al. [7],
where a sequence (i|ND+ (i)), for all i ∈ V (D), represents a UIC problem.
In TSUIC, S1 (sender one) encodes the messages in M1 , and S2 (sender two) encodes the
messages in M2 in order to achieve the optimal broadcast rate βt . In general, each sender has
private messages and common messages defined as follows: Let P1 , M1 \ M2 and P2 ,
M2 \ M1 be the set of private messages at senders S1 and S2 , respectively, and P3 , M1 ∩ M2
be the set of common messages at both senders. Now for a given side-information digraph D,
without loss of generality, we define the following vertex-induced sub-digraphs those dividing
D in to three parts: For i ∈ {1, 2, 3}, let Di be the sub-digraph of D induced by vertices
{j : xj ∈ Pi }. We refer to D1 , D2 and D3 as per this definition throughout this paper unless
stated otherwise. From the definition, it is clear that D1 , D2 and D3 are the three sub-digraphs
of D such that V (D) = V (D1 ) ∪ V (D2 ) ∪ V (D3 ) and V (Di ) ∩ V (Dk ) = ∅ for any i 6= k,
i, k ∈ {1, 2, 3}. In TSUIC, the senders are limited to transmit only their messages, and this
limitation is defined formally as a constraint due to the two senders, and it is defined as follows:

November 23, 2017

DRAFT

DRAFT

9

Definition 5 (Constraint due to the two senders): The constraint due to the two senders is the
following: While encoding, any two private messages xi ∈ P1 and xj ∈ P2 should not be encoded
together (with or without other messages) to construct one coded symbol, or alternatively any
two-sender index code can be written as (C1 , C2 ) such that C1 = F1 (M\P2 ) and C2 = F2 (M\P1 ).
In TSUIC, to reflect the senders’ message setting, we introduce an undirected graph, denoted
by Go = (V (Go ), E(Go )), that is constructed in the following way: (i) V (Go ) = V (D), and (ii)
for all i, j ∈ V (Go ), an undirected arc, i.e., an edge (i, j) ∈ E(Go ) if and only if i ∈ V (D1 ) and
j ∈ V (D2 ), or vice versa. This means, there is an edge connecting two vertices in Go if and
only if no sender contains both the messages requested by those vertices. We call the graph Go
the sender-constraint graph.
As a TSUIC problem is described by D and Go , it is represented by (D, Go ) in this paper. For
a given (D, Go ), let `(D, Go ) denote the index codelength, βt (D, Go ) and β(D, Go ) represent
the optimal broadcast rate for a fixed t, and over all t, respectively. `(D), βt (D) and β(D) are
the respective terms used for single-sender cases.
III. A

NOVEL WAY OF INVESTIGATING

TSUIC PROBLEMS

In a TSUIC problem, if there is no common message, i.e., P3 = ∅, then in our earlier work, we
have proved that the problem is equivalent to two separate SSUIC problems ([16, Theorem 1]).
However, if P3 6= ∅, then the problem is less well understood. We propose to understand this
problem by dividing it into three sub-problems based on the type of messages at the senders
(whether they are common or private), and then study the interactions among these sub-problems
due to the side-information present at the receivers. In this way, we can devise the structural
characteristics of TSUIC problems. For a given problem D, the three sub-problems based on
the type of messages are D1 , D2 and D3 . The side-information present at receivers of one
sub-problem about messages requested by receivers of other sub-problems are formally referred
to as an interaction between those sub-problems, defined in the following. We will see that
this allows us to derive βt (D, Go ) in terms of {βt (Di ) : i ∈ {1, 2, 3}} for a number of TSUIC
instances.
1) Interactions between D1 , D2 and D3 : Arcs between V (D1 ), V (D2 ) and V (D3 ), each
originating from some vertices of V (Di ), i ∈ {1, 2, 3}, and terminating at some vertices of
V (D) \ V (Di ) in D are called an interaction between D1 , D2 and D3 . It is called a fullyparticipated interaction between D1 , D2 and D3 if and only if we have the following: If

November 23, 2017

DRAFT

DRAFT

10

D0

H

D

4D 5

f (D)

3

3

1
1

2
D1

3
D2

(a)

4D 5

0

H0

3

f (D )

3

2

1
1

2
D1

2

3
D2

(b)

Fig. 2. (a) An example of the fully participated interaction between D1 , D2 and D3 of a side-information digraph D along with
the digraph H (having three vertices) obtained by mapping D by the function f , and (b) an example of the partially participated
interaction between D1 , D2 and D3 of a side-information digraph D0 along with the digraph H 0 obtained by mapping D0 by
the function f .

there exists an arc from a vertex of Di to a vertex of Dj for any i, j ∈ {1, 2, 3}, i 6= j, then
V (Dj ) ⊆ ND+ (r) for every r ∈ V (Di ). In other words, all the vertices of the sub-digraph
Di interact in the same way to all the vertices of the sub-digraph Dj . For an example of a
fully-participated interaction see Fig. 2a. If an interaction between the sub-digraphs is not a
fully-participated interaction, then it is called a partially-participated interaction between the
sub-digraphs. For example of a partially-participated interaction see Fig. 2b. For any D, if
V (Di ) ⊆ ND+ (r) for all r ∈ V (Di ) and i 6= j, i, j ∈ {1, 2, 3}, then it is denoted as Di → Dj . If
we write Di  Dj , then it means Di → Dj and Dj → Di . Now for simplicity, an interaction
between the sub-digraphs D1 , D2 and D3 of D can be viewed as an interaction between three
vertices, where each vertex represents one of the sub-digraphs. In this regard, we define a function
that maps a digraph D (with its sub-digraphs D1 , D2 and D3 ) to a digraph having three vertices,
denoted H, in the following: f : D → H such that (i) all the vertices in V (Di ) are mapped to a
single vertex i of H, so V (H) = {1, 2, 3}, and (ii) (i, j) ∈ A(H) if and only if there exist an
arc (u, v) ∈ A(D) for any u ∈ V (Di ) and v ∈ V (Dj ). For example see Fig. 2. By referring to
the definition of the fully or partially participated interaction, one can find that for a given D1 ,
D2 and D3 of D, we can retrieve D by observing f (D) if D has a fully-participated interaction
between the sub-digraphs, but this is not true if D has a partially-participated interaction between
the sub-digraphs. Observe that for any D, if Di → Dj , then it infers i → j in f (D) (i.e., H),
and vice-versa. Now considering the digraph H, we get a total of 64 possible cases of orientation
of arcs between its vertices. Depending upon the type of orientation of arcs between the vertices
of H, we broadly classify all of these cases into two parts: (i) CASE I — Acyclic orientation
(25 cases in total), and (ii) CASE II — with some cyclic orientation (39 cases). The CASE II

November 23, 2017

DRAFT

DRAFT

11

1

2
(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

CASE II-B

CASE II-A
CASE II-C
CASE II-D
CASE II-E

CASE II (With Some Cyclic Orientations)

CASE I (Acyclic Orientations)

3

(1)

(30)

(31)

(32)

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

(42)

(43)

(44)

(45)

(46)

(47)

(48)

(49)

(50)

(51)

(52)

(53)

(54)

(55)

(56)

(57)

(58)

(59)

(60)

(61)

(62)

(63)

(64)

(20)

Fig. 3. All possible interactions between the vertices of H. The digraph of a number i is labeled by Hi , i ∈ {1, 2, . . . , 64}. For
example, the digraph of the number 30 is labeled H30 .

is further classified into smaller sub-cases II-A, II-B, II-C, II-D and II-E. Refer to Fig. 3 for
details, where a case of H is labeled by Hi for i ∈ {1, 2, . . . , 64}. Note that an interaction
between D1 , D2 and D3 of D defines arcs between them (not within the sub-digraph), and the
cases of interactions (acyclic or cyclic) are defined with respect to the orientation of the arcs
between the sub-digraphs. In this paper, a fully-participated interaction and a partially-participated
interaction between D1 , D2 and D3 of D are called a cyclic-fully-participated interaction and
a cyclic-partially-participated interaction between the sub-digraphs, respectively, if and only if
f (D) has some cycles (for example, see CASE II in Fig. 3).

November 23, 2017

DRAFT

DRAFT

12

In SSUIC, Arbabjolfaei and Kim [8, Prop. 1] argued that the structural properties can reduce the
number of problems that need to be studied. This paper investigates the structural characteristics
of TSUIC problems for the same purpose by studying the interactions among D1 , D2 and D3
of D. Moreover, structural properties can be used to determine the criticality/non-criticality of
arcs in TSUIC as in its SSUIC counterpart [9], [25]. In this work, an arc is said to be critical if
removing the arc strictly increases the optimal broadcast rate. This paper, in TSUIC, analyzes all
cases of fully-participated and some cases of partially-participated interactions between D1 , D2
and D3 of D, and establishes their optimal broadcast rates as a function of the optimal broadcast
rates of D1 , D2 and D3 . This is done by utilizing existing SSUIC’s results and our proposed
coloring of confusion graphs for TSUIC, which we discuss in the subsequent sections. First, we
define some notations, which we use throughout this paper, in the following section.
IV. N OTATIONS
Unless stated otherwise, we use the following notations in the remainder of this paper:
1) Without loss of generality, we assume x1 , x2 , . . . , xn1 to be the messages requested by
vertices V (D1 ), xn1 +1 , xn1 +2 , . . . , xn1 +n2 the messages requested by vertices V (D2 ), and
xn1 +n2 +1 , xn1 +n2 +2 , . . . , xn1 +n2 +n3 the messages requested by vertices V (D3 ) with N =
n1 + n2 + n3 .
2) Indices i, i1 , i2 ∈ {1, 2, . . . , 2tn1 }, i1 6= i2 , j, j1 , j2 ∈ {1, 2, . . . , 2tn2 }, j1 6= j2 , and
k, k1 , k2 ∈ {1, 2, . . . , 2tn3 }, k1 6= k2 are used in the representation of possible realizations
of words of tn1 , tn2 and tn3 bits, respectively.
3) Consider that bits are associated with the messages requested by vertices of Di0 , i0 ∈ {1, 2, 3}.
Each realization of the bits, i.e., each member in {0, 1}tni0 is represented by a unique label
j0

j0

bDi0i0 , ji00 ∈ {1, 2, . . . , 2tni0 }. The Fig. 9a in Appendix A outlines each tuple bDi0i0 for t = 1.
Each message tuple (x1 , . . . , xN ) can then be uniquely written as (biD1 , bjD2 , bkD3 ) for some
i, j, k.
4) For the indices i, j, k, let Bbi

j
D1 ,bD2

cardinality 2tn3 , BbiD

2tn2 , and Bbj

k
D2 ,bD3

1

,bkD

3

, {(biD1 , bjD2 , bkD3 ) : for some fixed (biD1 , bjD2 )} with

, {(biD1 , bjD2 , bkD3 ) : for some fixed (biD1 , bkD3 )} with cardinality

is similarly defined.

5) For any vertex-induced sub-digraph Di0 , for some index i0 ∈ {1, 2, 3}, we assume the
following:

November 23, 2017

DRAFT

DRAFT

13

a) Let C(Di0 ) be an index code (linear or non-linear) having a codeword length of
p(C(Di0 )) bits (i.e., |C(Di0 )| = p(C(Di0 ))), for a given t (message bits), that achieves
βt (Di0 ) in SSUIC.
0

0

0

0

i
i
b) Let the sequence of bits in C(Di0 ) be (w1i , w2i , . . . , wp(C(D
), where wm
∈ {0, 1},
i0 ))

m ∈ {1, 2, . . . , p(C(Di0 ))}.
0

0

0

0

0

c) Let C 1 (Di0 ) = (w1i , w2i , . . . , wpi 1 (C(D 0 )) ) and C 2 (Di0 ) = (wpi 1 (C(D 0 ))+1 , wpi 1 (C(D 0 ))+2 , . . . ,
i

i0
wp(C(D
)
i0 ))

i

i

be two parts of the sequence of bits of a codeword of C(Di0 ) such that

C(Di0 ) = (C 1 (Di0 ), C 2 (Di0 )) with p(C(Di0 )) = p1 (C(Di0 )) + p2 (C(Di0 )).

d) For any two codes C(Di0 ) and C(Dj 0 ) with codeword lengths of p(C(Di0 )) and
p(C(Dj 0 )) bits, respectively, C(Di0 ) ⊕ C(Dj 0 ) refers to the bit-wise XOR of bits of
C(Di0 ) and C(Dj 0 ) with zero padding if p(C(Di0 )) 6= p(C(Dj 0 )). This means C(Di0 ) ⊕
C(Dj 0 ) contains max{p(C(Di0 )), p(C(Dj 0 ))} bits. For example, if C(Di0 ) = (101) and
C(Dj 0 ) = (001101), then C(Di0 ) ⊕ C(Dj 0 ) = (101000) ⊕ (001101) = (100101).
V. C ONFUSION GRAPHS AND COLORING : S INGLE - SENDER PRELIMINARIES AND TWO - SENDER
CONSTRUCTION

For an index-coding problem modeled by a side-information digraph D with N vertices, two
tuples of N messages, that are realized as uN = (u1 , u2 , . . . , uN ) and v N = (v1 , v2 , . . . , vN ),
are said to be confusable at a vertex (receiver) r ∈ {1, 2, . . . , N }, if ur 6= vr and ui0 = vi0 for
all i0 ∈ ND+ (r), where uj 0 , vj 0 ∈ {0, 1}t for all j 0 ∈ {1, 2, . . . , N }. We say that two tuples are

confusable if they are confusable at some receiver r. Clearly, in an index coding, we cannot
encode message tuples that are confusable to the same codeword; otherwise one of the receivers
cannot decode its requested message successfully. The confusability among all possible N -tuples
of messages (each message having t bits) for an index-coding problem is represented by a graph
called confusion graph, and it is defined as follows:
Definition 6 (Confusion graph): The confusion graph, denoted Γt (D) = (V (Γt (D), E(Γt (D)),
of a side-information digraph D with N vertices and t-bit messages is an undirected graph with
the following:
i) V (Γt (D)) = {uN : uN ∈ {0, 1}t×N }, and

ii) E(Γt (D)) = {(uN , v N ) : uN , v N ∈ {0, 1}t×N , and uN and v N are confusable}.
We will propose a notion of coloring for TSUIC. First, we recall the standard definition of
graph coloring in the following:

November 23, 2017

DRAFT

DRAFT

14

Definition 7 (Graph coloring and Chromatic number): A proper graph coloring of a graph G
is an onto function J : V (G) → J , where J is a set of colors, in such a way that if u and v
are adjacent vertices of G, then J(u) 6= J(v). The minimum number of colors over all possible

proper colorings of a graph G is called the chromatic number of G, and it is denoted by χ(G).
Consider coloring a confusion graph Γt (D) with a set of colors J . Now we get a family of
sets of independent vertices where all vertices belonging to one set are assigned with the same
color in the graph coloring. Here a set of independent vertices refers to a vertex set where any
pair of vertices are not connected by an edge in Γt (D), and we call such a set an independent
vertex set. The tuples representing vertices within an independent vertex set are not confusable,
and hence they can be coded into the same codeword. Assigning each independent vertex set
(whose vertices are all colored by a unique color) a unique codeword provides us a valid index
code having |J | codewords. Thus there exists a bijective mapping I : J → C, where C is an
index code (or a set of codewords that satisfies the demands made by all receivers). We know that
χ(Γt (D)) = min |J |. In SSUIC, it is shown that the optimal broadcast rate of an index-coding
J

problem D with t-bit messages can be obtained by using confusion graphs. This is stated in the
following theorem.
Theorem 1: (Alon et al. [23, Th. 1.1], Arbabjolfaei and Kim [8, Prop. 1]) The optimal broadcast
rate for a SSUIC problem with t-bit messages is
βt (D) =

dlog2 χ(Γt (D))e
.
t

(1)

The notion of confusion graphs has been considered in the index coding literature, and it has
been shown to be an effective tool for proving important results, for example, Bar-Yossef et
al. [3], Alon et al. [23], and Arbabjolfaei et al. [8] in their respective works, referred to the
confusion graph for the proof of results related to the odd hole and the odd anti-hole [3], the
gap between β and βt=1 of hypergraphs [23], and the structural properties of the index-coding
problems [8], respectively.
The confusion graph, which is only a function of the side-information graph, does not depend
on the number of senders. Its coloring function described above for SSUIC may not lead to an
index code for TSUIC due to the source constraint. In this work, we propose a way of coloring
the confusion graphs in TSUIC, we call this two-sender graph coloring. Now we present the
formal definition of two-sender graph coloring of confusion graphs for TSUIC.

November 23, 2017

DRAFT

DRAFT

15

Definition 8 (Two-sender graph coloring of Γt (D)): Let two onto functions J1 : {0, 1}tn1 ×

{0, 1}tn3 → J1 , and J2 : {0, 1}tn2 × {0, 1}tn3 → J2 be the coloring functions carried out by
senders S1 and S2 , respectively. A proper two-sender graph coloring of Γt (D) is an onto function
Jo : {0, 1}tn1 × {0, 1}tn2 × {0, 1}tn3 → J1 × J2 where Jo ((biD1 , bjD2 , bkD3 )) = (J1 (biD1 , bkD3 ),
0

0

0

J2 (bjD2 , bkD3 )) such that if (biD1 , bjD2 , bkD3 ) and (biD1 , bjD2 , bkD3 ) are adjacent vertices of Γt (D),
0

0

0

then Jo ((biD1 , bjD2 , bkD3 )) 6= Jo ((biD1 , bjD2 , bkD3 )).
Remark 2: The two-sender graph coloring is not a b-fold coloring that assigns a set of b colors
to each vertex such that the color sets corresponding to two adjacent vertices do not share any
color (refer to the definition of the fractional graph coloring [8]). In our definition, the color sets
can share colors, as long as the color vectors (i.e., ordered pairs) are different.
Now in the form of lemmas, we discuss two-sender graph coloring of Γt (D) in detail. Before
this, we first assume the following: For any indices i0 , j 0 , assume that ci0 and cj 0 are any two
distinct colors if i0 6= j 0 , and let (ci0 , cj 0 ) be an ordered pair of colors. Any two ordered pairs

of colors, (ci01 , cj10 ) and (ci02 , cj20 ) for indices i01 , j10 , i02 , j20 , are said to be different (or not equal) if
and only if i01 6= i02 or j10 6= j20 or both. If a color ci0 is associated to a sender Ss , s ∈ {1, 2}, then

we denote it by csi0 .

In TSUIC, the two senders encode separately, so in the aforementioned definition, we need to
assign an ordered pair of colors for each vertex, where the first color is associated with S1 and
the second color with S2 . Now we have the following lemmas.
Lemma 1: For any two vertices, uN,v N ∈ V (Γt (D)) such that they are labeled by (biD1 1,bjD2,bkD3)

and (biD2 1,bjD2,bkD3), respectively, if (uN , v N ) ∈ E(Γt (D)), then we must have Jo (uN ) = (c1i0 , c2j 0 )
1

N

and Jo (v ) =

(c1i0 , c2j 0 )
2
2

such that

c1i0
1

6=

c1i0
2

and

c2j 0
1

=

c2j 0
2

for some indices

1

i01 , i02 , j10 , j20 .

Proof: It is given that (uN , v N ) ∈ E(Γt (D)), so uN and v N are confusable. Moreover, these

two tuples are confusable only at some vertex in V (D1 ). This is because the labels (biD1 1 , bjD2 , bkD3 )
and (biD2 1 , bjD2 , bkD3 ) of uN and v N , respectively, are different only in biD1 sub-label (which is
representing tn1 -bit tuples of the messages requested by vertices in V (D1 )). Now for the sender
S2 , which does not contain any message in P1 (messages requested by receivers in V (D1 )),
the coloring function J2 (bjD2 , bkD3 ) provides the same color to both vertices. Thus c2j 0 = c2j 0 . On
1

2

the other hand, for the sender S1 , which contains all messages in P1 , it is necessary to have
J1 (biD1 1 , bkD3 ) 6= J1 (biD2 1 , bkD3 ) because these two tuples (biD1 1 , bkD3 ) and (biD2 1 , bkD3 ) are confusable

given that (biD1 1 , bjD2 , bkD3 ) and (biD2 1 , bjD2 , bkD3 ) are confusable at some receiver in V (D1 ). Thus
c1i0 6= c1i0 .
1

2

November 23, 2017

DRAFT

DRAFT

16

In a similar reasoning as in the above proof (of Lemma 1), one can prove the following lemmas:
Lemma 2: For any two vertices, uN,v N ∈ V (Γt (D)) such that they are labeled by (biD1,bjD12,bkD3)

and (biD1,bjD22,bkD3), respectively, if (uN , v N ) ∈ E(Γt (D)), then we must have Jo (uN ) = (c1i0 , c2j 0 )
1

1

and Jo (v N ) = (c1i0 , c2j 0 ) such that c1i0 = c1i0 and c2j 0 6= c2j 0 for some indices i01 , i02 , j10 , j20 .
2

2

1

2

1

2

If uN and v N are confusable at some vertices in V (D1 ) and in V (D2 ), then referring to Lemma 1
and 2, we get the following:
Lemma 3: For any two vertices, uN,v N ∈ V (Γt (D)) such that they are labeled by (biD1 1,bjD12,bkD3)

and (biD2 1,bjD22,bkD3), respectively, if (uN , v N ) ∈ E(Γt (D)) due to confusion at some vertices in
V (D1 ) and in V (D2 ), then we must have Jo (uN ) = (c1i0 , c2j 0 ) and Jo (v N ) = (c1i0 , c2j 0 ) such that
1

1

2

2

c1i0 6= c1i0 and c2j 0 6= c2j 0 for some indices i01 , i02 , j10 , j20 .
1

2

N

1

If u and v

N

2

are confusable at some vertices in V (D3 ), then while coloring Γt (D) in two-sender

graph coloring, it suffices to have a different color associated with any one of the senders because
all the messages in P3 are contained by both senders S1 and S2 . Thus we have the following
lemma:
Lemma 4: For any two vertices, uN,v N ∈ V (Γt (D)) such that they are labeled by (biD1,bjD2,bkD13)

and (biD1,bjD2,bkD23), respectively, if (uN , v N ) ∈ E(Γt (D)), then we have Jo (uN ) = (c1i0 , c2j 0 ) and
1

N

Jo (v ) =

(c1i0 , c2j 0 )
2
2

such that either

c1i0
1

6=

c1i0 ,
2

or

c2j 0
1

6=

c2j 0 ,
2

1

or both.

Now for a TSUIC problem with t-bit messages, we have the following theorem:
Theorem 2: The optimal broadcast rate for a TSUIC problem with t-bit messages is
βt (D, Go ) = min
J1 ,J2

dlog2 |J1 |e + dlog2 |J2 |e
.
t

(2)

Proof: For s ∈ {1, 2}, consider Js , a coloring function of the sender Ss , with a set of colors

Js such that the ordered pairs of colors in {(c1i0 , c2j 0 ) : c1i0 ∈ J1 , and c2j 0 ∈ J2 }, i0 ∈ {1, 2, . . . , |J1 |}

and j 0 ∈ {1, 2, . . . , |J2 |}, properly color the vertices of Γt (D) in two-sender graph coloring. A
two-sender index code is obtained by S1 mapping distinct colors in J1 to distinct sub-codewords,
and S2 mapping distinct colors in J2 to distinct sub-codewords. By definition, all confusable
vertex pairs are assigned a different codewords. Now for s ∈ {1, 2}, the sender Ss transmits |Js |
sub-codewords. Equivalently, dlog2 |Js |e bits are transmitted by Ss . This is because the number of
bits required to index |Js | colors are dlog2 |Js |e. Minimizing the sum (dlog2 |J1 |e + dlog2 |J2 |e)
over all coloring functions J1 (of S1 ) and J2 (of S2 ) per received message bits (i.e., t), we get
βt (D, Go ) ≤ min
J1 ,J2

November 23, 2017

dlog2 |J1 |e + dlog2 |J2 |e
.
t

(3)

DRAFT

DRAFT

17

p1 +p2
,
t
E,{Gr }

By definition of βt (D, Go ), we have βt (D, Go ) = min

so there exists a two-sender index

code such that S1 and S2 transmit p01 -bit and p02 -bit sub-codewords, respectively, resulting in
βt (D, Go ) =

p01 + p02
.
t

(4)
0

Now for each sender Ss , we know that there are at most 2ps possible sub-codewords. Assume a
0

bijective function that maps each sub-codeword to a color. This function provides us 2ps or fewer
0

distinct colors associated with each sender Ss . Moreover, Ss properly colors Γt (D) with 2ps or
fewer distinct colors in the two-sender graph coloring; otherwise, the two-sender index code,
which is formed by p01 -bit and p02 -bit sub-codewords of S1 and S2 , respectively, will be an invalid
code (contradicts our assumption). Altogether, there exists a valid two-sender graph coloring
0

0

such that |J10 | ≤ 2p1 and |J20 | ≤ 2p2 , or equivalently, p01 ≥ dlog2 |J10 |e and p02 ≥ dlog2 |J20 |e as
both are non-negative integers. Substituting the inequalities of p01 and p02 in (4), wet get
dlog2 |J10 |e + dlog2 |J10 |e
βt (D, Go ) ≥
.
t

(5)

Now we prove equality in (3). This is done by contradiction. Suppose that
βt (D, Go ) < min
J1 ,J2

dlog2 |J1 |e + dlog2 |J2 |e
.
t

(6)

From (5) and (6), we get
dlog2 |J10 |e + dlog2 |J10 |e
dlog2 |J1 |e + dlog2 |J2 |e
< min
,
J1 ,J2
t
t
and this leads to a contradiction. Thus βt (D, Go ) = min
J1 ,J2

(7)

dlog2 |J1 |e+dlog2 |J2 |e
.
t

We illustrate two-sender graph coloring of a confusion graph in TSUIC, and a mapping function
that maps colors to codewords at each sender from the following example.
Example 1: Consider a TSUIC problem (D, Go ) of the following: (1|2), (2|1), (3|1), and
M1 = {1, 3}, M2 = {2, 3} with t = 1. The problem is depicted in Fig. 4a. We have V (D1 ) = {1},
V (D2 ) = {2}, V (D3 ) = {3}, and N = 3. The confusion graph Γ1 (D) has 2N = 8 vertices

labeled by all possible realizations of a word with three bits. In Γ1 (D), any two vertices are
connected by an edge if the message tuples labeling the vertices are confused at some receiver.
For example, (0, 0, 0) and (1, 0, 0) are connected by an edge because these two message tuples
are confused at receiver 1. The confusion graph Γ1 (D) is depicted in Fig. 4b. Now we perform
two-sender graph coloring of the vertices of Γ1 (D). In two-sender graph coloring, each vertex
of Γ1 (D) is assigned with an ordered pair of colors; the first color is always associated with
S1 and the second color is always associated with S2 , and we color the vertices as dictated
November 23, 2017

DRAFT

DRAFT

18

(1,0,0)
(0,0,0)

(1,0,1)

Go
3

S2

3

D3

0
1

(0,0,1)

Γ1 (D)

D

S1

0
1

(1,1,0)
(0,1,0)

D1

1

2

D2

1

2

(a)
Fig. 4.

(0,1,1)

(1,1,1)

(b)

(a) A TSUIC problem (D, Go ), and (b) the confusion graph Γ1 (D), and its two-sender graph coloring.

by Lemma 1 to Lemma 4. For example, consider (0, 0, 0) and (1, 0, 0). These two tuples are
confused at receiver 1 (requesting x1 ). As S2 , which does not know x1 , the tuples (0, 0, 0) and
(1, 0, 0), which have the same second and third message bits, are treated as the same. Thus S2
must assign the same color, say RED, to both the tuples. As S1 knows x1 and the tuples are
confusable at receiver 1, it must assign two different colors, say RED and BLUE, to (0, 0, 0) and
(1, 0, 0), respectively. In a similar way, we assign ordered pairs of colors to all vertices of Γ1 (D)
as shown in Fig. 4b. Altogether, one can get J1 = {RED, BLUE} and J2 = {RED, BLUE}. Now
we assume a mapping function that maps RED to 0 and BLUE to 1. So, we get (0, 0, 0) → 00,
(1, 0, 0) → 10, (0, 1, 0) → 01 and so on for the remaining tuples (vertices of Γt (D)). Thus
{00, 10, 01, 11} is a valid two-sender index code for (D, Go ), where each sender transmits a 1-bit
sub-codeword for a message tuple, and the sum of bits to be transmitted by the two senders is
two for each message tuple. Consequently, βt (D, Go ) ≤ 2. Each sender has one private message,
and that must be transmitted by that sender, so there must be at least one transmission by that
sender. Thus βt (D, Go ) ≥ 2. Altogether, we get βt (D, Go ) = 2.
In this section, we have introduced confusion graphs. As this method has been utilized for
only SSUIC, we propose an approach to use the confusion graph in TSUIC to study structural
characteristics of TSUIC problems. As a confusion graph possesses some symmetry within — in
fact, all confusion graphs are vertex-transitive4 — while analyzing them (especially coloring),
we systematically group its vertices and then analyze the graph based on these groups (rather
than individual vertices). This way, for a TSUIC problem whose sub-problems interact with each
other in some way, we can reduce the complexity arising during its analysis (especially finding
4

A graph is vertex-transitive if every vertex can be mapped to any other vertex by some automorphism (or symmetry).

November 23, 2017

DRAFT

DRAFT

19

the number of colors in a proper coloring of Γt (D)) due to the number of vertices, which is
exponential in t and N . In the following section, we introduce our proposed method of grouping
the vertices of Γt (D).
VI. G ROUPING THE VERTICES OF Γt (D): S TATING ITS CHARACTERISTICS
A vertex of the confusion graph Γt (D) is represented by a tuple xN that is labeled by a unique
(biD1 , bjD2 , bkD3 ) (see Fig. 5). For the ease of analysis, we collect all the vertices with the same bkD3
sub-label into one group, and the subgraph of Γt (D) induced by that group of vertices is called
the k-th block (refer to Fig. 5 for the functional block diagram). Moreover, this grouping provides
2tn3 blocks in Γt (D). Clearly, all blocks in Γt (D) are isomorphic graphs. This is because each
block consists of all (biD1 , bjD2 , bkD3 ) for the same bkD3 sub-label (the bkD3 sub-labels are different
only for different blocks), and the edges in any block is due to the confusion at some receivers
in V (D1 ∪ D2 ). Moreover, the (tn1 + tn2 )-bit tuples of messages requested by the vertices in
V (D1 ∪ D2 ) are labeled by (biD1 , bjD2 ). Now we further group the vertices of a block with the
same bkD3 sub-label in two ways:

(i) Grouping all vertices with the same bjD2 sub-label into one sub-group, and the sub-graph
of Γt (D) induced by that group of vertices is called the j-th sub-block. This sub-grouping of
vertices provides 2tn2 sub-blocks within each block, and its vertex set is represented by Bbj

k
D2 ,bD3

.

Clearly, all sub-blocks of a Γt (D) are isomorphic graphs. This is because each sub-block consists
of all (biD1 , bjD2 , bkD3 ) for the same (bjD2 , bkD3 ) sub-labels (the (bjD2 , bkD3 ) sub-labels are different
only for different sub-blocks), and the edges in any sub-block is due to the confusion at some
receivers in V (D1 ). Moreover, the tn1 -bit tuples of messages requested by the vertices in V (D1 )
are labeled by biD1 .
(ii) Grouping all vertices with the same biD1 sub-label into one sub-group, and this sub-grouping of
vertices provides 2tn1 sub-groups of this kind within each block, and its vertex set is represented
by BbiD

1

,bkD

. From a similar reasoning as presented above for the case of the sub-block, it is

3

not difficult to see that all the vertex-induced graphs of Γt (D), each induced by the vertices in
BbiD

1

,bkD

3

, for all i and k, are isomorphic graphs.

Now we illustrate the aforesaid notations and grouping of the vertices by an example.
Example 2: Consider the TSUIC problem stated in Example 1. The confusion graph of the
problem, Γ1 (D), has the following: b1D1 = 0, b2D1 = 1, b1D2 = 0, b2D2 = 1, b1D3 = 0, b2D3 = 1,
Bb1D

2

,b1D

3

= {(0, 0, 0), (1, 0, 0)}, Bb2D

November 23, 2017

2

,b1D

3

= {(0, 1, 0), (1, 1, 0)}, Bb1D

2

,b2D

3

= {(0, 0, 1), (1, 0, 1)},
DRAFT

DRAFT

20

b1D3

tn1

b2D2

b1D3

tn1

b2D2

b1D3

tn1

b1D2

b2D3

tn1

b2D2

b2D3

tn1

b2D2

b2D3

tn1

b1D2

b2D3

tn1

b2D2

b2D3

tn1

b2D2

b1D3

b2D1

b1D2

b1D3

b2D1

b1D1

b2D2

b1D3

b2D1

b2D2

b1D3

b2D1

tn2

b1D3

b2D1

b2D2

b1D3

b2D1

b1D1

b1D2

b2D3

b2D1

b1D2

b2D3

b2D1

b1D1

b2D2

b2D3

b2D1

b2D2

b2D3

b2D1

tn2

b2D3

b2D1

b2D2

b2D3

b2D1

b1D1

b1D2

b2D3

tn3

b2D1

b1D2

b2D3

b1D1

b2D2

b2D3

tn3

b2D1

b2D2

b2D3

tn3

b2D1

b2D2

b1D1

b1D1

b2D2

b2D2

tn2

b2D2

b2D3

tn2

tn2

tn2

tn3

b2D1

tn3

b2D1

tn3

b2D1

b2D3

tn2

tn2

tn3

tn3

tn2

Vertices of SUB-BLOCK 2

b1D2

b1D2

b1D1

Vertices of Γ(D)

tn1

b1D1

Vertices of BLOCK 1

One vertex of Γ(D) = one realization of the message tuple xN ∈ {0, 1}tN

tn3

b2D3

Fig. 5. Functional block digraph of grouping the vertices of a confusion graph. The vertices of a confusion graph are all the
possible realizations of words of tN bits.

Bb2D

,b2D

= {(0, 1, 1), (1, 1, 1)}, Bb1D

,b1D

= {(0, 0, 0), (0, 1, 0)}, Bb2D

,b1D

= {(1, 0, 0), (1, 1, 0)},

Bb1D

,b2D

= {(0, 0, 1), (0, 1, 1)}, Bb2D

,b2D

= {(1, 0, 1), (1, 1, 1)}, Bb1D

,b1D

= {(0, 0, 0), (0, 0, 1)},

Bb2D

,b1D

= {(1, 0, 0), (1, 0, 1)}, Bb1D

2
1
1

3
3
2

1
1

1

3
3

,b2D

1
1

3

= {(0, 1, 0), (0, 1, 1)}, and Bb2D

2

2

1

,b2D

2

= {(1, 1, 0), (1, 1, 1)}.

Furthermore, the sub-graph of Γ1 (D) induced by the vertices in the sets {(0, 0, 0), (1, 0, 0), (0, 1, 0),
(1, 1, 0)} and {(0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1)} form k = 1 and k = 2 blocks, respectively
(see Fig. 4b). In addition, we have four different sub-blocks, each formed by the vertices in one
of the following sets: Bb1D

2

,b1D

3

, Bb2D

2

,b1D

3

, Bb1D

2

,b2D

3

, and Bb2D

2

,b2D

3

(for a general outline refer to

Fig. 9b in Appendix A).
For a confusion graph Γt (D), we have the following propositions after grouping its vertices
according to our proposed method. These are helpful for understanding the construction of a
confusion graph, and are useful for the proofs of our results in the subsequent sections.

November 23, 2017

DRAFT

DRAFT

21

Proposition 1: Γt (D1 ) and the sub-graph of Γt (D) induced by the vertices in Bbj

(bjD2 , bkD3 )

k
D2 ,bD3

for any

are isomorphic graphs.

Proof: For any (bjD2 , bkD3 ), let the subgraph of Γt (D) induced by the vertices in Bbj

k
D2 ,bD3

be G. We know that any vertex in the set Bbj

k
D2 ,bD3

has the same (bjD2 , bkD3 ) sub-labels, and all

vertices of Γt (D) with the same (bjD2 , bkD3 ) sub-label are included in the set. Thus in G, any
edge between its vertices is only due to the confusion at some receiver belonging to V (D1 )
(corresponding to the change in bits of biD1 sub-label of the vertices). We know that Γt (D1 )
has vertices V (Γt (D1 )) = {(biD1 )}, and any edge between its vertices is due to the confusion
at some receiver belonging to V (D1 ). Observe that |V (Γt (D1 ))| = 2tn1 = |Bbj

k
D2 ,bD3

| = |V (G)|.

Now (biD1 1 , biD2 1 ) ∈ E(Γt (D1 )) if ((biD1 1 , bjD2 , bkD3 ), (biD2 1 , bjD2 , bkD3 )) ∈ E(G) and vice-versa. This

is because the edges are due to the confusion of the tuples, representing those vertices, at some
receiver belonging to V (D1 ). Consequently, Γt (D1 ) and G are isomorphic graphs.
Now we illustrate Proposition 1 by an example. Consider the TSUIC problem stated in
Example 1. The confusion graph of D1 , Γ1 (D1 ), has two vertices 0 and 1 connected by an
edge as they are confused at receiver 1. Now the sub-graph of Γ1 (D) induced by the vertices in
Bbj

k
D2 ,bD3

, for any (bjD2 , bkD3 ), has two vertices (0, bjD2 , bkD3 ) and (1, bjD2 , bkD3 ) connected by an

edge as they are confused at receiver 1, and clearly, this vertex-induced sub-graph is isomorphic
to Γ1 (D1 ).
Note that Bbj

k
D2 ,bD3

is the vertex set of the j-th sub-block of the k-th block of Γt (D). In a

similar way to the proof of Proposition 1, one can prove the following proposition.
Proposition 2: The following are isomorphic graphs: (i) Γt (D2 ) and the sub-graph of Γt (D)
,bkD

for any (biD1 , bkD3 ), (ii) Γt (D3 ) and the sub-graph of Γt (D)

j
D1 ,bD2

for any (biD1 , bjD2 ), and (iii) Γt (D1 ∪ D2 ) and any k-th block

induced by the vertices in BbiD

1

induced by the vertices in Bbi

3

of a Γt (D).
Proposition 3: In two-sender graph coloring of the sub-graph of Γt (D) induced by the vertices
in Bbj

k
D2 ,bD3

for any (bjD2 , bkD3 ), χ(Γt (D1 )) is the minimum number of total ordered pairs of colors

required to color the vertex-induced sub-graph, and the minimum number of colors associated
with S1 and S2 are χ(Γt (D1 )) and one, respectively.
Proof: For any (bjD2 , bkD3 ), let the subgraph of Γt (D) induced by the vertices in Bbj

k
D2 ,bD3

be G. Observe that G includes all vertices of Γt (D) with the same (bjD2 , bkD3 ) sub-labels (due
to our proposed method of grouping the vertices of Γt (D)). So, the edges between the vertices
of G are only due to the confusion at some receivers belonging to V (D1 ). From Lemma 1,
November 23, 2017

DRAFT

DRAFT

22

any pair of vertices of G connected by an edge must have different colors associated with S1
and the same color associated with S2 . Thus the minimum number of colors associated with
S2 is one. From Proposition 1, G is isomorphic to Γt (D1 ), so it has the minimum of χ(Γt (D1 ))
independent vertex sets. Thus we need at least χ(Γt (D1 )) different ordered pairs of colors to
color G. Moreover, in two-sender graph coloring, a proper two-sender graph coloring is to let
S1 color the vertices in the same way as we color Γt (D1 ). As the colors associated with S2 is
one, the minimum number of colors associated with S1 must be χ(Γt (D1 )) in order to have the
minimum of χ(Γt (D1 )) ordered pairs of colors in two-sender graph coloring.
In a similar way to the proof of Proposition 3, one can prove the following proposition.
Proposition 4: In two-sender graph coloring of the sub-graph of Γt (D) induced by the vertices
in BbiD

1

,bkD

3

for any (biD1 , bkD3 ), χ(Γt (D2 )) is the minimum number of total ordered pairs of colors

required to color the vertex-induced sub-graph, and the minimum number of colors associated
with S1 and S2 are one and χ(Γt (D2 )), respectively.
Proposition 5: In two-sender graph coloring of the sub-graph of Γt (D) induced by the vertices
in Bbi

j
D1 ,bD2

for any (biD1 , bjD2 ), the minimum number of total ordered pairs of colors required to

color the vertex-induced sub-graph is χ(Γt (D3 )).
Proof: We know that Γt (D3 ) requires the minimum of χ(Γt (D3 )) different colors in its
coloring in SSUIC. Thus it has the minimum of χ(Γt (D3 )) independent vertex sets. From
Proposition 2, the sub-graph of Γt (D) induced by the vertices in Bbi

j
D1 ,bD2

is isomorphic to

Γt (D3 ), so it has the minimum of χ(Γt (D3 )) independent vertex sets. In two-sender graph
coloring, we assign each independent vertex set a unique ordered pair of colors. Thus the
vertex-induced sub-graph requires the minimum of χ(Γt (D1 )) ordered pairs of colors.
For convenience, we define the following types of edges of Γt (D):
Definition 9 (Inter-block edge and Intra-block edge): An edge between two vertices each
belonging to a different block of Γt (D) (e.g., an edge between a vertex of the k1 -th block and a
vertex of the k2 -th block of Γt (D)) is called an inter-block edge, and an edge within the vertices
of a block of Γt (D) (e.g., an edge between any two vertices of the k-th block of Γt (D)) is called
an intra-block edge.
VII. L OWER B OUNDS
For any D, we have β(D) ≤ βt (D) for all t (by definition). Since any index code for (D, Go )
is also an index code for D, but the converse is not always true, so we have the following:

November 23, 2017

DRAFT

DRAFT

23

Lemma 5 (A simple lower bound): For any D and Go , β(D, Go ) ≥ β(D).

In TSUIC, each sender Ss transmits at least β(Ds ), for s ∈ {1, 2}. We now provide a lower

bound of the optimal broadcast rate for a TSUIC problem with t-bit messages in the following
lemma.
Lemma 6 (A lower bound): For any two-sender index-coding problem (D, Go ), βt (D, Go ) ≥
βt (D1 ) + βt (D2 ), and β(D, Go ) ≥ β(D1 ) + β(D2 ).

Proof: For any two-sender index-coding problem (D, Go ), let (D0 , G0o ) be its sub-problem

induced by vertices V (D1 ∪ D2 ). Observe that (D0 , G0o ) has V (D3 ) = ∅. Now we have
βt (D0 , G0o ) = βt (D1 ) + βt (D2 ) ([16, Th. 1]). For any index-coding problem, its broadcast
rate is always lower bounded by the broadcast rate of any sub-problem, so we get
βt (D, Go ) ≥ βt (D0 , G0o ) = βt (D1 ) + βt (D2 ).

(8)

We know that lim βt (D1 ) = β(D1 ), lim βt (D2 ) = β(D2 ) and β(D, Go ) = lim βt (D, Go ) (by
t→∞

t→∞

t→∞

Definition 3). Now taking a limit t → ∞ on both sides in (8), we get
β(D, Go ) ≥ β(D1 ) + β(D2 ).

(9)

To compute the simple lower bound to the optimal broadcast rate of a given problem in TSUIC,
we utilize the following results by Arbabjolfaei and Kim [8, Prop. 3, Th. 2, Th. 3], and these are
stated in the following theorem.
Theorem 3: In SSUIC, for a side-information digraph D having two sub-digraphs Da and
Db induced by vertices V (Da ) and V (Db ), respectively, such that V (D) = V (Da ) ∪ V (Db ) and
V (Da ) ∩ V (Db ) = ∅, we have
1) β(D) = β(Da )+β(Db ) if there is (i) no interaction between Da and Db (i.e., no Da → Db
and Db → Da ), or (ii) a one way interaction (either partially or fully participated) between
Da and Db , i.e., either only Da → Db or Db → Da , and
2) β(D) = max{β(Da ), β(Db )} if there is a fully participated both way interaction between
Da and Db (i.e., fully participated Da  Db ).
In the rest of this paper, for any D having fully-participated interactions between its sub-digraphs
D1 , D2 and D3 , we express β(D, Go ) and βt (D, Go ) as a function of the optimal broadcast
rates of D1 , D2 and D3 . The results are summarized in Table I. Furthermore, similar results
are presented for D whose f (D) is of CASE I and Case II-A, and it has partially-participated
interactions between the sub-digraphs.

November 23, 2017

DRAFT

DRAFT

24

TABLE I
S UMMARY OF OUR RESULTS FOR ANY D

CASE I

f (D)
H1 − H12

WITH FULLY- PARTICIPATED INTERACTIONS BETWEEN

β(D, Go )

CASE II-B CASE II-A
CASE II-C

H34 − H40
H43 − H45

H41 , H42

D3

IN

TSUIC.

βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,  ∈ {−2, −1, 0}
(Theorem 5)

β(D1 ) + β(D2 ) + β(D3 ) = β(D)
(Theorem 4)

H30 − H33

AND

βt (D, Go )

βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,  ∈ {−2, −1, 0}

H13 − H25

H26 − H29

D1 , D2

(Conjecture 1)

β(D1 )+β(D2 )+β(D3 )

βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,  ∈ {−2, −1, 0}

(Theorem 6)

(Theorem 6)

max{β(D3 ), β(D1 ) + β(D2 )}

max{βt (D3 ), βt (D1 ) + βt (D2 )}

(Theorem 7)

(Theorem 7)

β(D2 ) + max{β(D1 ), β(D3 )}
(Proposition 8)
≤ β(D2 ) + max{β(D1 ), β(D3 )}

≤ βt (D2 ) + max{βt (D1 ), βt (D3 )}
= βt (D1 ) + βt (D2 ), if βt (D1 ) ≥ βt (D3 )

= β(D1 ) + β(D2 ), if β(D1 ) ≥ β(D3 )

(Theorem 8)

CASE II-E

CASE II-D

(Theorem 8)

H46 − H57

H58 − H64

≤ β(D1 ) + max{β(D2 ), β(D3 )}

= β(D1 ) + β(D2 ), if β(D2 ) ≥ β(D3 )
(Corollary 2)

≤ βt (D1 ) + max{βt (D2 ), βt (D3 )}

= βt (D1 ) + βt (D2 ), if βt (D2 ) ≥ βt (D3 )
(Corollary 2)

≤ max{β(D1 ), β(D3 )} + max{β(D2 ), β(D3 )}

≤ max{βt (D1 ), βt (D3 )} + max{βt (D2 ), βt (D3 )}

= β(D1 ) + β(D2 ), if β(D3 ) ≤ min{β(D1 ), β(D2 )} = βt (D1 ) + βt (D2 ), if βt (D3 ) ≤ min{βt (D1 ), βt (D2 )}
(Theorem 9)

(Theorem 9)

VIII. M AIN R ESULTS
A. Optimal broadcast rate of a digraph D whose f (D) belongs to CASE I and CASE II-A: The
arcs between D1 , D2 and D3 are not critical in the asymptotic regime in the message size.
Theorem 4 (CASE I): For any D having any interaction (i.e., either fully participated or
partially participated) between its sub-digraphs D1 , D2 and D3 , if f (D) ∈ {H1 , H2 , . . . , H25 }
(i.e., a digraph H of CASE I in Fig. 3), then β(D, Go ) = β(D1 ) + β(D2 ) + β(D3 ) = β(D).
Proof: Referring to the definition of the mapping function f (in Section III), we know that
for any D if f (D) ∈ {H1 , H2 , . . . , H25 }, then the interaction between D1 , D2 and D3 of D are
November 23, 2017

DRAFT

DRAFT

25

D

1

Go

D3

5

2

D1

1

5

2

D2

4

3

4

3

Fig. 6. A given side-information digraph D such that f (D) = H12 , and a source-constraint graph Go (for M1 = {1, 4, 5}
and M2 = {1, 2, 3}). Moreover, we have V (D1 ) = {4, 5}, V (D2 ) = {2, 3} and V (D3 ) = {1}. From Theorem 4, we get
β(D, Go ) = β(D) = β(D1 ) + β(D2 ) + β(D3 ) = 1 + 2 + 1 = 4. It is not difficult to observe that a two-sender index code
{x4 ⊕ x5 , x1 , x2 , x3 }, that is obtained by transmitting x4 ⊕ x5 from S1 , and x1 , x2 , x3 from S2 , achieves the optimal broadcast
rate both in TSUIC and SSUIC.

acyclic. Thus one can arrange D1 , D2 and D3 in a sequence such that there is no arc between
D1 , D2 and D3 in a backward direction. Without loss of generality, let the sequence be D1 , D2
and D3 . Now for D, referring to Theorem 3, we get
β(D) = β(D1 ∪ D2 ) + β(D3 ) = β(D1 ) + β(D2 ) + β(D3 ).

(10)

From Lemma 5, we have
β(D, Go ) ≥ β(D).

(11)

β(D, Go ) ≥ β(D1 ) + β(D2 ) + β(D3 ).

(12)

Now from (10) and (11), we get

In TSUIC, if we consider the sub-digraphs D1 , D2 and D3 separately, then their respective
source constraint graphs are the sub-graphs of G0 induced by vertices V (D1 ), V (D2 ) and V (D3 ),
denoted G10 , G20 and G30 , respectively. These sub-graphs are edgeless graphs, and thus one can get
β(D1 , G10 ) = β(D1 ), β(D2 , G20 ) = β(D2 ) and β(D3 , G30 ) = β(D3 ). We know that the optimal
broadcast rate of a side-information digraph is always less than or equal to the sum of the optimal
broadcast rates of its sub-digraphs, so
β(D, Go ) ≤ β(D1 , G10 ) + β(D2 , G20 ) + β(D3 , G30 )
≤ β(D1 ) + β(D2 ) + β(D3 ).

(13)

From (10), (12) and (13), we get β(D, Go ) = β(D1 ) + β(D2 ) + β(D3 ) = β(D).
Example 3: Consider a TSUIC problem of the following: (1), (2|1, 4, 5), (3|1, 2, 4, 5), (4|1, 5),
(5|1, 4), and M1 = {1, 4, 5}, M2 = {1, 2, 3}. We compute its β(D, Go ) using Theorem 4. Refer
to Fig. 6 for details.

November 23, 2017

DRAFT

DRAFT

26

Proposition 6: For any D having any interaction (i.e., either fully participated or partially
participated) between its sub-digraph D1 , D2 and D3 , if f (D) ∈ {H1 , H27 }, then βt (D, Go ) =
βt (D1 ) + βt (D2 ) + βt (D3 ) + /t for some  ∈ {−2, −1, 0}.
Proof: Refer to Appendix B.
Theorem 5 (CASE I): For any D having any interaction (i.e., either fully participated or
partially participated) between its sub-digraphs D1 , D2 and D3 , if f (D) ∈ {H1 , H2 , . . . , H12 },
then βt (D, Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t for some  ∈ {−2, −1, 0}.
0

Proof: Let D be denoted by Di if f (D) = Hi0 , i0 ∈ {1, 27}. From Proposition 6, we have
βt (D1 , Go ) = βt (D27 , Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,

(14)

for some  ∈ {−2, −1, 0}. Observe that the interaction between D1 , D2 and D3 of D such that

f (D) ∈ {H2 , H3 . . . , H12 } has fewer interactions (between D1 , D2 and D3 ) than that of D27 , so
βt (D, Go ) ≥ βt (D27 , Go ),

(15)

and more interactions than that of D1 , so
βt (D, Go ) ≤ βt (D1 , Go ).

(16)

Now from (14), (15) and (16), we get βt (D, Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t for some
 ∈ {−2, −1, 0}.

For the digraphs if f (D) ∈ {H13 , H14 , . . . , H25 }, then considering Theorem 4 and 5, we

conjecture the following:
Conjecture 1 (CASE I): For any D having any interaction (i.e., either fully participated or
partially participated) between its sub-digraphs D1 , D2 and D3 , if f (D) ∈ {H13 , H14 , . . . , H25 },
then βt (D, Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t for some  ∈ {−2, −1, 0}.
For any D whose f (D) belongs to a digraph of CASE II in Fig. 3, referring to the definition
of the mapping function f , we observe that the interaction between D1 , D2 and D3 of D are
not acyclic. The CASE II is further divided into five sub-cases. Case II-A depicts a sub-case
when there is no 3 → 1 and 3 → 2 in H, and for the digraph whose f (D) is of this sub-case,
we have the following theorem.
Theorem 6 (CASE II-A): For any D having any interaction (i.e., either fully participated or
partially participated) between its sub-digraphs D1 , D2 and D3 , if f (D) ∈ {H26 , H27 , H28 , H29 },
then βt (D, Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t, where  ∈ {−2, −1, 0}, and β(D, Go ) =
β(D1 ) + β(D2 ) + β(D3 ).
November 23, 2017

DRAFT

DRAFT

27

0

Proof: Let D be denoted by Di if f (D) = Hi0 , i0 ∈ {1, 27} . From Proposition 6, we have
βt (D1 , Go ) = βt (D27 , Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,

(17)

for some  ∈ {−2, −1, 0}. Observe that the interaction between D1 , D2 and D3 of D such that
f (D) ∈ {H26 , H28 , H29 } has fewer interactions (between D1 , D2 and D3 ) than that of D27 , so
βt (D, Go ) ≥ βt (D27 , Go ),

(18)

and more interactions than that of D1 , so
βt (D, Go ) ≤ βt (D1 , Go ).

(19)

Now from (17), (18) and (19), we get
βt (D, Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,

(20)

where  ∈ {−2, −1, 0}. Now taking a limit t → ∞ on both sides in (20), we get
lim βt (D, Go ) = lim (βt (D1 ) + βt (D2 ) + βt (D3 ) + /t)

t→∞

t→∞

β(D, Go ) = β(D1 ) + β(D2 ) + β(D3 ),

(21)

where lim t = 0.
t→∞

Remark 3: For any D having non-empty D1 , D2 and D3 such that f (D) ∈ {H26 , H27 , H28 , H29 },
in SSUIC, we have β(D) = β(D3 ) + max{β(D1 ), β(D2 )} by Theorem 3, however in TSUIC,
β(D), a lower bound to β(D, Go ), is not achievable due to Theorem 6.
Corollary 1: For any D having any interaction (i.e., either fully participated or partially
participated) between its sub-digraphs D1 , D2 and D3 , if f (D) ∈ {H1 , H2 , . . . , H29 }, then the
arcs (contributing to that interaction) between D1 , D2 and D3 of D are not critical in TSUIC in
the asymptotic regime in message size (considering infinitely long messages).
Proof: The proof follows from Theorem 4 and Theorem 6.
B. Optimal broadcast rates of a digraph D having a fully participated interaction between its
sub-digraphs D1 , D2 and D3 such that f (D) belongs to CASE II-B: βt (D, Go ) = βt (D) for D
whose f (D) ∈ {H30 , H32 , H33 }.
Theorem 7 (CASE II-B): For any D having a fully participated interaction between its subdigraphs D1 , D2 and D3 , and t-bit messages for any t ≥ 1, if f (D) ∈ {H30 , H31 , H32 , H33 }, then
βt (D, Go ) = max{βt (D3 ), βt (D1 ) + βt (D2 )} and β(D, Go ) = max{β(D3 ), β(D1 ) + β(D2 )}.
November 23, 2017

DRAFT

DRAFT

28

D
3
D1

1

D3

4
2

D2

Go
3

4

1

2

Fig. 7. A given side-information digraph D such that f (D) = H30 , and a source-constraint graph Go . We have V (D1 ) = {1},
V (D2 ) = {2} and V (D3 ) = {3, 4}. From Theorem 7, we get β(D, Go ) = 2, and from Proposition 7, β(D) = β(D, Go ) = 2.
It is not difficult to observe that a two-sender-index code {x1 ⊕ x3 , x2 ⊕ x4 }, that is obtained by transmitting x1 ⊕ x3 and
x2 ⊕ x4 from sender 1 and sender 2, respectively, achieves its optimal broadcast rate both in TSUIC and SSUIC.

Proof: Refer to Appendix C.
Proposition 7: For any D having a fully participated interaction between its sub-digraphs D1 ,
D2 and D3 such that f (D) ∈ {H30 , H32 , H33 }, β(D, Go ) = β(D).
Proof: For the given digraph D, by applying Theorem 3, one can get β(D) = max{β(D3 ),
β(D1 ) + β(D2 )}. Now from Theorem 7, we have β(D, Go ) = max{β(D3 ), β(D1 ) + β(D2 )}.
Altogether, β(D, Go ) = β(D) = max{β(D3 ), β(D1 ) + β(D2 )}.
Remark 4: In TSUIC, for any D having a fully participated interaction between its non-empty
sub-digraphs D1 , D2 and D3 such that f (D) = H31 , no TSUIC scheme achieves β(D) if
β(D3 ) < β(D1 ) + β(D2 ) because β(D) = max{β(D3 ), max{β(D1 ), β(D2 )}} (by Theorem 3)
and β(D, Go ) is at least β(D1 ) + β(D2 ) (by Lemma 6).
Example 4: Consider a TSUIC problem of the following: (1|3, 4), (2|3, 4), (3|1, 2, 4), (4|1, 2),
and M1 = {1, 3, 4}, M2 = {2, 3, 4}. We compute its β(D, Go ) and βt (D, Go ) using Theorem 7.
Refer to Fig. 7 for details.
C. Optimal broadcast rates of a digraph D having a fully participated interaction between its
sub-digraphs D1 , D2 and D3 such that f (D) belongs to CASE II-C and CASE II-D: An upper
bound, and special cases where the upper bound is tight
Theorem 8 (CASE II-C): For any D having a fully participated interaction between its subdigraphs D1 , D2 and D3 , and t-bit messages for any t ≥ 1, if f (D) ∈ {H34 , H35 , . . . , H45 }, then
(i) βt (D, Go ) ≤ βt (D2 ) + max{βt (D1 ), βt (D3 )}, (ii) βt (D, Go ) = βt (D1 ) + βt (D2 ) if βt (D1 ) ≥
βt (D3 ), (iii) β(D, Go ) ≤ β(D2 ) + max{β(D1 ), β(D3 )}, and (iv) β(D, Go ) = β(D1 ) + β(D2 ) if
β(D1 ) ≥ β(D3 ).
Proof: Refer to Appendix D.

November 23, 2017

DRAFT

DRAFT

29

Proposition 8: For any D having a fully participated interaction between its sub-digraphs
D1 , D2 and D3 such that f (D) ∈ {H34 , H35 , . . . , H40 , H43 , H44 , H45 } (all digraphs of CASE II-C
except H41 and H42 ), β(D, Go ) = β(D2 ) + max{β(D1 ), β(D3 )}.
Proof: It follows from Theorem 8 that β(D, Go ) = β(D1 ) + β(D2 ) if β(D1 ) ≥ β(D3 ), and
for the case when β(D1 ) ≤ β(D3 ),
β(D, Go ) ≤ β(D2 ) + β(D3 ).

(22)

Considering Theorem 3, we get β(D) = β(D2 )+β(D3 ) if β(D1 ) ≤ β(D3 ). As β(D) ≤ β(D, Go )
(Lemma 5), so
β(D, Go ) ≥ β(D2 ) + β(D3 ).

(23)

From (22) and (23), we get β(D, Go ) = β(D2 ) + β(D3 ) if β(D1 ) ≤ β(D3 ). Altogether,
β(D, Go ) = β(D2 ) + max{β(D1 ), β(D3 )}.
Proposition 9: For any D having a fully participated interaction between its sub-digraphs D1 ,
D2 and D3 such that f (D) ∈ {H34 , H35 , . . . , H40 }, β(D, Go ) = β(D) if β(D1 ) ≥ β(D3 ).
Proof: For the given digraph D, by applying Theorem 3, one can get β(D) = β(D2 ) +
max{β(D1 ), β(D3 )}. Thus β(D) = β(D1 ) + β(D2 ) if β(D1 ) ≥ β(D3 ). Now from Theorem 8,
we have β(D, Go ) = β(D1 ) + β(D2 ) if β(D1 ) ≥ β(D3 ). Altogether, β(D, Go ) = β(D) =
β(D1 ) + β(D2 ).
Remark 5: For any D such that f (D) ∈ {H41 , H42 }, we are not able to express β(D) as a
function of β(D1 ), β(D2 ) and β(D3 ) in general, so in TSUIC, it is not easy to check whether
β(D, Go ) equal to β(D) or not for this case. Now for any D such that f (D) ∈ {H43 , H44 , H45 }, in
TSUIC, we achieve β(D), which is equal to β(D1 ) + β(D2 ) if β(D1 ) = β(D3 ) ≤ β(D2 ) + β(D3 ).
If β(D1 ) > β(D2 ) + β(D3 ), then it is not difficult to observe that β(D) is not achievable in
TSUIC.
Example 5: Consider a TSUIC problem D of the following: (1|2, 4, 5), (2|4, 5), (3|1, 2), (4|1, 2, 5),
(5|1, 2, 4), and M1 = {1, 2, 4, 5}, M2 = {3, 4, 5}. We compute its β(D, Go ) and βt (D, Go ) using
Theorem 8. Refer to Fig. 8 for details.
Corollary 2 (CASE II-D): For any D having a fully participated interaction between its subdigraphs D1 , D2 and D3 , and t-bit messages for any t ≥ 1, if f (D) ∈ {H46 , H47 , . . . , H57 }, then
(i) βt (D, Go ) ≤ βt (D1 ) + max{βt (D2 ), βt (D3 )}, (ii) βt (D, Go ) = βt (D1 ) + βt (D2 ) if βt (D2 ) ≥
βt (D3 ), (iii) β(D, Go ) ≤ β(D1 ) + max{β(D2 ), β(D3 )}, and (iv) β(D, Go ) = β(D1 ) + β(D2 ) if
β(D2 ) ≥ β(D3 ).
November 23, 2017

DRAFT

DRAFT

30

D

5

4

3

1
D1

Fig. 8.

Go
4

D3

5
3

1

D2

2

2

(a) A given side-information digraph D such that f (D) = H36 , and a source-constraint graph Go . We have

V (D1 ) = {1, 2}, V (D2 ) = {3}, and V (D3 ) = {4, 5}. From Theorem 8, we get β(D, Go ) = 3 and from Proposition 9,
β(D) = β(D, Go ) = 3. It is not difficult to observe that a two-sender index code {x1 ⊕x4 ⊕x5 , x2 , x3 }, where (x1 ⊕x4 ⊕x5 , x2 )
and x3 are transmitted by sender 1 and sender 2, respectively, achieves its optimal broadcast rate both in TSUIC and SSUIC.

Proof: For the given digraph D, let D0 be the digraph obtained by swapping D1 and D2 in D
(in other words, we say that the contents of the two senders are swapped). So, D0 is obtained by
swapping D1 and D2 of D, and vice-versa. Considering the definition of the function f , one can
find that swapping D1 and D2 in D implies swapping vertices 1 and 2 in H. So, after swapping,
observe H34 from H46 , H35 from H47 , and so on up to H45 from H57 (in Fig. 3). Clearly, after
swapping D1 and D2 of D0 in its results stated by Theorem 8, we get the valid results for D.
Remark 6: After swapping D1 and D2 in the results stated by Propositions 8 and 9, and the
observations stated in Remark 5, we obtain the results for a digraph D whose f (D) is one of
the digraphs of CASE II-D.
D. Optimal broadcast rates of a digraph D having a fully participated interaction between its
sub-digraphs D1 , D2 and D3 such that f (D) belongs to CASE II-E: Conditions and bounds
Theorem 9 (CASE II-E): For any D having a fully participated interaction between its subdigraphs D1 , D2 and D3 , and t-bit messages for any t ≥ 1, if f (D) ∈ {H58 , H59 , . . . , H64 }, then
(i) βt (D, Go ) ≤ max(βt (D1 ), βt (D3 )) + max(βt (D2 ), βt (D3 )), (ii) βt (D, Go ) = βt (D1 ) + βt (D2 )
if βt (D3 ) ≤ min{βt (D1 ), βt (D2 )}, (iii) β(D, Go ) ≤ max(β(D1 ), β(D3 )) + max(β(D2 ), β(D3 )) ,
and (iv) β(D, Go ) = β(D1 ) + β(D2 ) if β(D3 ) ≤ min{β(D1 ), β(D2 )}.
Proof: Refer to Appendix E.
Proposition 10: For any D having a fully participated interaction between its sub-digraphs D1 ,
D2 and D3 such that f (D) ∈ {H58 , H59 , H60 }, β(D, Go ) = β(D) = β(D3 )+max{β(D1 ), β(D2 )}
if min{β(D1 ), β(D2 )} ≤ β(D3 ) ≤ max{β(D1 ), β(D2 )}.

November 23, 2017

DRAFT

DRAFT

31

Proof: It follows from Theorem 9 that β(D, Go ) ≤ max{β(D1 ), β(D3 )}+max{β(D2 ), β(D3 )}.
So, considering min{β(D1 ), β(D2 )} ≤ β(D3 ) ≤ max{β(D1 ), β(D2 )}, if β(D1 ) ≥ β(D2 ), then
β(D, Go ) ≤ β(D1 ) + β(D3 ),

(24)

β(D, Go ) ≤ β(D2 ) + β(D3 ).

(25)

β(D, Go ) ≤ β(D3 ) + max{β(D1 ), β(D2 )},

(26)

and if β(D2 ) ≥ β(D1 ), then

From (24) and (25), we get

if min{β(D1 ), β(D2 )} ≤ β(D3 ) ≤ max{β(D1 ), β(D2 )}. Now from Theorem 3, one can get
β(D) = β(D3 ) + max{β(D1 ), β(D2 )}. As β(D) ≤ β(D, Go ) (Lemma 5), we get
β(D, Go ) ≥ β(D3 ) + max{β(D1 ), β(D2 )}.

(27)

From (26) and (27), we get β(D, Go ) = β(D3 ) + max{β(D1 ), β(D2 )}.
IX. D ISCUSSIONS
Consider any digraph D and its sub-digraphs D1 , D2 and D3 . Let d+
D (u) be the out-degree of
a vertex u of D. Now we make the following two observations in TSUIC:
•

The role of side-information of the vertices in V (D3 ) (whose vertices are requesting common
messages) about the messages requested by vertices in V (D1 ∪ D2 ) (whose vertices are
requesting private messages) in TSUIC: It is proved in SSUIC that if the interaction
between D1 , D2 and D3 is acyclic, i.e., f (D) belongs to one of the digraphs in CASE I,
then β(D) = β(D1 ) + β(D2 ) + β(D3 ) (by using Theorem 3). This means that the arcs
contributing acyclic interactions between the sub-digraphs of D can be removed without
affecting the optimal broadcast rate of D, meaning that those are non-critical arcs. In this
paper, we have proved that this result is also true in TSUIC (by Theorem 4). Moreover, in
TSUIC, we have proved that for D, if the vertices in V (D3 ) have no side-information about
the messages requested by vertices in V (D1 ∪ D2 ), i.e., d+
f (D) (3) = ∅, then by Theorem 6, we
have β(D, Go ) = β(D1 ) + β(D2 ) + β(D3 ) (behaves like having acyclic interactions between
D1 , D2 and D3 ). This infers that in TSUIC, for any D, any arc that is contributing an
interaction between D1 , D2 and D3 is a non-critical arc if we have the vertices in V (D3 ) with
no side-information about the messages requested by vertices in V (D1 ∪ D2 ). For the cases

November 23, 2017

DRAFT

DRAFT

32

where vertices in V (D3 ) having fully-participated interaction with the vertices in V (D2 ) or
V (D1 ) or both in a digraph D having a cyclic-fully-participated interaction between D1 ,
D2 and D3 , we have seen that β(D, Go ) < β(D1 ) + β(D2 ) + β(D3 ) by Theorem 7, 8, and
9. In the same regard, the result is not known for D having a cyclic-partially-participated
interaction between its sub-digraphs D1 , D2 and D3 .
•

Non-critical arcs in SSUIC are not necessarily non-critical in TSUIC: We illustrate this
with an example. Consider the TSUIC problem stated in Example 1 (whose f (D) = H58 ).
In SSUIC, we know that the optimal broadcast rate β(D) = 2. This problem has an arc
(3, 1) that is non-critical in SSUIC (its removal does not change the optimal broadcast rate)
but it is critical in TSUIC. This can be understood from the following: In SSUIC, we can
remove the arc (3, 1) ∈ A(D), and still form a valid index code {x1 ⊕ x2 , x3 } that achieves
β(D). This infers that removing the arc (3, 1) does not affect the optimal broadcast rate in
SSUIC. However, in TSUIC, if we remove the arc (3, 1) ∈ A(D), then the new problem,
say D0 , has β(D0 , Go ) = 3 (applying Theorem 6), whereas we get a valid two-sender index
code {x1 ⊕ x3 , x2 ⊕ x3 } of codelength two if we consider (3, 1) ∈ A(D).
X. C ONCLUDING REMARKS AND OPEN PROBLEMS

In this paper, we studied two-sender unicast-index-coding problems and established their
structural characteristics. Noting that SSUIC is a well studied problem (though for any arbitrary
instance, it is still an open problem), there have been many important contributions made in the
literature. In this paper we solved TSUIC instances by expressing the optimal broadcast rates in
terms of that of SSUIC. To this end, we introduced a two-sender graph coloring of confusion
graphs in TSUIC, and propose a way of grouping the vertices of a confusion graph for the ease
of its analysis while coloring. With these, we derived optimal broadcast rates of TSUIC problems,
both in the asymptotic and non-asymptotic regime, as a function of the optimal broadcast rates
of their sub-problems. We have also presented a class of TSUIC instances where the interactions
between the sub-problems of the problem are not critical.
Some open problems for future works are the following:
•

Study of the critical edges in the TSUIC problems: It is observed that the non-critical
arcs in SSUIC can be critical arcs in TSUIC. This requires further study.

•

Extend the results to more than two senders: As our study of TSUIC problems is a step
towards understanding multi-sender index coding, a general distributed index coding, it is

November 23, 2017

DRAFT

DRAFT

33

left as a future work to extend the approaches implemented and the results obtained in this
paper to more general setups.
•

Finding the optimal broadcast rates of TSUIC problems with cyclic-partially-participated
interactions: The analysis of D with partially-participated interactions between its subdigraphs D1 , D2 and D3 is left as a future work.
A PPENDIX A

The two figures in Fig. 9 outline the labels used to represent vertices of a confusion graph.
xni0 −1 xni0

x1 x2

1
0
1

i
D2
1

0

D

,b

D

j2

2

(b i
1
D

1

,b k
D

3

,b

D

j2

2

1

)

k1

B bjD2 2,b D 3

,b k
D

3

1

)

D1

3

k

,bD1

3

1
n 0
i
b2Di0 −3
n 0
i
b2Di0 −2
2ni0 −1
bDi0
n 0
i
b2Di0

0
1
0
1

0

1

1

(a)
Fig. 9.

(b

i
D2

j1 2

0

1

k2

B bjD1 2,b D 3

,b D

0

i1 1

Bbi1

,bD1

j1 2

k

D1

,b D

Bbi2

j2 2

1

1

)

3

j2 2

0

D

1

,b D

1

(b i
2

k

i1 1

0

D

B bD

1

1

,b

)

,b D

0

2

1

B bD

n 0 −1
i
b2Di0 −1
2ni0 −1
bDi0
n 0 −1
i
b2Di0 +1
n 0 −1
i
b2Di0 +2
n 0 −1
i
b2Di0 +3
2ni0 −1 +4
bDi0

1

D

k1

B bjD1 2,b D 3

k

3

i2 1

1

,b

D

j1

B bD

bDi0

0

,b

i2 1

0

2ni0 −1 −2

j1

2

B bD

n 0 −1
i
−3

i1

1

0

1

,b

D

(b

0
b2Di0

(b

1

,b

D

j1

2

Vertices of the j2 -th SUB-BLOCK

0

Vertices of the k1 -th BLOCK

b1Di0
b2Di0
b3Di0
b4Di0

(b

D

i1

1

,b

D

j1

2

,b

(b i
2

D

(b i
1
1

Bbi1

D1

k

,bD2

3

D

k

1

2

)

3

D

,b

D

k2

B bjD2 2,b D 3

k

2

3

,b

D

j2

2

)

,b k
D

3

,b

D

j2

2

Bbi2

D1

,b k
D

3

2

2

)

k

,bD2

3

)

(b)
j 00

(a) Each ni0 -bit tuple bDi 0 with its respective bits for t = 1, where i0 ∈ {1, 2, 3} and ji00 ∈ {1, 2, . . . , 2ni0 }, and (b)
i

representation of the vertices (e.g., (biD11 , bjD12 , bkD3 )) and sets of vertices (e.g., Bbj1

D2

k

,bD1

), each represented by a dotted line, in

3

a confusion graph.

A PPENDIX B
P ROOF OF P ROPOSITION 6
Before proving proposition 6, with the help of the following example, we provide an overview
of the construction of the confusion graph and its two-sender graph coloring, which after
generalization leads to the proof of Proposition 6.

November 23, 2017

DRAFT

DRAFT

34

(b1D1 , b1D2 , bkD3 ) (b2D1 , b1D2 , bkD3 ) (b1D1 , b2D2 , bkD3 ) (b2D1 , b2D2 , bkD3 )

(0,0,00)

(1,0,00)

(0,1,00)

(1,1,00)
k = 1 block

k = 2 block

D
3
D1

D3

1

(1,0,10)

(0,1,10)

(1,1,10)

(0,0,01)

(1,0,01)

(0,1,01)

(1,1,01)

Here,

4
2

Go
3

(0,0,10)

D2

k = 3 block

4

1

2

k = 4 block
(0,0,11)

(1,0,11)

(a)

(0,1,11)

(1,1,11)

(b)

Fig. 10. (a) A given side-information digraph D such that f (D) = H26 , and a source-constraint graph Go , (b) the confusion
graph Γ1 (D), and its two-sender graph coloring (where each vertex is assigned with an ordered pair of colors such that the first
color is always associated with S1 and the second color is always associated with S2 ). The edges are shown in color only for an
illustration purpose, it is not an edge coloring.

A. An example
Consider a TSUIC problem (D, Go ) of the following: (1|2), (2|1), (3|4), (4|3), and M1 =
{1, 3, 4}, M2 = {2, 3, 4} with t = 1. For D, we have f (D) = H26 . Refer to Fig. 10 for its
confusion graph Γ1 (D) whose vertices are grouped according to our proposed method. Now
in details, we illustrate the construction of Γ1 (D) and its two-sender graph coloring. These
are used to derive βt=1 (D, Go ). For the problem, we have V (D1 ) = {1}, V (D2 ) = {2}, and
V (D3 ) = {3, 4}. Γ1 (D) has 24 = 16 vertices labeled by all possible realizations of a word

with four bits, each one is represented by a unique (biD1 , bjD2 , bkD3 ) label, where i, j ∈ {1, 2},
k ∈ {1, 2, 3, 4}, sub-labels biD1 , bjD2 ∈ {0, 1} and bkD3 ∈ {00, 01, 10, 11}.

Consider the block with k = 1, it has four vertices labeled by (0, 0, 00), (1, 0, 00), (0, 1, 00) and
(1, 1, 00). One can find the intra-block edges5 (due to confusion at some receivers in V (D1 ∪ D2 )),
and inter-block edges (due to confusion at some receivers in V (D)) as shown in Fig. 10. We
5

Refer to Definition 9 for intra-block and inter-block edges.

November 23, 2017

DRAFT

DRAFT

35

observe that all the blocks are isomorphic to each other. Now we color Γ1 (D) starting from the
block with k = 1. We color similarly for any other individual block. Consider its sub-block with
j = 1, and it has two vertices (0, 0, 00) and (1, 0, 00). As these two tuples ((0, 0, 00) and (1, 0, 00))
are confused at receiver 1, so S1 must assign different colors, and S2 must assign the same color
(by Lemma 1). Thus we assign say (0, 0, 00) → (RED, RED) and (1, 0, 00) → (BLUE, RED).
We color similarly for any individual sub-block. For the sub-graph of Γ1 (D) induced by the
vertices in Bb1D

1

,b1D

3

= {(0, 0, 00), (0, 1, 00)}, as these two tuples ((0, 0, 00) and (0, 1, 00)) are

confused at receiver 2, so S2 must assign different colors, and S1 must assign the same color (by
Lemma 2). Thus we assign say (0, 0, 00) → (RED, RED) and (0, 1, 00) → (RED, BLUE). We
color similarly for any individual sub-graph of this type. By carrying this way of coloring (as of
the sub-block and the sub-graph) to all the vertices of the block with k = 1, altogether, we have the
following: (0, 0, 00) → (RED, RED), (1, 0, 00) → (BLUE, RED), (0, 1, 00) → (RED, BLUE),
and (1, 1, 00) → (BLUE, BLUE). We say a two-sender graph coloring is the best possible
coloring if it corresponds to the minimum sum of the bits, which is required to uniquely index
the colors associated with each sender, in TSUIC. As |V (D1 )| = 1, Γ1 (D1 ) is a graph with

two vertices (labeled by 0 and 1) connected by an edge. Thus χ(Γ1 (D1 )) = 2. Similarly, we
get χ(Γ1 (D2 )) = 2. Now considering Propositions 1, 2, 3, 4, and our proposed grouping of the
vertices of a confusion graph, one can get χ(Γ1 (D1 )) × χ(Γ1 (D2 )) ordered pairs of colors in the
best possible coloring of a block of Γ1 (D) in two-sender graph coloring. Thus, in any block,
the four ordered pairs of colors (two colors associated per sender), that we have assigned to the
vertices of Γ1 (D), is the best possible coloring.
Now we address the inter-block edges while coloring. We consider any two blocks, and
perform two-sender graph coloring. Firstly, consider the two blocks with k = 1 (all tuples having
bkD3 = 00) and k = 2 (all tuples having bkD3 = 10). As receivers 3 does not have {x1 , x2 } in its
side-information, any tuple of the block with k = 1 and any tuple of the block with k = 2 are
confused at receiver 3. Thus every vertex of the block with k = 1 are connected to each vertex
of the block with k = 2 by an inter-block edge. Consequently, we do not need to consider other
inter-block edges due to confusions at some other receivers for this case. Now during two-sender
graph coloring of these two blocks, we need to have two different ordered pairs of colors (one
for each block). Furthermore, as x3 is a common message to both senders, it suffices to have
two completely different color sets (each for one block) associated with one of the senders. In
other words, one of the senders will contribute additional colors to resolve these confusions

November 23, 2017

DRAFT

DRAFT

36

(indicated by the inter-block edges between the blocks with k equal to 1 and 2). Furthermore, for
this case, one can see that if both senders contribute additional colors to resolve the confusion
referring to the inter-block edges between the blocks, then the total sum of the bits that are
required to represent the colors associated with S1 and S2 is strictly greater than three, which is
required if only one sender contributes additional colors to resolve the confusion. Assume that S1
contributes the additional colors to resolve the confusions (inter-block edges) between the vertices
of these blocks. Now we have the following coloring for the vertices of the block with k = 2:
(0, 0, 10) → (YELLOW, RED), (1, 0, 10) → (GREEN, RED), (0, 1, 10) → (YELLOW, BLUE),
and (1, 1, 10) → (GREEN, BLUE). Secondly, we color similarly as above for the blocks with k
equal to (i) 1 and 3, (ii) 2 and 4, and (iii) 3 and 4. Thirdly, we consider the two blocks with k = 1
(all tuples having bkD3 = 00) and k = 4 (all tuples having bkD3 = 11). Clearly, these blocks have
no inter-block edges due to the confusion at receivers 3 and 4. The inter-block edges are due to
the confusion at receivers 1 and 2, and one can see them as shown in Fig. 10. It is not difficult
to verify that if we color the vertices of the block with k = 4 by the same coloring function
done for the vertices of the block with k = 1, which is a function of (biD1 , bjD2 ) sub-labels of
the vertices, then the coloring is still valid. Thus in order to color the vertices of the block with
k = 4, we do not need any additional colors for senders than that assigned to the vertices of the
block with k = 1. Finally, we color similarly as above for the blocks with k equal to 2 and 3.
Now observe Γ1 (D) by assuming each block as one super-vertex, the edges that connects all the
vertices of one block to every vertex of another block, and vice-versa (edges due to confusion
at some receivers in V (D3 )) as a single super-edge connecting those two super-vertices, and
neglect all the inter-block edges due to the confusion at some receivers except receivers in V (D3 ),
we see that the resulting graph is Γ1 (D3 ). Clearly, in two-sender graph coloring, we require
χ(Γ1 (D3 )) times of χ(Γ1 (D1 )) × χ(Γ1 (D2 )) (which is required for each block) ordered pairs of
colors in total, i.e., 2 × 4 = 8 ordered pairs of colors. In this way, we color the whole Γ1 (D)
with J1 = {RED, BLUE, YELLOW, GREEN} and J2 = {RED, BLUE}, and one can verify
that this is the best possible coloring in two-sender graph coloring. Consequently, S1 and S2
need to transmit 2-bit and 1-bit sub-codewords, respectively. Thus βt=1 (D, Go ) = 3, and one can
find that βt=1 (D, Go ) = β(D1 ) + β(D2 ) + β(D3 ) = 3.

November 23, 2017

DRAFT

DRAFT

37

B. Proof of Proposition 6
We prove the following lemmas that is used to prove the proposition. Refer to Section IV for
notations. For any D, refer to Definition 9 for the definition of intra-block and inter-block edges
of Γt (D).
Lemma 7: In two-sender graph coloring of any k-th block of the confusion graph Γt (D) of
any digraph D, the minimum number of colors associated with S1 and S2 are χ(Γt (D1 )) and
χ(Γt (D2 )), respectively, and the minimum of χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of colors are
required to color the block.
Proof: For any D, based on our proposed way of grouping the vertices of Γt (D) (see
Section VI), we write the vertices of any k-th block of Γt (D) in the following matrix form (for
notations see Section IV):

(b1 , b1 , bk ) (b2D1 , b1D2 , bkD3 )
 D1 D2 D3

 (b1 , b2 , bk ) (b2 , b2 , bk )
 D1 D2 D3
D1
D2
D3
Bk = 

..
..

.
.


tn2
tn2
(b1D1 , b2D2 , bkD3 ) (b2D1 , b2D2 , bkD3 )

tn1
(b2D1 , b1D2 , bkD3 )

...





. . . (bD1 , b2D2 , bkD3 ) 



..
..

.
.


tn1
tn2
. . . (b2D1 , b2D2 , bkD3 )
2tn1

We have the following observations in Bk and Γt (D):
1) For any i, j, the sets of all the vertices of the j-th row and all the vertices of the i-th
column of the matrix Bk are Bbj

k
D2 ,bD3

and BbiD

1

,bkD

, respectively.
3

2) All the vertices of this block have the same bkD3 sub-label, so we do not need to consider
bkD3 sub-label of the vertices while analyzing any k-th block of Γt (D).
3) A sub-block (a sub-graph of Γt (D) induced by the vertices in Bbj

k
D2 ,bD3

) has vertices with

the same (bjD2 , bkD3 ) sub-labels (see any row of Bk ). So, we consider only biD1 sub-label

while analyzing any j-th sub-block of Γt (D). Now assume that we relabel the vertices
of the j-th sub-block by the first sub-label, i.e., (biD1 ) ∈ (biD1 , bjD2 , bkD3 ). Consequently
all the rows of Bk become identical. Thus we can consider one sub-block, analyze it and
find its results, and these results carry similarly over all the sub-blocks of the k-th block.
Due to symmetry, by similar reasoning, we consider only bjD2 sub-label while analyzing
any sub-graph of Γt (D) induced by the vertices in BbiD

1

,bkD

3

, and all the columns of Bk

become identical if we relabel the vertices of the i-th column by the second sub-label, i.e.,
(bjD2 ) ∈ (biD1 , bjD2 , bkD3 ).

November 23, 2017

DRAFT

DRAFT

38

(Necessity) For any vertex with (biD1 , bjD2 , bkD3 ) label, one can think about two sets that include
it, viz., Bbj

k
D2 ,bD3

(the set of vertices of the j-th row of Bk ) and BbiD

1

of the i-th column of Bk ) in such a way that Bbj
Bbj

k
D2 ,bD3

\ {(biD1 , bjD2 , bkD3 )} and BbiD

k
D2 ,bD3

1

,bkD

3

∩ BbiD

1

,bkD

3

(the set of vertices

,bkD

3

= {(biD1 , bjD2 , bkD3 )}. Clearly,

\ {(biD1 , bjD2 , bkD3 )} are disjoint sets. Now we recall

that the sub-graph of Γt (D) induced by the vertices in Bbj

k
D2 ,bD3

is isomorphic to Γt (D1 ) (by

Proposition 1), and the vertex-induced sub-graph, which is also known as the j-th sub-block of
the k-th block, requires the minimum of χ(Γt (D1 )) different colors associated with S1 and one
color associated with S2 , i.e., (the minimum of) χ(Γt (D1 )) ordered pairs of colors while coloring
the sub-block in two-sender graph coloring (by Proposition 3). Thus, there exist a minimum
of χ(Γt (D1 )) distinct vertices in Bbj

whose colors are all different. Now considering each

k
D2 ,bD3

of these distinct vertices, one can get χ(Γt (D1 )) numbers of disjoint BbiD

1

,bkD

sets such that
3

each set includes one of these distinct vertices. Clearly, the sub-graph of Γt (D) induced by the
vertices in the union of these disjoint BbiD

1

,bkD

3

sets require at least χ(Γt (D1 )) times the number

of ordered pairs of colors required to color one of the vertex-induced sub-graph by the vertices in
BbiD

1

,bkD

3

(noting that Bbj

k
D2 ,bD3

\ {(biD1 , bjD2 , bkD3 )} and BbiD

1

,bkD

3

\ {(biD1 , bjD2 , bkD3 )} are disjoint

sets). We recall that the sub-graph of Γt (D) induced by the vertices in BbiD

1

,bkD

is isomorphic to
3

Γt (D2 ) (by Proposition 2), and the vertex-induced sub-graph requires the minimum of χ(Γt (D2 ))
different colors associated with S2 and one color associated with S1 , i.e., (the minimum of)
χ(Γt (D2 )) ordered pairs of colors while coloring the sub-block in two-sender graph coloring
(by Propositions 4). Altogether, the block requires at least χ(Γt (D1 )) and χ(Γt (D2 )) colors
associated with S1 and S2 , respectively, and at least χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of
colors in its two-sender graph coloring.
(Sufficiency) Consider a sub-block of Γt (D) induced by the vertices in Bbj

k
D2 ,bD3

(i.e., vertices

in the j-th row of Bk ). As a sub-block requires the minimum of χ(Γt (D1 )) ordered pairs of
colors while coloring it in two-sender graph coloring (by Proposition 3), the sub-block must
have a minimum of χ(Γt (D1 )) independent vertex sets (one unique ordered pair of colors is
assigned to one independent vertex set), otherwise we can color the sub-block with fewer than
χ(Γt (D1 )) ordered pairs of colors, clearly this is not possible. Now for the j-th sub-block, let the
0
0
sequence of independent vertex sets of this sub-block be Vj,1
, Vj,2
, . . . , Vj,0 χ(Γt (D1 )) . Considering

observation (3) above, we assign the similar sequence of independent vertex sets to all other
sub-blocks such that for any pair of j1 -th and j2 -th sub-blocks of the k-th block, any two vertex
sets Vj01 ,m and Vj02 ,m for m ∈ {1, 2, . . . , χ(Γt (D1 ))} have the same set of vertices labeled by the
November 23, 2017

DRAFT

DRAFT

39

first sub-label (biD1 ). Now writing the independent vertex sets of the block in a matrix form, we
get the following matrix of order 2tn2 × χ(Γt (D1 )):

0
0
V0
V1,2
V1,3
 1,1
 0
0
0
 V2,1
V2,2
V2,3


 0
0
0
V0k =  V3,1
V3,2
V3,3

 .
..
..
 ..
.
.


V20tn2 ,1 V20tn2 ,2 V20tn2 ,3

...

V1,0 χ(Γt (D1 ))

...

V2,0 χ(Γt (D1 ))

...

V3,0 χ(Γt (D1 ))

..

..
.

.

. . . V20tn2 ,χ(Γt (D1 ))








,






where a row corresponds to the independent vertex sets of the respective sub-block, and each
column of the matrix has the vertex sets having the same set of vertices labeled by the first
sub-label (biD1 ).
Now for any column m of V0k , as the vertex sets of the column have the same set of
vertices labeled by the first sub-label (biD1 ), we collect the vertices for a fixed index i to a set
0
{(biD1 , bjD2 , bkD3 ) : (biD1 , bjD2 , bkD3 ) ∈ Vj,m
, ∀j}. Clearly, this set equal to BbiD

1

the sub-graph of Γt (D) induced by the vertices in BbiD

1

,bkD

3

,bkD

. Recall that

3

is isomorphic to Γt (D2 ), and this

vertex-induced sub-graph requires the minimum of χ(Γt (D2 )) different colors associated with S2
and one color associated with S1 , i.e., (the minimum of) χ(Γt (D2 )) ordered pairs of colors while
coloring the vertex-induced sub-graph in two-sender graph coloring (refer to Propositions 2 and
4). Thus the vertex-induced sub-graph has a minimum of χ(Γt (D2 )) independent vertex sets.
Now if a vertex in Vj01 ,m and a vertex in Vj02 ,m are independent, then all the vertices in Vj01 ,m and
a vertex in Vj02 ,m are independent. This is because the vertex sets of the column have the same
set of independent vertices labeled by the first sub-label (biD1 ). Thereby, for each column m, we
get (the minimum of) χ(Γt (D2 )) independent vertex sets, and let each of these sets be denoted
by Vm0 ,m for m0 ∈ {1, 2, . . . , χ(Γt (D2 ))}. Now writing the independent vertex sets of a block in
a matrix form, we get the following matrix of order χ(Γt (D2 )) × χ(Γt (D1 )):


V1,1
V1,2
V1,3
...
V1,χ(Γt (D1 ))






V2,1
V2,2
V2,3
...
V2,χ(Γt (D1 ))






Vk = 
,
V3,1
V3,2
V3,3
...
V3,χ(Γt (D1 ))




.
.
.
.
..


.
.
.
.
.
.
.
.
.




Vχ(Γt (D2 )),1 Vχ(Γt (D2 )),2 Vχ(Γt (D2 )),3 . . . Vχ(Γt (D2 )),χ(Γt (D1 ))

November 23, 2017

DRAFT

DRAFT

40

where each element of the matrix corresponds to the independent vertex sets among the respective
rows and columns of Vk .
In two-sender graph coloring of the k-th block, we assign one ordered pairs of colors to each
of the elements in Vk , so we get a χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of colors. Let the
ordered pairs of colors arranged in a matrix form be

(c11 , c21 )
(c12 , c21 )
(c13 , c21 )



(c11 , c22 )
(c12 , c22 )
(c13 , c22 )



Ck = 
(c11 , c23 )
(c12 , c23 )
(c13 , c23 )


..
..
..

.
.
.


(c11 , c2χ(Γt (D2 )) ) (c12 , c2χ(Γt (D2 )) ) (c13 , c2χ(Γt (D2 )) )

...

(c1χ(Γt (D1 )) , c21 )
1

...

(cχ(Γt (D1 )) , c22 )

...

(c1χ(Γt (D1 )) , c23 )

..

..
.

.

. . . (c1χ(Γt (D1 )) , c2χ(Γt (D2 )) )








,






where Ck (m0 , m) = (c1m , c2m0 ) is the color of all vertices in Vk (m0 , m) = Vm0 ,m , for all elements
of the matrices. Referring to the Definition 8 (two-sender graph coloring), one can find that this
is a valid coloring, where the colors associated with S1 and S2 are χ(Γt (D1 )) and χ(Γt (D2 )),
respectively.
Lemma 8: Consider a two-sender graph coloring function Jo that properly colors the confusion graph Γt (D). If there is no inter-block edge due to the confusion at some receiver in
V (D3 ) between any blocks of Γt (D), then Jo (biD1 , bjD2 , b1D3 ) = Jo (biD1 , bjD2 , b2D3 ) = · · · =
tn3

Jo (biD1 , bjD2 , b2D3 ), for all i and j, is a valid two-sender graph coloring.

Proof: We first prove the lemma considering any two blocks, say k1 -th block and k2 -th block.
If there is no inter-block edge due to the confusion at any receiver in V (D3 ) between the k1 -th and
k2 -th blocks of Γt (D), then we have two cases: (i) no inter-block edge and (ii) some inter-block
edges due to the confusion at some receivers in V (D1 ) ∪ V (D2 ). In case (i), since k1 -block and
k2 -block are isomorphic, we can color a block by two-sender graph coloring, and keep the same
copy of colorings in another block (i.e., Jo (biD1 1 , bjD12 , bkD13 ) = Jo (biD1 1 , bjD12 , bkD23 ), ∀i1 , j1 ). Now

for case (ii), suppose that there exists an edge ((biD1 , bjD2 , bkD13 ), (biD2 1 , bjD22 , bkD23 )) ∈ E(Γt (D)).
We know that k1 and k2 are two different blocks, so k1 6= k2 . Moreover, since the edge is
due to the confusion at some receivers in V (D1 ) ∪ V (D2 ), we must have (i, j) 6= (i2 , j2 ).
Now if there exists the edge ((biD1 , bjD2 , bkD13 ), (biD2 1 , bjD22 , bkD23 )), then there must exist an edge
((biD1 , bjD2 , bkD13 ), (biD2 1 , bjD22 , bkD13 )). This edge is between the vertices of the same block, and
the confusion must have already resolved by the coloring Jo . Thereby, Jo (biD1 , bjD2 , bkD13 ) =
Jo (biD1 , bjD2 , bkD23 ), ∀i, j, is a valid coloring.
November 23, 2017

DRAFT

DRAFT

41

Since the choice of k1 and k2 is arbitrary, a two-sender graph coloring of all the blocks of
Γt (D) with Jo (biD1 , bjD2 , bkD13 ) = Jo (biD1 , bjD2 , bkD23 ) = · · · = Jo (biD1 , bjD2 , bkDm3 ), for all i and j, is
a valid two-sender graph coloring.
Lemma 9: For D having fully-participated interactions between its sub-digraphs D1 , D2 and
D3 , the confusion at some receivers in V (D1 ) does not contribute any inter-block edges in
Γt (D) if D1 → D3 in D (equivalently, (1, 3) ∈ A(f (D))), and the confusion at some receivers
in V (D2 ) does not contribute any inter-block edges in Γt (D) if D2 → D3 in D (equivalently,
(2, 3) ∈ A(f (D))).
Proof: There is no edge due to the confusion at some receivers in V (D1 ) between any
pair of vertices ((biD1 1 , bjD12 , bkD13 ), (biD1 , bjD2 , bkD23 )) such that (biD1 1 , bjD12 , bkD13 ) ∈ Bbj1

(biD1 , bjD2 , bkD23 ) ∈ Bbj

k2
D2 ,bD3

k1
D2 ,bD3

and

because any vertex in V (D1 ) has {xu : u ∈ V (D3 )} in its side-

information and the corresponding bkD13 and bkD23 labels of the two vertices are different. This

proves the first assertion. Repeating the same argument for D2 , we get the second assertion (for
the case D2 → D3 in D).

Lemma 10: For any real numbers A and B, dA + Be = dAe + dBe + 0 , where 0 ∈ {−1, 0}.
Proof: As we know that for any real number A, we have A ≤ dAe, and dAe − A < 1 (this

implies dAe < A + 1 or dAe − 1 < A). So we get A ≤ dAe < A + 1. This is true for any other
real number A + B, so A + B ≤ dA + Be < A + B + 1. Altogether, we get
dAe + dBe − 2 < A + B ≤ dA + Be < A + B + 1 ≤ dAe + dBe + 1
dAe + dBe − 2 < dA + Be < dAe + dBe + 1.

(28)

There are only two integers in (dAe + dBe − 2, dAe + dBe + 1), and they are dAe + dBe − 1
and dAe + dBe, so dA + Be = dAe + dBe + 0 , where 0 ∈ {−1, 0}.

Proof of Proposition 6: We first consider D having f (D) = H27 , denoted D27 , and construct

its confusion graph. Then we color Γt (D27 ) by two-sender graph coloring. While constructing
the confusion graph of D27 , we group its vertices according to the grouping of vertices of the
confusion graph described in Section VI.
(Construction of the confusion graph of D27 ) All edges of Γt (D27 ) are listed in the following:
(i) Edges in E(Γt (D27 )) due to the confusion at some vertices in V (D1 ): The confusion at
any vertex in V (D1 ) contributes to only intra-edges due to Lemma 9.
(ii) Edges in E(Γt (D27 )) due to the confusion at some vertices in V (D2 ): The confusion at
any vertex in V (D2 ) contributes to only intra-edges due to Lemma 9.
November 23, 2017

DRAFT

DRAFT

42

(iii) Edges in E(Γt (D27 )) due to the confusion at some vertices in V (D3 ): If there exists an
edge due to the confusion at some vertices in V (D3 ) between any vertex pair ((biD1 , bjD2 , bkD13 ),
(biD2 1 , bjD22 , bkD23 )), then each of the vertices in the k1 -th block has edges with all the vertices in
the k2 -th block. This is because any vertex in V (D3 ) has no message requested by any vertex in
V (D1 ) ∪ V (D2 ) in its side-information resulting in there being no effect due to a change in bits

of biD1 or bjD2 sub-label once we have an edge due to confusion at some receivers in V (D3 ) that
corresponds to the change in bits of the bkD3 sub-label.
(Coloring the confusion graph Γt (D27 )) In SSUIC, we know that the minimum numbers of
colors required to color D1 , D2 and D3 separately are χ(Γt (D1 )), χ(Γt (D2 )) and χ(Γt (D3 )),
respectively. From Lemma 7, in two-sender graph coloring, vertices in any k-th block of Γt (D27 )
are colored properly with the minimum of χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of colors,

where the minimum number of colors associated with S1 and S2 are χ(Γt (D1 )) and χ(Γt (D2 )),
respectively. Referring to the construction of Γt (D27 ), the inter-block edges are solely due to
the confusion at some vertices in V (D3 ) (from (i), (ii) and (iii) of the construction), and if
there exists an inter-block edge between any two vertices, the first one belonging to k1 -th
block and the second one belonging to k2 -th block, then we have edges from every vertex of
the k1 -th block to all vertices of the k2 -th block. This states that it is necessary to have two
different sets of ordered pairs of χ(Γt (D1 )) × χ(Γt (D2 )) colors, one for each block if there
is an edge between these blocks. Furthermore, it is sufficient to consider the different color
sets associated with one of the senders for those blocks in order to obtain the different sets
of χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of colors. As we require the minimum of χ(Γt (D3 ))
ordered pairs of colors to color vertices in any Bbi

j
D1 ,bD2

(refer to Propositions 5), so the total

number of minimum ordered pairs of colors required to color Γt (D27 ) in two-sender graph
coloring is χ(Γt (D1 )) × χ(Γt (D2 )) × χ(Γt (D3 )). Let χ1 (Γt (D3 )) and χ2 (Γt (D3 )) be the nonnegative non-zero integer factors of χ(Γt (D3 )) which are the best choice over all χ1 (Γt (D3 )) and
χ2 (Γt (D3 )) such that the term dlog2 (χ(Γt (D1 ))× χ1 (Γt (D3 )))e+dlog2 (χ(Γt (D2 ))× χ2 (Γt (D3 )))e
is minimized. Here an integer is considered because each sender broadcasts sub-codewords in
bits. Now χ(Γt (D1 )) × χ1 (Γt (D3 )) and χ(Γt (D2 )) × χ2 (Γt (D3 )) are the colors associated with
S1 and S2 , respectively, and they produce χ(Γt (D1 )) × χ(Γt (D2 )) × χ(Γt (D3 )) ordered pairs of

November 23, 2017

DRAFT

DRAFT

43

colors required for two-sender graph coloring of Γt (D27 ). Now from Theorem 2, we get
t × βt (D27 , Go )
= dlog2 (χ(Γt (D1 )) × χ1 (Γt (D3 )))e + dlog2 (χ(Γt (D2 )) × χ2 (Γt (D3 )))e
= dlog2 (χ(Γt (D1 ))) + log2 (χ1 (Γt (D3 )))e + dlog2 (χ(Γt (D2 ))) + log2 (χ2 (Γt (D3 )))e
= dlog2 (χ(Γt (D1 )))e + dlog2 (χ1 (Γt (D3 )))e + dlog2 (χ(Γt (D2 )))e + dlog2 (χ2 (Γt (D3 )))e + 1
= dlog2 (χ(Γt (D1 )))e + dlog2 (χ(Γt (D2 )))e + dlog2 (χ1 (Γt (D3 )) × χ2 (Γt (D3 )))e + 1 + 2
βt (D27 , Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,

(29)

where 1 ∈ {−2, −1, 0} and 2 ∈ {0, 1} are obtained by using Lemma 10, and  = (2 + 1 ) ∈
χ
{−2, −1, 0, 1}, βt (Dm ) = dlog2 ( (Γt t (Dm )))e , for m ∈ {1, 2, 3}. As we know that βt (D27 , Go ) ≤
βt (D1 ) + βt (D2 ) + βt (D3 ) (by (13)), the value of  in (29) cannot be greater than zero. Thus,
 ∈ {−2, −1, 0}. Overall βt (D27 , Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t, where  ∈ {−2, −1, 0}.
Now we consider D having f (D) = H1 , denoted D1 . In contrast to D27 , D1 has no interaction

between D1 , D2 and D3 . This results in extra edges, both intra-block and inter-block edges, in
Γt (D1 ) with respect to Γt (D27 ). We observe that one can build Γt (D1 ) on the top of Γt (D27 )
by adding these extra edges.
(Coloring the confusion graph Γt (D1 )) The extra edges of Γt (D1 ) with respect to Γt (D27 ) are
both intra-block and inter-block edges. The extra intra-block edges do not change the requirements
of ordered pairs of colors in two-sender graph colorings of a block of Γt (D1 ) due to Lemma 7.
Now we address the extra inter-block edges.
For the extra inter-block edges in E(Γt (D1 )) due to the confusion at some vertices in V (D1 ) and
V (D2 ) in two-sender graph coloring, we have the following: If there is no inter-block edge due to
the confusion at some vertices in V (D3 ), then we can do two-sender graph coloring of these blocks
as stated by Lemma 8. This implies that we can do two-sender graph coloring of all these blocks
by χ(Γt (D1 )) × χ(Γt (D2 )) ordered pairs of colors, where the minimum colors associated with S1
and S2 are χ(Γt (D1 )) and χ(Γt (D2 )), respectively. Now referring to the edges in E(Γt (D1 )) due

to the confusion at some vertices in V (D3 ), if any k1 -th and k2 -th blocks have the inter-block
edges (includes all extra edges due to the confusion at some vertices in V (D1 ) and V (D2 )), then
it is necessary to have two different sets of ordered pairs of χ(Γt (D1 )) × χ(Γt (D2 )) colors, one

for each block (the same as of the case of D27 ). Furthermore, it is sufficient to consider different
color sets associated with one of the senders for these blocks in order to achieve the necessity.

November 23, 2017

DRAFT

DRAFT

44

Altogether, similar to D27 , the total number of minimum ordered pairs of colors required to color
Γt (D1 ) in two-sender graph coloring is χ(Γt (D1 )) × χ(Γt (D2 )) × χ(Γt (D3 )). Thus the results for

Γt (D1 ) follow from the results of Γt (D27 ). Hence, βt (D1 , Go ) = βt (D1 ) + βt (D2 ) + βt (D3 ) + /t,
 ∈ {−2, −1, 0}.
A PPENDIX C
P ROOF OF T HEOREM 7
Proof: For the problems in TSUIC, we prove this theorem by constructing a valid index
code based on single-sender index codes. Refer to Section IV for notations.
(First case: βt (D, Go ) = βt (D3 ) if βt (D3 ) ≥ βt (D1 ) + βt (D2 )) The given condition βt (D3 ) ≥
βt (D1 )+βt (D2 ) implies that |C(D3 )| ≥ |C(D1 )|+|C(D2 )| (i.e., p(C(D3 )) ≥ p(C(D1 ))+p(C(D1 )))

for a finite t. Now in TSUIC, we propose that S1 transmits C1 = C 1 (D3 ) ⊕ C(D1 ) of p1 (C(D3 )) =
p(C(D1 )) bits, and S2 transmits C2 = C 2 (D3 ) ⊕ C(D2 ) of p2 (C(D3 )) bits because p2 (C(D3 )) ≥

p(C(D1 )) as we have p(C(D3 )) ≥ p(C(D1 ))+p(C(D1 )) and p1 (C(D3 )) = p(C(D1 )). Each receiver

receives (p1 (C(D3 )) + p2 (C(D3 )))-bit (C1 , C2 ). Now the decoding is done in the following way: (i)
All the vertices in V (D1 ) will decode their requested messages from C1 and its side-information
that also includes {xi : i ∈ V (D3 )} (as there is a fully-participated D1 → D3 in D), (ii) all the
vertices in V (D2 ) will decode their requested messages from C2 and its side-information that
also includes {xi : i ∈ V (D3 )} (as there is a fully-participated D2 → D3 in D), and (iii) all the
vertices in V (D3 ) will decode their requested messages from (C1 , C2 ) and its side-information
that also includes {xi : i ∈ V (D1 ) ∪ V (D2 )} (as there is fully-participated D3 → (D1 ∪ D2 ) in
D). Thus (p1 (C(D3 )) + p2 (C(D3 )))-bit (C1 , C2 ) is a valid index code in TSUIC for this case, and
βt (D, Go ) ≤ (p1 (C(D3 )) + p2 (C(D3 )))/t = p(C(D3 ))/t = βt (D3 ).

(30)

In SSUIC, βt (D) ≥ βt (D3 ) because D3 is a sub-graph of D. Now in TSUIC,
βt (D, Go ) ≥ βt (D) ≥ βt (D3 ).

(31)

From (30) and (31), we have βt (D, Go ) = βt (D3 ).
(Second case: βt (D, Go ) = βt (D1 )+βt (D2 ) if βt (D3 ) ≤ βt (D1 )+βt (D2 )) The given condition
βt (D3 ) ≤ βt (D1 ) + βt (D2 ) implies that |C(D3 )| ≤ |C(D1 )| + |C(D2 )|. Now we have the following
three sub-cases: (i) |C(D3 )| ≥ max{|C(D1 )|, |C(D2 )|}, (ii) |C(D3 )| ≤ |C(D1 )|, and (iii) |C(D3 )| ≤
|C(D2 )|. For these sub-cases, we propose the following:

November 23, 2017

DRAFT

DRAFT

45

(Sub-case (i): |C(D3 )| ≥ max{|C(D1 )|, |C(D2 )|}) S1 transmits C1 = C 1 (D3 ) ⊕ C(D1 ) of

p1 (C(D3 )) = p(C(D1 )) bits, and S2 transmits C2 = C 2 (D3 ) ⊕ C(D2 ) of p(C(D1 )) bits because

p(C(D1 )) ≥ p2 (C(D3 )) as we have p(C(D3 )) ≤ p(C(D1 ))+p(C(D1 )) and p1 (C(D3 )) = p(C(D1 )).
Each receiver receives (p(C(D1 )) + p(C(D1 )))-bit (C1 , C2 ). Now one can verify that the decoding
is done in the same way as stated in the first case. Thus (p(C(D1 )) + p(C(D1 )))-bit (C1 , C2 ) is a
valid index code in TSUIC for this sub-case.
(Sub-case (ii): |C(D3 )| ≤ |C(D1 )|) S1 transmits C1 = C(D3 )⊕C(D1 ) of p(C(D1 )) bits (because
p(C(D3 )) ≤ p(C(D1 ))), and S2 transmits C2 = C(D2 ) of p(C(D1 )) bits. Now the decoding is done
in the following way: (i) All the vertices in V (D1 ) will decode their requested messages from
C1 and its side-information that also includes {xi : i ∈ V (D3 )} (as there is a fully-participated
D1 → D3 in D), (ii) all the vertices in V (D2 ) will decode their requested messages from C2 and
its side-information, and (iii) all the vertices in V (D3 ) will decode their requested messages from
C1 and its side-information that also includes {xi : i ∈ V (D1 )} (as there is a fully-participated
D3 → D1 in D). Thus (p(C(D1 )) + p(C(D1 )))-bit (C1 , C2 ) is a valid encoding in TSUIC for this
sub-case.
(Sub-case (iii): |C(D3 )| ≤ |C(D2 )|) As we have a fully-participated D3 → (D1 ∪ D2 ) in D, so
by swapping D1 and D2 (meaning we swap the two senders) in the sub-case (ii), one can prove
that (p(C(D1 )) + p(C(D1 )))-bit (C1 , C2 ) is a valid index code in TSUIC for this sub-case.
Altogether for the second case,
βt (D, Go ) ≤ (p(C(D1 )) + p(C(D1 )))/t = βt (D1 ) + βt (D2 ).

(32)

By considering βt (D, Go ) ≥ βt (D1 ) + βt (D2 ) (by Lemma 6) and (32), we get, βt (D, Go ) =
βt (D1 ) + βt (D2 ).
Now combining these two cases (First and Second cases), we get
βt (D, Go ) = max{βt (D3 ), βt (D1 ) + βt (D2 )}.

(33)

Now taking a limit t → ∞ on both sides of (33), we get
lim βt (D, Go ) = lim max{βt (D3 ), βt (D1 ) + βt (D2 )}

t→∞

t→∞

lim β(D, Go ) = max{ lim βt (D3 ), lim (βt (D1 ) + βt (D2 ))}.

t→∞

t→∞

t→∞

(34)

We know that β = inf βt = lim βt (by Definition 3), and “a limit of a finite sum of functions
t

t→∞

equals the sum of the limit of each functions, if the limit of each function exists”, so we get
β(D, Go ) = max{β(D3 ), β(D1 ) + β(D2 )} from (34).
November 23, 2017

DRAFT

DRAFT

46

A PPENDIX D
P ROOF OF T HEOREM 8
Proof: For the problems in TSUIC, we prove this theorem by constructing a valid index
code based on single-sender index codes. Refer to Section IV for notations.
In TSUIC, we propose that S1 transmits C1 = C(D1 ) ⊕ C(D3 ) consisting of max{p(C(D1 )),
p(C(D3 ))} bits, and S2 transmits C2 = C(D2 ) of p(C(D1 )) bits. Each receiver receives (p(C(D1 ))+
max{p(C(D1 )), p(C(D3 ))})-bit (C1 , C2 ). Now the decoding is done in the following way: (i) All
the vertices in V (D1 ) will decode their requested messages from C1 and its side-information
that also includes {xi : i ∈ V (D3 )} (as there is a fully-participated D1 → D3 in D), (ii) all the
vertices in V (D2 ) will decode their requested messages from C2 and its side-information, and (iii)
all the vertices in V (D3 ) will decode their requested messages from C1 and its side-information
that also includes {xi : i ∈ V (D1 )} (as there is a fully-participated D3 → D1 in D). Thus
(p(C(D1 )) + p(C(D1 )))-bit (C1 , C2 ) is a valid index code in TSUIC for this case, and
1
βt (D, Go ) ≤ (p(C(D1 ))+max{p(C(D1 )), p(C(D3 ))}) = βt (D2 )+max{βt (D1 ), βt (D3 )}. (35)
t
Now by Lemma 6, we have βt (D, Go ) ≥ βt (D1 ) + βt (D2 ), and from (35), if βt (D1 ) ≥ βt (D3 ),
then βt (D, Go ) ≤ βt (D1 ) + βt (D2 ). Altogether, we get βt (D, Go ) = βt (D1 ) + βt (D2 ).

For the sub-digraph Dj 0 , j 0 ∈ {1, 2, 3}, we know that there exists an index code C(Dj 0 ) of

p(C(Dj 0 )) bits such that p(C(Dj 0 ))/t tends to β(Dj 0 ) if t → ∞, and for any t ≥ 1, β(Dj 0 ) ≤
p(C(Dj 0 ))/t. So, for we write p(C(Dj 0 ))/t = β(Dj 0 ) + t (Dj 0 ), for some t (Dj 0 ) ≥ 0 such that
t (Dj 0 ) tends to zero if message length t tends to infinity. For D, considering the same code
formation, which is a valid two-sender index code, as stated for the cases considering the finite
message length, we get S1 and S2 transmitting sub-codewords of max{p(C(D1 )), p(C(D3 ))} and
p(C(D2 )) bits, respectively. For any t ≥ 1, there exists a two-sender index code of the following
bit length:
p1 + p2 = max{p(C(D1 )), p(C(D3 ))} + p(C(D2 )).
Now dividing both sides by t in the above equation, we get
p1 + p2
= max{p(C(D1 ))/t, p(C(D3 ))/t} + p(C(D3 ))/t
t
= max{β(D1 ) + t (D1 ), β(D3 ) + t (D3 )} + β(D2 ) + t (D2 ),

November 23, 2017

(36)

DRAFT

DRAFT

47

where t (Dj 0 ) ≥ 0 for j 0 ∈ {1, 2, 3}. For any j 0 ∈ {1, 2, 3}, as t (Dj 0 ) → 0 for t → ∞, we get
β(D, Go ) ≤ lim (p1 + p2 )/t = max{β(D1 ), β(D3 )} + β(D2 ).
t→∞

(37)

Alternatively, we can get (37) by taking a limit t → ∞ on both sides of (35) because β = lim βt
t→∞

(by Definition 3).
Clearly, if β(D1 ) ≥ β(D3 ), then from (37), we get
β(D, Go ) ≤ β(D1 ) + β(D2 ).

(38)

Now from Lemma 6 and (38), we get β(D, Go ) = β(D1 ) + β(D2 ) if β(D1 ) ≥ β(D3 ).
A PPENDIX E
P ROOF OF T HEOREM 9
Proof: For the problems in TSUIC, we prove this theorem by constructing a valid index
code based on single-sender index codes. Refer to Section IV for notations.
In TSUIC, we propose that S1 transmits C1 = C(D1 ) ⊕ C(D3 ) of max{p(C(D1 )), p(C(D3 ))}
bits, and S2 transmits C2 = C(D2 ) ⊕ C(D3 ) of max{p(C(D1 )), p(C(D3 ))} bits. Each receiver
receives (max{p(C(D1 )), p(C(D3 ))}+max{p(C(D1 )), p(C(D3 ))})-bit (C1 , C2 ). Now the decoding
is done in the following way: For D (i) if f (D) ∈ {H58 , H59 , . . . , H63 }, all the vertices in V (D1 )
will decode their requested messages from C1 ⊕ C2 and its side-information that also includes
{xi : i ∈ V (D2 )} (as there is a fully-participated D1 → D2 in D), and if f (D) = H64 , all
the vertices in V (D1 ) will decode their requested messages from C1 and its side-information
that also includes {xi : i ∈ V (D3 )} (as there is a fully-participated D1 → D3 in D), (ii) if

f (D) ∈ {Hi0 : i0 ∈ {58, 59, 60, 61, 62, 64}}, all the vertices in V (D2 ) will decode their requested
messages from C1 ⊕ C2 and its side-information that also includes {xi : i ∈ V (D1 )} (as there is
a fully-participated D2 → D1 in D), and if f (D) = H63 , all the vertices in V (D2 ) will decode
their requested messages from C2 and its side-information that also includes {xi : i ∈ V (D3 )}

(as there is a fully-participated D2 → D3 in D), (iii) if f (D) ∈ {Hi0 : i0 ∈ {58, 59, 61, 63}},
all the vertices in V (D3 ) will decode their requested messages either from C1 and its sideinformation that also includes {xi : i ∈ V (D1 )} (as there is a fully-participated D3 → D1 in D),
and if f (D) ∈ {Hi0 : i0 ∈ {60, 62, 64}}, all the vertices in V (D3 ) will decode their requested

messages from C2 and its side-information that also includes {xi : i ∈ V (D2 )} (as there is a fully-

November 23, 2017

DRAFT

DRAFT

48

participated D3 → D2 in D). Thus (max{p(C(D1 )), p(C(D3 ))} + max{p(C(D1 )), p(C(D3 ))})-bit
(C1 , C2 ) is a valid index code in TSUIC for this case, and
βt (D, Go ) ≤ (max{p(C(D1 )), p(C(D3 ))} + max{p(C(D1 )), p(C(D3 ))})/t
≤ max{βt (D1 ), βt (D3 )} + max{βt (D2 ), βt (D3 )}.

(39)

Now if βt (D3 ) ≤ min{βt (D1 ), βt (D2 )}, from (39), we get βt (D, Go ) ≤ βt (D1 ) + βt (D2 ). From
Lemma 6, we have βt (D, Go ) ≥ βt (D1 ) + βt (D2 ). Thus βt (D, Go ) = βt (D1 ) + βt (D2 ) if
βt (D3 ) ≤ min{βt (D1 ), βt (D2 )}.

Now by taking a limit t → ∞ on both sides of (39), we get
lim βt (D, Go ) ≤ lim max{βt (D1 ), βt (D3 )} + lim max{βt (D2 ), βt (D3 )}

t→∞

t→∞

t→∞

β(D, Go ) ≤ max{β(D1 ), β(D3 )} + max{β(D2 ), β(D3 )}.

(40)

This is because β = lim βt (by Definition 3). Now from (40), we get β(D, Go ) ≤ β(D1 )+β(D2 )
t→∞

if β(D3 ) ≤ min{β(D1 ), β(D2 )}, and β(D, Go ) ≥ β(D1 )+β(D2 ) from Lemma 6. So, β(D, Go ) =
β(D1 ) + β(D2 ) if β(D3 ) ≤ min{β(D1 ), β(D2 )}.
R EFERENCES
[1] Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over broadcast channels,” in Proc. IEEE INFOCOM,
vol. 3, Mar. 1998, pp. 1257–1264.
[2] ——, “Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching
clients,” IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2825–2830, Jun. 2006.
[3] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with side information,” IEEE Trans. Inf. Theory, vol. 57,
no. 3, pp. 1479–1494, Mar. 2011.
[4] A. Blasiak, R. Kleinberg, and E. Lubetzky, “Broadcasting with side information: Bounding and approximating the broadcast
rate,” IEEE Trans. Inf. Theory, vol. 59, no. 9, pp. 5811–5823, Sept. 2013.
[5] S. E. Rouayheb, A. Sprintson, and C. Georghiades, “On the index coding problem and its relation to network coding and
matroid theory,” IEEE Trans. Inf. Theory, vol. 56, no. 7, pp. 3187–3195, Jul. 2010.
[6] H. Maleki, V. R. Cadambe, and S. A. Jafar, “Index coding – An interference alignment perspective,” IEEE Trans. Inf.
Theory, vol. 60, no. 9, pp. 5402–5432, Jul. 2014.
[7] F. Arbabjolfaei, B. Bandemer, Y.-H. Kim, E. Sasoglu, and L. Wang, “On the capacity region for index coding,” in Proc.
IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2013, pp. 962–966.
[8] F. Arbabjolfaei and Y.-H. Kim, “Structural properties of index coding capacity using fractional graph theory,” in Proc.
IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1034–1038.
[9] M. Tahmasbi, A. Shahrasbi, and A. Gohari, “Critical graphs in index coding,” IEEE J. Sel. Areas Commun., vol. 33, no. 2,
pp. 225–235, Feb. 2015.
[10] K. Shanmugam, A. G. Dimakis, and M. Langberg, “Local graph coloring and index coding,” in Proc. IEEE Int. Symp. Inf.
Theory (ISIT), Jul. 2013, pp. 1152–1156.

November 23, 2017

DRAFT

DRAFT

49

[11] L. Ong, “Optimal finite-length and asymptotic index codes for five or fewer receivers,” IEEE Trans. Inf. Theory, vol. 63,
no. 11, pp. 7116–7130, Nov. 2017.
[12] C. Thapa, L. Ong, and S. J. Johnson, “Interlinked cycles for index coding: Generalizing cycles and cliques,” IEEE Trans.
Inf. Theory, vol. 63, no. 6, pp. 3692–3711, Jun. 2017.
[13] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless content delivery
through distributed caching helpers,” IEEE Trans. Inf. Theory, vol. 59, no. 12, pp. 8402–8413, Dec. 2013.
[14] S. E. Rouayheb, A. Sprintson, and P. Sadeghi, “On coding for cooperative data exchange,” in Proc. IEEE Inf. Theory
Workshop (ITW), Jan. 2010, pp. 1–5.
[15] L. Ong, C. K. Ho, and F. Lim, “The single-uniprior index-coding problem: The single-sender case and the multi-sender
extension,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3165–3182, Jun. 2016.
[16] C. Thapa, L. Ong, and S. J. Johnson, “Graph-theoretic approaches to two-sender index coding,” in Proc. IEEE Globecom
Workshops, Dec. 2016, pp. 1–6.
[17] M. A. R. Chaudhry, Z. Asad, A. Sprintson, and M. Langberg, “On the complementary index coding problem,” in Proc.
IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2011, pp. 224–248.
[18] M. J. Neely, A. S. Tehrani, and Z. Zhang, “Dynamic index coding for wireless broadcast networks,” IEEE Trans. Inf.
Theory, vol. 59, no. 11, pp. 7525–7540, Nov. 2013.
[19] P. Sadeghi, F. Arbabjolfaei, and Y.-H. Kim, “Distributed index coding,” in Proc. IEEE Inf. Theory Workshop (ITW), Sept.
2016, pp. 330–334.
[20] Y. Liu, P. Sadeghi, F. Arbabjolfaei, and Y.-H. Kim, “On the capacity for distributed index coding,” in Proc. IEEE Int. Symp.
Inf. Theory (ISIT), Jun. 2017, pp. 3055–3059.
[21] M. Li, L. Ong, and S. J. Johnson, “Improved bounds for multi-sender index coding,” in Proc. IEEE Int. Symp. Inf. Theory
(ISIT), Jun. 2017, pp. 3060–3064.
[22] F. Arbabjolfaei, “Index coding: Fundamental limits, coding schemes, and structural properties,” Ph.D. dissertation, Dept. of
Elect. and Comput. Eng. (Commun. Theory and Systems), University of California, San Diego, CA, USA, 2017.
[23] N. Alon, A. Hassidim, E. Lubetzky, U. Stav, and A. Weinstein, “Broadcasting with side information,” in Proc. IEEE Symp.
on Found. of Comput. Sci., Oct. 2008, pp. 823–832.
[24] M. Fekete, “Uber die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten,”
Mathematische Zeitschrift, vol. 17, pp. 228–249, Dec. 1923.
[25] F. Arbabjolfaei and Y.-H. Kim, “On critical index coding problems,” in Proc. IEEE Inf. Theory Workshop (ITW), Oct. 2015,
pp. 9–13.

November 23, 2017

DRAFT

