# On the Solvability of $3$s$/n$t Sum-Network — A Region Decomposition and
Weak Decentralized Code Method

Wentu Song, Kai Cai, Chau Yuen, and Rongquan Feng Wentu Song and Chau Yuen are
with Singapore University of Technology and Design, Singapore (e-mails:
{wentu$\\_$song, yuenchau}@sutd.edu.sg).Kai Cai is with Department of
Mathematics, University of Hong Kong. (e-mail: kcai@hku.hk).Rongquan Feng is
with the LMAM, School of Mathematical Sciences, Peking University, China
(e-mail: fengrq@math.pku.edu.cn).

###### Abstract

We study the network coding problem of sum-networks with $3$ sources and $n$
terminals ($3$s$/n$t sum-network), for an arbitrary positive integer $n$, and
derive a sufficient and necessary condition for the solvability of a family of
so-called “terminal-separable” sum-network. Both the condition of “terminal-
separable” and the solvability of a terminal-separable sum-network can be
decided in polynomial time. Consequently, we give another necessary and
sufficient condition, which yields a faster $(O(|E|)$ time$)$ algorithm than
that of Shenvi and Dey $($[18], $(O(|E|^{3})$ time$)$, to determine the
solvability of the $3$s$/3$t sum-network.

To obtain the results, we further develop the region decomposition method in
[22, 23] and generalize the decentralized coding method in [21]. Our methods
provide new efficient tools for multiple source multiple sink network coding
problems.

###### Index Terms:

Function computation, linear network coding, sum-network, region
decomposition, decentralized code.

##  I Introduction

A $k$-source $n$-terminal ($k$s$/n$t) sum-network is modelled as a directed,
acyclic, finite graph $G$ with a set of $k$ vertices
$\\{s_{1},\cdots,s_{k}\\}$ called sources and a set of $n$ vertices
$\\{t_{1},\cdots,t_{n}\\}$ called terminals (sinks), such that each source
$s_{i}$ generates a message $X_{i}\in\mathbb{F}$ and each terminal wants to
obtain the sum $\sum_{i=1}^{k}X_{i}$ using linear network coding [1, 2], where
$\mathbb{F}$ is a finite field. The problem of communicating the sum over
networks is in fact a subclass of the problem of _distributed function
computation_ over networks, which has been explored in different contexts
[3]-[11], most are from information theoretic perspective and focus on small
or simple networks.

The study of network coding for sum-networks began with A. Ramamoorthy [12]
and was investigated from several aspects recently [12]-[20]. In [12], it was
shown that for a $k$s$/2$t or $2$s$/n$t sum-network with unit capacity edges
and independent, unit-entropy sources, it is solvable if and only if every
source-terminal pair is connected.

The main focus of the study on the sum-network is to determine the
solvability. One direction is to find out necessary and sufficient solvability
conditions for $k$s$/n$t sum-network of larger integers $k$ and $n$. In this
direction, successes to date are sporadic and the best known result is from
Shenvi and Dey [18], where the authors characterize the solvability of
$3$s$/3$t sum-networks using a collection of six “connection conditions”.
Another direction is to derive bounds on the capacity, or similarly —
sufficient or necessary conditions on the solvability of sum-network. In [17],
some upper and lower bounds on the capacity of sum-network are presented.
These bounds are observed to be loose for the case of $k>2$ and $n>3$. In
[19], the authors proved that the linear solvability of a sum-network is
equivalent to the linear solvability of some multiple-unicast network and vice
versa. They also proved that for any set of polynomials having integer
coefficients, there exists a sum-network that is scalar linear solvable over a
finite field $\mathbb{F}$ if and only if the polynomials have a common root in
$\mathbb{F}$. However, both the multiple-unicast network coding problem and
the problem of solving the common root of polynomials with integer
coefficients are NP-hard, which indicate that the $k$s$/n$t sum-network
problem for $k>2$ and $n>3$ is very challenging.

Like the other settings of multiple-source multiple-sink network coding
problem, loosely speaking, the difficulties of the sum-network problem lie in
two aspects: one is the topological structure of the underlying network, which
can be of arbitrary complex; the other is the distributed function computation
nature of the coding requirements. So what is of most importance than new
results, is to develop new methodologies to handle the difficulties mentioned
above, both for analyzing of network structure and for coding design.

The first methodology that we developed is focusing on the network structure.
The region decomposition method, which has been found efficient for analyzing
network structure and very successful in the 2-multicast networks [22] and
2-unicast networks with non-single rates [23], is further developed in this
paper. In [22], we proved that each directed, acyclic network $G$ has a unique
“basic region graph”, denote by $\text{RG}(D^{**})$, and the network coding
problem on $G$ can be converted to a coding problem on $\text{RG}(D^{**})$.
Generally, $\text{RG}(D^{**})$ could have a much more “simpler” topological
structure than $G$. In the present paper, we further develop this method and
decompose a network $G$ by two steps. In the first step, we perform basic
region decomposition and construct the basic region graph, just as in [22]. In
the second step, we further decompose the basic region graph into mutually
disjoint parts and consider the possibility of designing valid code in each
part separately. Most important, there is a special subgraph, denoted by
$\Pi$, such that to determine solvability of $G$, we only need to consider
code design problem on $\Pi$. Specifically, $G$ is solvable if and only if
there exists a code on $\Pi$ which satisfies some certain conditions. This
significantly simplifies the original problem of determining solvability.

Another methodology is the concept of “weak decentralized code” that
generalize the “decentralized code” in [21]. Rather than that in [21] where
the coding vectors of any two subtrees are linear independent, by weak
decentralized code, each “equivalent family of regions” is assigned the same
coding vector, and for any two regions, their coding vectors are linearly
independent if and only if they belong to different equivalent families.

Combining the developed region decomposition and weak decentralized code
methods, we give a sufficient and necessary condition for the solvability of a
class of $3$s$/n$t sum-network, termed _terminal-separable region graph_ , for
arbitrary $n\in\mathbb{Z}^{+}$. The condition can be verified in polynomial
time. Moreover, as two simple corollaries of our result, we prove that: (1) A
$3$s$/2$t sum-network is always solvable if each source-terminal pair is
connected; (2) A $3$s$/3$t sum-network is unsolvable if and only if the basic
region graph has some certain fixed structure.

Following the technical line of this paper, we can also completely
characterize the solvability of $3$s$/4$t sum-network. Limited by space of
this paper, we leave the results of $3$s$/4$t sum-network to a future paper.

This paper is organized as follows. In Section II, we introduce the network
coding model of sum-network. The method for region decomposition and for
decomposing the basic region graph is presented in Sections III and IV. The
method of weak decentralized code for $3$s$/n$t sum-network is presented in V.
We characterize solvability for terminal-separable $3$s$/n$t sum-network in
Section VI. Finally, the paper is concluded in Section VII.

Fig 1: Examples of region graph: (a) is a $3$s$/3$t sum-network $G_{1}$, where
all links are sequentially indexed as $1,2,\cdots,20$. Here, the imaginary
links $1,2,3$ are the $X_{1},X_{2},X_{3}$ source link, and $18,19,20$ are the
terminal links at terminal $t_{1},t_{2},t_{3}$ respectively. (b) is the region
graph $\text{RG}(D)$, where
$S_{1}=\\{1,4,5\\},S_{2}=\\{2,6,7\\},S_{3}=\\{3,8,9\\},R_{1}=\\{10,12,13\\},R_{2}=\\{11,14,15,16\\},R_{3}=\\{17\\},T_{1}=\\{18\\},T_{2}=\\{19\\},T_{3}=\\{20\\}$
and $D=\\{S_{1},S_{2},S_{3},R_{1},R_{2},R_{3},T_{1},T_{2},T_{3}\\}$. (c) is
the region graph $\text{RG}(D^{\prime})$, where
$S_{1}=\\{1,4,5\\},S_{2}=\\{2,6,7\\},S_{3}=\\{3,8,9\\},R_{1}^{\prime}=\\{10,12,13\\},R_{2}^{\prime}=\\{11,14,15,16\\},T_{1}=\\{18\\},T_{2}=\\{19\\},T_{3}=\\{17,20\\}$
and
$D^{\prime}=\\{S_{1},S_{2},S_{3},R_{1}^{\prime},R_{2}^{\prime},T_{1},T_{2},T_{3}\\}$.
In (c), although $R_{1}^{\prime}$ contains link $13$, which is an incoming
link of link $20\in T_{3}$, $R_{1}^{\prime}$ is not a parent of $T_{3}$. This
is because link $20$ is not the leader of $T_{3}$. (Note that
$\text{lead}(T_{3})$ is link $17$.)

##  II Models and Notations

In this paper, we always denote $[n]=\\{1,2,\cdots,n\\}$ for any positive
integer $n$.

A $k$-source $n$-terminal ($k$s$/n$t) sum-network is a directed, acyclic,
finite graph $G=(V,E)$, where $V$ is the node (vertex) set and $E$ is the link
(edge) set. There is a set of $k$ vertices
$\\{s_{1},s_{2},\cdots,s_{k}\\}\subseteq V$ called sources and a set of $n$
vertices $\\{t_{1},t_{2},\cdots,t_{n}\\}\subseteq V$ called terminals (sinks)
such that each source $s_{i}$ generates a message $X_{i}\in\mathbb{F}$ and
each terminal $t_{j}$ wants to get the sum $\sum_{i=1}^{k}X_{i}$ by linear
network coding, where $\mathbb{F}$ is a finite field. Generally, for the sake
of simplification, each link $e$ of $G$ is further assumed to be error-free,
delay-free and can carry one symbol in each use.

For any link $e=(u,v)\in E$, $u$ is called the _tail_ of $e$ and $v$ is called
the _head_ of $e$, and are denoted by $u=\text{tail}(e)$ and
$v=\text{head}(e)$, respectively. Moreover, we call $e$ an incoming link of
$v~{}($an outgoing link of $u)$. For two links $e,e^{\prime}\in E$, we call
$e^{\prime}$ an incoming link of $e$ ($e$ an outgoing link of $e^{\prime}$) if
$\text{tail}(e)=\text{head}(e^{\prime})$. For any $e\in E$, denoted by
$\text{In}(e)$ the set of incoming links of $e$.

To aid analysis, we assume that each source $s_{i}$ has an imaginary incoming
link, called $X_{i}$ source link $($or _source link_ for short$)$, and each
terminal $t_{j}$ has an imaginary outgoing link, called terminal link. Note
that the source links have no tail and the terminal links have no head. As a
result, the source links have no incoming link. For the sake of convenience,
if $e\in E$ is not a source link (resp. terminal link), we call $e$ a _non-
source link_ (resp. _non-terminal link_).

We assume that each non-source non-terminal link $e$ of $G$ is on a path from
some source to some terminal. Otherwise, $e$ has no impact on the network
coding of $G$ and can be removed from $G$.

Let $\mathbb{F}^{k}$ be the $k$-dimensional vector space over the finite field
$\mathbb{F}$. For any subset $A\subseteq\mathbb{F}^{k}$, let $\langle
A\rangle$ denote the subspace of $\mathbb{F}^{k}$ spanned by $A$. For
$i\in\\{1,\cdots,k\\}$, let $\alpha_{i}$ denote the vector of $\mathbb{F}^{k}$
with the $i$th component being one and all other components being zero.
Meanwhile, we denote

$\bar{\alpha}=\sum_{i=1}^{k}\alpha_{i}=(1,1,\cdots,1)$

i.e., the vector with all components being one.

For any linear network coding scheme, the message transmitted along any link
$e$ is a linear combination $M_{e}=\sum_{i=1}^{k}c_{i}X_{i}$ of the source
messages, where $c_{i}\in\mathbb{F}$. We use the vector of coefficients,
$d_{e}=(c_{1},\cdots,c_{k})$, to represent the message $M_{e}$ and call
$d_{e}$ the global encoding vector of $e$. To ensure the computability of
network coding, the outgoing message, as a $k$-dimensional vector, must be in
the span of all incoming messages. Moreover, to ensure that all terminals
receive the sum $\sum_{i=1}^{k}X_{i}$, if $e$ is a terminal link of the sum-
network, then $d_{e}=\sum_{i=1}^{k}\alpha_{i}=\bar{\alpha}$. Thus, we can
define a linear network code of a $k$s$/n$t sum-network as follows:

######  Definition II.1 (Linear Network Code)

A _linear network code_ (LC) of $G$ over a field $\mathbb{F}$ is a collection
of vectors $C=\\{d_{e}\in\mathbb{F}^{k};e\in E\\}$ such that

  * (1)

$d_{e}=\alpha_{i}$ if $e$ is the $X_{i}$ source link $(i=1,\cdots,k)$;

  * (2)

$d_{e}\in\langle d_{e^{\prime}};e^{\prime}\in\text{In}(e)\rangle$ if $e$ is a
non-source link.

The code $C=\\{d_{e}\in\mathbb{F}^{k};e\in E\\}$ is said to be a _linear
solution_ of $G$ if $d_{e}=\bar{\alpha}$ for all terminal link $e$.

The vector $d_{e}$ is called the global encoding vector of link $e$. The
network $G$ is said to be solvable if it has a linear solution over some
finite field $\mathbb{F}$. Otherwise, it is said unsolvable.

##  III Region Decomposition Approach for Network Coding

In this section, we present the region decomposition approach, which will take
a key role in our discussion. The basic concepts of region decomposition can
be seen in [22, 23]. For the sake of self-containment, we briefly repeat its
core in the following. It should be mentioned that the basic idea of region
decomposition is also rooted in [21].

###  III-A Region Decomposition and Region Graph

In the following, we consider $G=(V,E)$ as a $k$s$/n$t sum-network.

######  Definition III.1 (Region Decomposition)

Let $R$ be a non-empty subset of $E$. $R$ is called a region of $G$ if there
is an $e_{l}\in R$ such that for any $e\in R\backslash\\{e_{l}\\}$, $R$
contains an incoming link of $e$. If $E$ is partitioned into mutually disjoint
regions, say $R_{1},R_{2},\cdots,R_{N}$, then we call
$D=\\{R_{1},R_{2},\cdots,R_{N}\\}$ a region decomposition of $G$.

The edge $e_{l}$ in Definition III.1 is called the _leader_ of $R$ and is
denoted as $e_{l}=\text{lead}(R)$. A region $R$ is called the $X_{i}$ _source
region_ (or a _source region_ for short) if $\text{lead}(R)$ is the $X_{i}$
source link; $R$ is called a _terminal region_ if $R$ contains a terminal
link. If $R$ is neither a source region nor a terminal region, then $R$ is
called a coding region. If $R$ is not a source region, we call $R$ a _non-
source region_.

Consider the network $G_{1}$ in Fig. 1 (a). We can easily check that the
subsets of links $R=\\{3,8,9,11,16,17\\}$ and $R^{\prime}=\\{5,10,12,13,19\\}$
are two regions of $G_{1}$ with $\text{lead}(R)=3$ and
$\text{lead}(R^{\prime})=5$. However, $\\{5,6,10,12,13\\}$ is not a region
because it does not contain any incoming link of link $5$ and $6$. Similarly,
the subset $\\{10,11,12,13,14\\}$ is not a region.

###### Remark III.2

Since the source links have no incoming link, then each source region contains
exactly one source link, i.e., its leader. But a terminal region may contains
more than one terminal links. So there are exactly $k$ source region and at
most $n$ terminal regions for any $k$s$/n$t sum-network. Without loss of
generality, we can assume $G$ has exactly $n$ terminal regions.

Convention: In this work, we will always denote the $k$ different source
regions as $S_{1},\cdots,S_{k}$ and the $n$ terminal regions as
$T_{1},\cdots,T_{n}$.

######  Definition III.3 (Region Graph)

Let $D$ be a region decomposition of $G$. The region graph of $G$ about $D$ is
a directed, simple graph with vertex set $D$ and edge set $\mathcal{E}_{D}$,
where $\mathcal{E}_{D}$ is the set of all ordered pairs $(R^{\prime},R)$ such
that $R^{\prime}$ contains an incoming link of $\text{lead}(R)$.

Examples of region graph are given in Fig. 1 (b) and (c). In general, a
network may have many region decompositions, hence has many region graphs.

We use $\text{RG}(D)$ to denote the region graph of $G$ about $D$, i.e.,
$\text{RG}(D)=(D,\mathcal{E}_{D})$. If $(R^{\prime},R)$ is an edge of
$\text{RG}(D)$, we call $R^{\prime}$ a _parent_ of $R~{}(R$ a _child_ of
$R^{\prime})$. For $R\in D$, we use $\text{In}(R)$ to denote the set of
parents of $R$ in $\text{RG}(D)$.

###### Remark III.4

Note that the leader of each source region is the corresponding source link
and the source links have no incoming link. So the source regions have no
parent. Moreover, since $G$ is acyclic, then clearly, $\text{RG}(D)$ is
acyclic.

For $R,R^{\prime}\in D$, a path in $\text{RG}(D)$ from $R^{\prime}$ to $R$ is
a sequence of regions $\\{R_{0}=R^{\prime},R_{1},\cdots,R_{K}=R\\}$ such that
$R_{i-1}$ is a parent of $R_{i}$ for each $i\in\\{1,\cdots,K\\}$. If there is
a path from $R^{\prime}$ to $R$, we say $R^{\prime}$ is connected to $R$ and
denote $R^{\prime}\rightarrow R$. Else, we say $R^{\prime}$ is not connected
to $R$ and denote $R^{\prime}\nrightarrow R$. In particular, we have
$R\rightarrow R$ for all $R\in D$.

######  Definition III.5 (Codes on Region Graph)

A _linear code_ (LC) of the region graph $\text{RG}(D)$ over the field
$\mathbb{F}$ is a collection of vectors
$\tilde{C}=\\{d_{R}\in\mathbb{F}^{k};R\in D\\}$ such that

  * (1)

$d_{S_{i}}=\alpha_{i}$ for each $i\in\\{1,\cdots,k\\}$, where $S_{i}$ is the
$X_{i}$ source region;

  * (2)

$d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ if $R$ is a
non-source region.

The code $\tilde{C}$ is said to be a _linear solution_ of $\text{RG}(D)$ if
$d_{T_{j}}=\bar{\alpha}$ for each terminal region $T_{j}$. $\text{RG}(D)$ is
said to be feasible if it has a linear solution over some finite field
$\mathbb{F}$. Otherwise, it is said infeasible.

The vector $d_{R}$ is called the global encoding vector of $R$. By Definition
III.5, for any linear solution of $\text{RG}(D)$, it always be that
$d_{S_{i}}=\alpha_{i}$ and $d_{T_{j}}=\bar{\alpha}$. So in order to obtain a
solution of $\text{RG}(D)$, we only need to specify the global encoding vector
$d_{R}$ for each coding region $R\in D$.

Any linear solution of $\text{RG}(D)$ can be extended to a linear solution of
$G$. In fact, we have the following lemma.

###### Lemma III.6

Let $D$ be a region decomposition of $G$ and
$\tilde{C}=\\{d_{R}\in\mathbb{F}^{3};R\in D\\}$ be a linear solution of
$\text{RG}(D)$. Let $d_{e}=d_{R}$ for each $R\in D$ and each $e\in R$. Then
$C=\\{d_{e};e\in E\\}$ is a linear solution of $G$.

###### proof III.7

For each link $e\in E$, by Definition III.1, there is a unique $R\in D$ such
that $e\in R$. So $C$ is well defined. By Definition III.5, we have
$d_{e}=\alpha_{i}$ for each $X_{i}$ source link $e$ and $d_{e}=\bar{\alpha}$
for each terminal link $e$. Moreover, suppose $e\in E$ is a non-source link.
By the same discussion as in the proof of Lemma 3.11 of [22], we can prove
that $d_{e}\in\langle d_{e^{\prime}};e^{\prime}\in\text{In}(e)\rangle$. Thus,
$C$ is a linear solution of $G$.

By Lemma III.6, if $D$ is a region decomposition of $G$ and $\text{RG}(D)$ is
feasible, then $G$ is solvable. But conversely, if $G$ is solvable, it is not
necessary that $\text{RG}(D)$ is feasible.

For the region graph $\text{RG}(D)$ in Fig. 1 (b), let $d_{R_{1}}=\alpha_{1}$
and $d_{R_{2}}=d_{R_{3}}=\alpha_{2}+\alpha_{3}$. Then $\tilde{C}=\\{d_{R};R\in
D\\}$ is a linear solution of $\text{RG}(D)$ and we can obtain a linear
solution of $G_{1}$ by Lemma III.6. However, the region graph
$\text{RG}(D^{\prime})$ in Fig. 1 (c) is not feasible because for any linear
code, by condition (2) of Definition III.5, we have $d_{T_{3}}\in\langle
d_{R_{2}^{\prime}},d_{S_{3}}\rangle$ and $d_{R_{2}^{\prime}}\in\langle
d_{S_{2}},d_{S_{3}}\rangle$, which implies that
$\alpha_{1}+\alpha_{2}+\alpha_{3}=\bar{\alpha}=d_{T_{3}}\in\langle
d_{S_{2}},d_{S_{3}}\rangle=\langle\alpha_{2},\alpha_{3}\rangle$, a
contradiction.

###  III-B Basic Region Graph

In this subsection, we shall define a special region decomposition $D^{**}$ of
$G$, called the basic region decomposition of $G$, which is unique and has the
property that $G$ is solvable if and only if the region graph
$\text{RG}(D^{**})$ is feasible.

######  Definition III.8 (Basic Region Decomposition)

Let $D^{**}$ be a region decomposition of $G$. $D^{**}$ is called a basic
region decomposition of $G$ if the following conditions hold:

  * (1)

For any $R\in D^{**}$ and any $e\in R\setminus\\{\text{lead}(R)\\}$,
$\text{In}(e)\subseteq R$;

  * (2)

Each non-source region $R$ in $D^{**}$ has at least two parents in
$\text{RG}(D^{**})$.

Accordingly, the region graph $\text{RG}(D^{**})$ is called a basic region
graph of $G$.

For example, one can check that for the network $G_{1}$ in Fig. 1 (a), the
region graph $\text{RG}(D)$ in Fig. 1 (b) is a basic region graph of $G_{1}$.
However, the region graph $\text{RG}(D^{\prime})$ Fig. 1 (c) is not a basic
region graph of $G_{1}$ because $D^{\prime}$ does not satisfies condition (1)
of Definition III.8. In fact, for the link $20\in T_{3}\in D^{\prime}$,
$20\neq\text{lead}(T_{3})=17$ and $\text{In}(20)=\\{13,17\\}\nsubseteq T_{3}$.

It is known that for networks with two unit-rate multicast sessions, the basic
region decomposition is unique [22, Th. 4.4] and can be obtained in time
$O(|E|)$ [22, Algorithm 5]. Note that the notions of basic region
decomposition and basic region graph only depend on the topology of $G$ and
have no relation with the specific demand of sinks. Hence Algorithm 5 and
Theorem 4.4 of [22] can be directly generalized to arbitrary directed acyclic
networks with $k$ sources and $n$ sinks (terminals), including multicast
networks and sum-networks. We list these results for sum-network as the
following theorem.

###### Theorem III.9

The $k$s$/n$t sum-network $G$ has a unique basic region decomposition, hence
has a unique basic region graph. Moreover, the basic region decomposition and
the basic region graph can be obtained in time $O(|E|)$.

Convention: In the following, we will always use $D^{**}$ and
$\text{RG}(D^{**})$ to denote the basic region decomposition and basic region
graph of $G$.

Corresponding to Theorem 4.5 of [22], we have the following theorem for sum-
network.

###### Theorem III.10

$G$ is solvable if and only if $\text{RG}(D^{**})$ is feasible, where $D^{**}$
is the basic region decomposition of $G$.

###### proof III.11

Suppose $\text{RG}(D^{**})$ is feasible and $\tilde{C}$ is a linear solution
of $\text{RG}(D^{**})$. By Lemma III.6, we can obtain a linear solution $C$ of
$G$. So $G$ is solvable.

Conversely, suppose $G$ is solvable and $C=\\{d_{e}\in\mathbb{F}^{k};e\in
E\\}$ is a linear solution of $G$. Without loss of generality, we can assume
that $d_{e}\neq 0$ for all $e\in E$. By condition (2) of Definition II.1 and
condition (1) of Definition III.8, we can easily see that for any $R\in
D^{**}$ and any $e\in R$, $d_{e}\in\langle d_{\text{lead}(R)}\rangle$. So we
can further assume that $d_{e}=d_{\text{lead}(R)}$. For each $R\in D^{**}$,
let $d_{R}=d_{\text{lead}(R)}$. Then by Definition III.3 and III.5, we can
check that $\tilde{C}=\\{d_{R};R\in D^{**}\\}$ is a linear solution of
$\text{RG}(D^{**})$. So $\text{RG}(D^{**})$ is feasible.

Fig 2: Two examples of unsolvable $3$s$/3$t sum-network, where
$s_{1},s_{2},s_{3}$ are three sources and $t_{1},t_{2},t_{3}$ are three
terminals. The imaginary links $1,2,3$ are the $X_{1},X_{2},X_{3}$ source
link, and the imaginary links $4,5,6$ are the terminal links at terminal
$t_{1},t_{2},t_{3}$ respectively.

Fig 3: The corresponding basic region graph of the networks in Fig. 2.

###### Example III.12

We consider two examples of sum-network in Fig. 2, which can also be found in
[18].

In Fig. 2 (a), let $S_{1}=\\{1,(s_{1},v_{1}),(s_{1},t_{2})\\}$, $S_{2}=\\{2$,
$(s_{2},v_{2}),(s_{2},t_{1})\\}$, $S_{3}=\\{3,(s_{3},v_{1}),(s_{3},v_{2})\\}$,
$P_{1}=\\{(v_{2},v_{4})$, $(v_{4},t_{3}),(v_{4},t_{2})\\}$,
$P_{2}=\\{(v_{1},v_{3}),(v_{3},t_{1}),(v_{3},t_{3})\\}$, $T_{1}=\\{4\\}$,
$T_{2}=\\{5\\}$ and $T_{3}=\\{6\\}$. Then $D^{**}=\\{S_{1},S_{2},S_{3},P_{1}$,
$P_{2},T_{1},T_{2},T_{3}\\}$ is its basic region decomposition. The basic
region graph is shown in Fig. 3 (a). If $C=\\{d_{e}\in\mathbb{F}^{3};e\in
E\\}$ is a linear solution of $G$, the global encoding vector of all links in
the same region must be the same. For example,
$d_{(s_{1},v_{1})}=d_{(s_{1},t_{2})}=d_{1}$,
$d_{(v_{3},t_{1})}=d_{(v_{3},t_{3})}=d_{(v_{1},v_{3})}$, etc. So we can view
each region as a node and consider coding on the basic region graph
$\text{RG}(D^{**})$. We will show in Section VI. C that $\text{RG}(D^{**})$ is
infeasible. So the original network is unsolvable.

In Fig. 2 (b), let $S_{1}=\\{1,(s_{1},v_{1}),(s_{1},v_{2}),(s_{1},t_{1})$,
$(s_{1},t_{2})\\}$, $S_{2}=\\{2,(s_{2},v_{2}),(s_{2},v_{3})\\}$,
$S_{3}=\\{3,(s_{3},v_{1})$, $(s_{3},v_{3})\\}$,
$P_{1}=\\{(v_{3},v_{5}),(v_{5},t_{3})$, $(v_{5},t_{2})\\}$,
$P_{2}=\\{(v_{1},v_{4})$, $(v_{4},t_{1}),(v_{4},t_{3})\\}$,
$P_{3}=\\{(v_{2},t_{1})\\}$, $T_{1}=\\{4\\}$, $T_{2}=\\{5\\}$ and
$T_{3}=\\{6\\}$. Then
$D^{**}=\\{S_{1},S_{2},S_{3},P_{1},P_{2},P_{3},T_{1},T_{2},T_{3}\\}$ is its
basic region decomposition. The basic region graph is shown in Fig. 3 (b). We
will also show in Section VI. C that its basic region graph is infeasible. So
this network is unsolvable.

###### Lemma III.13

Suppose $\Theta\subseteq D^{**}$ and for each $j\in[n]$, there is a
$Q\in\Theta$ such that $Q\rightarrow T_{j}$. If the sum of source messages
$\sum_{i=1}^{k}X_{i}$ can be transmitted from $\\{S_{1},\cdots,S_{k}\\}$ to
all $Q\in\Theta$ simultaneously, then $\text{RG}(D^{**})$ is feasible.

This lemma is obvious because if a region can receive the sum, then all its
down-link regions can receive the sum.

###### Example III.14

Consider the region graph $\text{RG}(D^{**})$ in Fig. 4 (a). Let
$\Theta=\\{Q,T_{1}\\}$. Then the sum $X_{1}+X_{2}+X_{3}$ can be transmitted
from $\\{S_{1},S_{2},S_{3}\\}$ to $\\{Q,T_{1}\\}$ by letting
$d_{R_{1}}=d_{R_{2}}=\alpha_{1},d_{R_{3}}=\alpha_{2}+\alpha_{3}$ and
$d_{Q}=\alpha_{1}+\alpha_{2}+\alpha_{3}$. Moreover, by letting
$d_{T_{2}}=d_{T_{3}}=\alpha_{1}+\alpha_{2}+\alpha_{3}$, we can obtain a linear
solution of $\text{RG}(D^{**})$. We remind the reader that for $k=3$, the
vectors $\alpha_{1}=(1,0,0),\alpha_{2}=(0,1,0),\alpha_{3}=(0,0,1)$ are the
global encoding vectors of the source messages $X_{1},X_{2},X_{3}$
respectively, and $\bar{\alpha}=\alpha_{1}+\alpha_{2}+\alpha_{3}=(1,1,1)$ is
the global encoding vector of the sum $\sum_{i=1}^{3}X_{i}$.

Fig 4: Two examples of region graph.

If $T_{j}\rightarrow T_{j^{\prime}}$ for some
$\\{j,j^{\prime}\\}\subseteq[n]$, then we can reduce the number of terminal
regions. In fact, without loss of generality, assume $T_{j}\rightarrow T_{n}$
for some $j\in\\{1,\cdots,n-1\\}$. Let
$\Theta=\\{T_{1},T_{2},\cdots,T_{n-1}\\}$. If $\text{RG}(D^{**})$ is feasible,
then naturally, the sum $\sum_{i=1}^{k}X_{i}$ can be transmitted to all
$T_{j}\in\Theta$. Conversely, if the sum can be transmitted to all
$T_{j}\in\Theta$, then by Lemma III.13, $\text{RG}(D^{**})$ is feasible. So we
can reduce the number of terminal regions to $n-1$. For this reason, we can
assume that $T_{j}\nrightarrow T_{j^{\prime}}$ for all pair
$\\{j,j^{\prime}\\}\subseteq[n]$.

Since each non-source non-terminal link $e$ of $G$ is on a path from some
source to some terminal, then by Definition III.1 and III.3, each region $R\in
D^{**}$ is on a path from some source region to some terminal region in
$\text{RG}(D^{**})$. Moreover, each terminal region $T_{j}$ has no child.
Otherwise, since $\text{RG}(D^{**})$ is acyclic, then by tracing child from
$T_{j}$, we can always find a path from $T_{j}$ to some other terminal region
$T_{j^{\prime}}$, which contradicts to the assumption that $T_{j}\nrightarrow
T_{j^{\prime}}$ for all $\\{j,j^{\prime}\\}\subseteq[n]$. Thus, the following
assumption is reasonable.

Assumption 1: The terminal regions have no child and for each region $R\in
D^{**}$, $R\rightarrow T_{j}$ for some terminal region $T_{j}$.

###  III-C Super Region

As in [23], we can define super region of $G$ for the region graph
$\text{RG}(D^{**})$.

######  Definition III.15 (Super Region [23])

Suppose $\emptyset\neq\Theta\subseteq D^{**}$. The super region generated by
$\Theta$, denoted by $\text{reg}(\Theta)$, is a subset of $D^{**}$ which is
defined recursively as follows:

  * (1)

If $R\in\Theta$, then $R\in\text{reg}(\Theta)$;

  * (2)

If $R\in D^{**}$ and $\text{In}(R)\subseteq\text{reg}(\Theta)$, then
$R\in\text{reg}(\Theta)$.

We define $\text{reg}^{\circ}(\Theta)=\text{reg}(\Theta)\setminus\Theta$.
Moreover, if the subset $\Theta=\\{R_{1},\cdots,R_{k}\\}$, then we denote
$\text{reg}(\Theta)=\text{reg}(R_{1},\cdots,R_{k})$.

Consider the region graph in Fig. 4 (a). We can find the super region
$\text{reg}(R_{2},R_{3},R_{4})$ as follows. First, we list all regions in a
way that each region is before all of its children. For example,
$\\{S_{1},S_{2},S_{3},R_{1},R_{2},R_{3},R_{4},Q,T_{1},T_{2},T_{3}\\}$. Then we
can check all regions one by one to obtain $\text{reg}(R_{2},R_{3},R_{4})$. In
fact, by Definition III.15, we have
$S_{1},S_{2},S_{3},R_{1}\notin\text{reg}(R_{2},R_{3},R_{4})$ and
$R_{2},R_{3},R_{4}\in\text{reg}(R_{2},R_{3},R_{4}).$ Note that
$\text{In}(Q)=\\{R_{2},R_{3}\\}\subseteq\text{reg}(R_{2},R_{3},R_{4})$. Then
by (2) of Definition III.15, we have $Q\in\text{reg}(R_{2},R_{3},R_{4}).$
Since $T_{1}$ has a parent $R_{1}\notin\text{reg}(R_{2},R_{3},R_{4})$, then by
Definition III.15, $T_{1}\notin\text{reg}(R_{2},R_{3},R_{4}).$ Similarly,
$\\{T_{2},T_{3}\\}\subseteq\text{reg}(R_{2},R_{3},R_{4}).$ Thus, we have
$\text{reg}(R_{2},R_{3},R_{4})=\\{R_{2},R_{3},R_{4},Q,T_{2},T_{3}\\}$.

Consider the region graph in Fig. 4 (b). By a similar discussion, we can check
that $\text{reg}(R_{2},R_{4})=\\{R_{2},R_{4},Q_{1},Q_{3},T_{2}\\}$ and
$\text{reg}(R_{2},R_{3},R_{5})=\\{R_{2},R_{3},R_{5},Q_{2},Q_{4},T_{3}\\}$.

In general, since $\text{RG}(D^{**})$ is acyclic, regions in $D^{**}$ can be
sequentially indexed as $D^{**}=\\{R_{1},R_{2},R_{3},\cdots,R_{N}\\}$ such
that $R_{i}=S_{i}$ for $i\in\\{1,2,3\\}$ and $\ell<\ell^{\prime}$ if
$R_{\ell}$ is a parent of $R_{\ell^{\prime}}$. By Definition III.15, it is
easy to see that the following Algorithm 1 output the super region
$\text{reg}(\Theta)$ in time $O(|D^{**}|)$.

Algorithm 1: Super-Region
$(\text{RG}(D^{**}),\Theta)$:$\mathcal{R}=\Theta$;$\ell\leftarrow$from $1$ to
$N$If$\text{In}(R)\subseteq\text{reg}(\Theta)$then$\mathcal{R}=\mathcal{R}\cup\\{R_{\ell}\\}$;Return$\text{reg}(\Theta)=\mathcal{R}$;

###### Remark III.16

From condition (2) of Definition III.5 and III.15, we can easily prove, using
induction, that if $\tilde{C}=\\{d_{R}\in\mathbb{F}^{k};R\in D^{**}\\}$ is a
linear code of $\text{RG}(D^{**})$ and $\emptyset\neq\Theta\subseteq D^{**}$,
then $d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\Theta\rangle$ for all
$R\in\text{reg}(\Theta)$.

Also by Definition III.15, it is easy to see that for any subsets
$\Theta_{1},\Theta_{2}$ of $D^{**}$, if
$\Theta_{1}\subseteq\text{reg}(\Theta_{2})$, then
$\text{reg}(\Theta_{1})\subseteq\text{reg}(\Theta_{2})$. In this paper, we
will always hold this fact as self-evident.

The following two lemmas are some other properties of super region.

###### Lemma III.17

Suppose $\Theta_{1}$ and $\Theta_{2}$ are two subsets of $D^{**}$. Then
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})=\text{reg}(\Theta)$, where

$\displaystyle\Theta=(\text{reg}(\Theta_{1})\cap\Theta_{2})\cup(\text{reg}(\Theta_{2})\cap\Theta_{1}).$
(III.1)

###### proof III.18

By (III.1), $\Theta\subseteq\text{reg}(\Theta_{1})$ and
$\Theta\subseteq\text{reg}(\Theta_{2})$. So by Definition III.15,
$\text{reg}(\Theta)\subseteq\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})$.

We still need to prove that
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\subseteq\text{reg}(\Theta)$.
Since $\text{RG}(D^{**})$ is acyclic, then regions in
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})$ can be sequentially indexed
as $\\{R_{1},R_{2},\cdots,R_{N}\\}$ such that $\ell<\ell^{\prime}$ if
$R_{\ell}$ is a parent of $R_{\ell^{\prime}}$. For each $R_{i}$, if
$R_{i}\notin\Theta$, then by (III.1), $R_{i}\notin\Theta_{1}\cup\Theta_{2}$.
So $R_{i}\in\text{reg}^{\circ}(\Theta_{1})\cap\text{reg}^{\circ}(\Theta_{2})$,
and by Definition III.15,
$\text{In}(R_{i})\subseteq\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})$,
which implies that $\text{In}(R_{i})\subseteq\\{R_{1},\cdots,R_{i-1}\\}$.
Thus, $R_{1}\in\Theta\subseteq\text{reg}(\Theta)$ and by Definition III.15,
$R_{i}\in\text{reg}(\Theta)$ for $i\in\\{2,\cdots,N\\}$. So we have
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\subseteq\text{reg}^{\circ}(\Theta)$.

By above discussion,
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})=\text{reg}(\Theta)$.

For any $\\{Q_{1},\cdots,Q_{\ell},Q\\}\subseteq D$, if each $Q_{i}$ has a
message $Y_{i}\in\mathbb{F}$ and $Q_{i}\rightarrow Q$, then any linear
combination $\sum_{i=1}^{\ell}\lambda_{i}Y_{i}$ can be transmitted to $Q$ by a
linear network code. Formally, we have the following lemma.

###### Lemma III.19

Suppose $\Lambda=\\{Q_{1},\cdots,Q_{\ell}\\}\subseteq D^{**}$ and $Q\in
D^{**}\backslash\Lambda$ such that for each $Q_{i}\in\Lambda$, there is a path
$\mathcal{P}_{i}$ from $Q_{i}$ to $Q$. Let $\Omega\subseteq D^{**}$ be such
that $\mathcal{P}_{i}\backslash\Lambda\subseteq\Omega,\forall
i\in\\{1,\cdots,\ell\\}$. Then for any
$\\{d_{Q_{1}},\cdots,d_{Q_{\ell}}\\}\subseteq\mathbb{F}^{k}$ and any
$d_{0}\in\langle d_{Q_{1}},\cdots,d_{Q_{\ell}}\rangle$, there is a code
$\tilde{C}_{\Omega}=\\{d_{R}\in\mathbb{F}^{k};R\in\Omega\\}$ such that
$d_{Q}=d_{0}$ and $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all $R\in\Omega$.

This lemma is obvious and we omit its proof.

###  III-D Weak Decentralized Code On Super Region

For any set $A$, a collection $\mathcal{I}=\\{\Delta_{1},\cdots,\Delta_{K}\\}$
of subsets of $A$ is called a partition of $A$ if
$\Delta_{1},\cdots,\Delta_{K}$ are mutually disjoint and
$\bigcup_{i=1}^{K}\Delta_{i}=A$. Each subset $\Delta_{i}$ is called an
_equivalent class_ of $A$. If $a\in\Delta_{i}$, we denote $\Delta_{i}=[a]$.
Thus, for each $\Delta_{i}$, we can pick an arbitrary $a_{i}\in\Delta_{i}$ and
denote
$\mathcal{I}=\\{\Delta_{1},\cdots,\Delta_{K}\\}=\\{[a_{1}],\cdots,[a_{K}]\\}$.
The element $a_{i}$ is called a representative element of $\Delta_{i}$. Note
that if $a_{i},b_{i}\in\Delta_{i}$, then we have $\Delta_{i}=[a_{i}]=[b_{i}]$.

For any subset $\Omega\subseteq D^{**}$ and any collection
$\tilde{C}_{\Omega}=\\{d_{R}\in\mathbb{F}^{k};R\in\Omega\\}$, we call
$\tilde{C}_{\Omega}$ a code on $\Omega$. In the following, we give an approach
to construct a code on a super region. Such a code has some interesting
property and is the basis of our code construction for three-source sum-
network.

###### Definition III.20

Suppose $\\{Q_{1},Q_{2}\\}\subseteq D^{**}$. A partition
$\mathcal{I}=\\{\Delta_{1},\Delta_{2},\cdots,\Delta_{K}\\}$ of
$\text{reg}(Q_{1},Q_{2})$ is said to be R-_closed_ if $K\geq 2$ and
$\text{reg}(\Delta_{j})=\Delta_{j}$ for all $j\in\\{1,\cdots,K\\}$.

In Definition III.20, it must be that $Q_{1},Q_{2}$ belongs to different
equivalent classes. This is because if $Q_{1},Q_{2}\in\Delta_{i}$, then
$\text{reg}(Q_{1},Q_{2})\subseteq\text{reg}(\Delta_{i})=\Delta_{i}$ and we
have $K=1$, which contradicts to the condition that $K\geq 2$. Thus, by proper
naming, we can always assume that $Q_{1}\in\Delta_{1}$ and
$Q_{2}\in\Delta_{2}$.

######  Definition III.21 (Weak Decentralized Code on
$\text{reg}(Q_{1},Q_{2})$)

Suppose $\mathcal{I}=\\{\Delta_{1},\Delta_{2},\cdots,\Delta_{K}\\}$ is an
R-closed partition of $\text{reg}(Q_{1},Q_{2})$ and
$d_{1},d_{2},\cdots,d_{K}\in\mathbb{F}^{k}$ are mutually linearly independent
such that $d_{j}\in\langle d_{1},d_{2}\rangle$ for all $j\geq 3$. For each
$j\in\\{1,2,\cdots,K\\}$ and $R\in\Delta_{j}$, let $d_{R}=d_{j}$. The code
$\tilde{C}_{Q_{1},Q_{2}}=\\{d_{R};R\in\text{reg}(Q_{1},Q_{2})\\}$ is called an
$\mathcal{I}$-_weak decentralized code_ on $\text{reg}(Q_{1},Q_{2})$.

As a simple result of linear algebra, if $|\mathbb{F}|\geq K-1$, then we can
always find a set of vectors
$\\{d_{1},d_{2},\cdots,d_{K}\\}\subseteq\mathbb{F}^{k}$ satisfying the
condition of Definition III.21. Thus, if $|\mathbb{F}|\geq K-1$, then we can
always construct an $\mathcal{I}$-weak decentralized code on
$\text{reg}(Q_{1},Q_{2})$.

Fig 5: An example of weak decentralized code: (a) depicts a super region
$\text{reg}(Q_{1},Q_{2})$ and (b) depicts a weak decentralized code on
$\text{reg}(Q_{1},Q_{2})$. In (a), let
$\Delta_{1}=\\{Q_{1},Q_{7},Q_{10}\\},\Delta_{2}=\\{Q_{2},Q_{5}\\},\Delta_{3}=\\{Q_{3},Q_{9},Q_{11}\\}$
and $\Delta_{4}=\\{Q_{4},Q_{6},Q_{8}\\}$. Then
$\text{reg}(\Delta_{j})=\Delta_{j}$ for all $j\in\\{1,2,3,4\\}$. Let
$d_{1},d_{2},d_{3},d_{4}\in\mathbb{F}^{k}$ be mutually linearly independent
and $d_{3},d_{4}\in\langle d_{1},d_{2}\rangle$. Then the code illustrated in
Fig. 5 (b) is a decentralized code on $\text{reg}(Q_{1},Q_{2})$.

An example of weak decentralized code is given in Fig. 5. Moreover, weak
decentralized code has the following property.

###### Lemma III.22

Let $\tilde{C}_{Q_{1},Q_{2}}$ be as in Definition III.21. Then
$d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all
$R\in\text{reg}^{\circ}(Q_{1},Q_{2})$.

###### proof III.23

Suppose $R\in\text{reg}^{\circ}(Q_{1},Q_{2})$. Then by Definition III.15,
$\text{In}(R)\subseteq\text{reg}(Q_{1},Q_{2})$. We have the following two
cases:

Case 1: $\text{In}(R)\subseteq\Delta_{j}$ for some $j\in\\{1,2,\cdots,K\\}$.
Then by Definition III.15 and III.21, we have
$R\in\text{reg}(\Delta_{j})=\Delta_{j}$. Again by Definition III.21, we have
$d_{R}=d_{R^{\prime}}=d_{j}$ for all $R^{\prime}\in\text{In}(R)$. So
$d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$.

Case 2: $\text{In}(R)\nsubseteq\Delta_{j}$ for all $j\in\\{1,2,\cdots,K\\}$.
Since $R$ has at least two parents (Definition III.8), then we can assume
$R^{\prime}_{1}\in\text{In}(R)\cap\Delta_{\ell_{1}}$ and
$R^{\prime}_{2}\in\text{In}(R)\cap\Delta_{\ell_{2}}$ for some
$\\{\ell_{1},\ell_{2}\\}\subseteq\\{1,2,\cdots,K\\}$. By Definition III.21,
$d_{R^{\prime}_{1}}=d_{\ell_{1}}$, $d_{R^{\prime}_{2}}=d_{\ell_{2}}$ and
$d_{R}=d_{\ell}$ for some $\ell\in\\{1,2,\cdots,K\\}$. Also by Definition
III.21, $d_{\ell},d_{\ell_{1}},d_{\ell_{2}}\in\langle d_{1},d_{2}\rangle$ and
$d_{\ell_{1}},d_{\ell_{2}}$ are linearly independent. So $d_{R}\in\langle
d_{1},d_{2}\rangle=\langle d_{\ell_{1}},d_{\ell_{2}}\rangle=\langle
d_{R^{\prime}_{1}},d_{R^{\prime}_{2}}\rangle\subseteq\text{In}(R)\rangle$.

A special case of weak decentralized code is that each $\Delta_{j}$ contains a
single element, i.e., $\text{reg}(Q_{1},Q_{2})=\\{Q_{1}$,
$Q_{2},\cdots,Q_{K}\\}$ and $\Delta_{j}=\\{Q_{j}\\},\forall
j\in\\{1,2,\cdots,K\\}$. In this case, $d_{R}$ and $d_{R^{\prime}}$ are
linearly independent for all
$\\{R,R^{\prime}\\}\subseteq\text{reg}(Q_{1},Q_{2})$. Such code is called
decentralized code [21].

##  IV Decomposition of the Basic Region Graph

Throughout this section, we assume $G$ is a $3$s$/n$t sum-network. By Theorem
III.10, $G$ is solvable if and only if the the basic region graph
$\text{RG}(D^{**})$ is feasible. Thus, to study the network coding problem of
$G$, it is sufficient to consider coding on $\text{RG}(D^{**})$. By Remark
III.2, $\text{RG}(D^{**})$ has exactly three source regions and at most $n$
terminal regions. Without loss of generality, we assume $\text{RG}(D^{**})$
has exactly $n$ terminal regions. Recall that $S_{i}~{}(i\in\\{1,2,3\\})$
denote the $X_{i}$ source region and $\\{T_{j};j\in[n]\\}$ denote the set of
$n$ terminal regions.

For each $i\in\\{1,2,3\\}$, by Lemma III.17, we have

$\displaystyle\text{reg}(S_{i},S_{i_{1}})\cap\text{reg}(S_{i},S_{i_{2}})=\\{S_{i}\\}$
(IV.1)

where $\\{i_{1},i_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. So by Definition
III.15, we have

$\displaystyle\text{reg}^{\circ}(S_{i},S_{i_{1}})\cap\text{reg}^{\circ}(S_{i},S_{i_{2}})=\emptyset.$
(IV.2)

Thus, the three subsets $\text{reg}^{\circ}(S_{1},S_{2})$,
$\text{reg}^{\circ}(S_{1},S_{3})$ and $\text{reg}^{\circ}(S_{2},S_{3})$ are
mutually disjoint.

To design codes on $\text{RG}(D^{**})$, we find it convenient to decompose
$\text{RG}(D^{**})$ into mutually disjoint parts according to the connection
condition of the source-terminal pairs. In Subsection A, we will give a method
to decompose $\text{RG}(D^{**})$ and show some useful properties of such
decomposition.

###  IV-A Decomposition of $\text{RG}(D^{**})$

We first specify some subsets of $D^{**}$, which leads to a decomposition of
$\text{RG}(D^{**})$ and will play an import role in our study.

###### Definition IV.1

We specify some subsets of $D^{**}$ as follows.

  * (1)

$\Pi\triangleq\text{reg}(S_{1},S_{2})\cup\text{reg}(S_{1},S_{3})\cup\text{reg}(S_{2},S_{3})$.

  * (2)

For $I\subseteq[n]$, $\Omega_{I}$ is the set of all $R\in D^{**}\backslash\Pi$
such that $R\rightarrow T_{j}$ for all $j\in I$ and $R\nrightarrow
T_{j^{\prime}}$ for all $j^{\prime}\in[n]\setminus I$.

  * (3)

$\Lambda_{I}$ is the set of all $Q\in\Pi$ such that $Q$ has a child
$R\in\Omega_{I}$.

If the subset $I=\\{i_{1},\cdots,i_{\ell}\\}$, we also denote
$\Omega_{I}=\Omega_{i_{1},\cdots,i_{\ell}}$ and
$\Lambda_{I}=\Lambda_{i_{1},\cdots,i_{\ell}}$.

###### Example IV.2

We show some examples of the subsets in Definition IV.1 for the region graphs
in Fig. 4.

For the region graph in Fig. 4 (a). By Definition III.15, we have
$\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},R_{1},R_{4}\\}$,
$\text{reg}(S_{1},S_{3})=\\{S_{1},S_{3},R_{2}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},R_{3}\\}$. So by (1) of Definition
IV.1, $\Pi=\\{S_{1},S_{2},S_{3},R_{1},R_{2},R_{3},R_{4}\\}$. By (2) of
Definition IV.1, $\Omega_{i}=\\{T_{i}\\}$ for $i\in\\{1,2,3\\}$,
$\Omega_{2,3}=\\{Q\\}$ and
$\Omega_{1,2}=\Omega_{1,3}=\Omega_{1,2,3}=\emptyset$. By (3) of Definition
IV.1, we have $\Lambda_{1}=\\{R_{1},R_{3}\\}$, $\Lambda_{2}=\\{R_{4}\\}$,
$\Lambda_{3}=\\{R_{3}\\}$, $\Lambda_{2,3}=\\{R_{2},R_{3}\\}$.

For the region graph in Fig. 4 (b), by Definition III.15,
$\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},R_{1},R_{4}\\}$,
$\text{reg}(S_{1},S_{3})=\\{S_{1},S_{3},R_{2}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},R_{3},R_{5}\\}$. So
$\Pi=\\{S_{1},S_{2},S_{3},R_{1}$, $R_{2},R_{3},R_{4},R_{5}\\}$. We can further
check that $\Omega_{1}=\\{T_{1}\\}$, $\Omega_{2}=\\{Q_{1},Q_{3},T_{2}\\}$,
$\Omega_{3}=\\{Q_{2},Q_{4},T_{3}\\}$ and
$\Omega_{1,2}=\Omega_{1,3}=\Omega_{2,3}=\Omega_{1,2,3}=\emptyset$. By (3) of
Definition IV.1, we have $\Lambda_{1}=\\{S_{1},R_{5}\\}$,
$\Lambda_{2}=\\{R_{2},R_{4}\\}$ and $\Lambda_{3}=\\{R_{2},R_{3},R_{5}\\}$.

###### Theorem IV.3

The collection $\\{\Pi\\}\cup\\{\Omega_{I},I\subseteq[n]\\}$ is a partition of
$D^{**}$ and it can be obtained in time $O(|D^{**}|)$.

###### proof IV.4

By Definition IV.1, it is easy to see that
$D^{**}=\Pi\bigcup(\bigcup_{I\subseteq[n]}\Omega_{I})$ and the subsets $\Pi$
and $\Omega_{I},I\subseteq[n],$ are mutually disjoint. So
$\\{\Pi\\}\cup\\{\Omega_{I},I\subseteq[n]\\}$ is a partition of $D^{**}$. We
shall prove that it can be obtained in time $O(|D^{**}|)$.

Since for each $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, the super region
$\text{reg}(S_{i_{1}},S_{i_{2}})$ can be found by Algorithm 1, so the subset
$\Pi$ can be found by Algorithm 1 in time $O(|D^{**}|)$.

Note that $\text{RG}(D^{**})$ is acyclic and the terminal regions have no
child (Assumption 1), then regions in $D^{**}\backslash\Pi$ can be
sequentially indexed as
$D^{**}\backslash\Pi=\\{R_{1},R_{2},R_{3},\cdots,R_{N}\\}$ such that
$R_{N-n+j}=T_{j}$ for $j\in[n]$ and $\ell<\ell^{\prime}$ if $R_{\ell}$ is a
parent of $R_{\ell^{\prime}}$. Then the collection
$\\{\Omega_{I},I\subseteq[n]\\}$ can be found by tracing the parents back for
all terminals. See the following Algorithm 2:

Algorithm 2: Labelling Algorithm $(\text{RG}(D^{**}))$:$j\leftarrow$from $1$
to $n$Label $R_{N-n+j}$ with $j$;$\ell\leftarrow$from $N-n$ to
$1$$j\leftarrow$from $1$ to $n$if$R_{\ell}$has a child $R_{\ell^{\prime}}$
such that $R_{\ell^{\prime}}$ is labelledwith $j$thenLabel $R_{\ell}$ with
$j$;

Note that $R\rightarrow T_{j}$ if and only if $R$ is labelled with $j$ by
Algorithm 2.For each $R\in D^{**}\backslash\Pi$, let
$I_{R}=\\{j\in[n];R\text{~{}is labelled with~{}}j\\}$. Then for each
$I\subseteq[n]$, we have $\Omega_{I}=\\{R;I_{R}=I\\}$. Clearly, the time
complexity of Algorithm 2 is $O(|D^{**}|)$.

Decomposing $D^{**}$ into the subsets $\Pi$ and $\Omega_{I},I\subseteq[n],$
will be used to construct linear solution of $\text{RG}(D^{**})$: We construct
a code $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ on $\Pi$ and a code
$\tilde{C}_{\Omega_{I}}=\\{d_{R};R\in\Omega_{I}\\}$ on $\Omega_{I}$ for each
$I\subseteq[n]$ such that $\Omega_{I}\neq\emptyset$. Then we can potentially
obtain a linear solution $\tilde{C}$ of $\text{RG}(D^{**})$ by letting
$\tilde{C}=\tilde{C}_{\Pi}\textstyle\bigcup\left(\bigcup_{\emptyset\neq
I\subseteq[n]}\tilde{C}_{\Omega_{I}}\right)$. By Theorem IV.3, $\Pi$ and all
subsets $\Omega_{I},I\subseteq[n],$ are mutually disjoint. So the code
$\tilde{C}$ is well defined. This method will be used to prove Theorem IV.12.

###### Lemma IV.5

Let $R\in D^{**}$. Then $R\in D^{**}\backslash\Pi$ if and only if
$S_{i}\rightarrow R$ for all $i\in\\{1,2,3\\}$.

###### proof IV.6

Suppose $R\in D^{**}\backslash\Pi$. By (1) of Definition IV.1, $R\neq
S_{i}\in\Pi$ for all $i\in\\{1,2,3\\}$. Let
$\\{i_{1},i_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. Again by (1) of Definition
IV.1, $R\notin\text{reg}(S_{i_{1}},S_{i_{2}})\subseteq\Pi$. By Definition
III.15, $R$ has a parent, say $R_{1}$, such that
$R_{1}\notin\text{reg}(S_{i_{1}},S_{i_{2}})$. If $R_{1}\neq S_{i}$, then
similarly, $R_{1}$ has a parent $R_{2}$ such that
$R_{2}\notin\text{reg}(S_{i_{1}},S_{i_{2}})$. Since $\text{RG}(D^{**})$ is a
finite graph, we can always find a path $\\{R_{K},R_{K-1},\cdots,R_{1},R\\}$
such that $R_{K}=S_{i}$. Thus, we have $S_{i}\rightarrow R$ for all
$i\in\\{1,2,3\\}$.

Conversely, suppose $S_{i}\rightarrow R$ for all $i\in\\{1,2,3\\}$. Then there
is a path $\\{S_{1},R_{1},\cdots,R_{K-1},R_{K}=R\\}$. Since $S_{1}$ has no
parent (Remark III.4), then by Definition III.15,
$S_{1}\notin\text{reg}(S_{2},S_{3})$. By Definition III.15 and induction,
$R_{i}\notin\text{reg}(S_{2},S_{3})$, $i=1,\cdots,K-1,K$. So
$R=R_{K}\notin\text{reg}(S_{2},S_{3})$. Similarly, we can prove
$R\notin\text{reg}(S_{1},S_{2})$ and $R\notin\text{reg}(S_{1},S_{3})$. So by
(1) of Definition IV.1, $R\notin\Pi$. Thus, $R\in D^{**}\backslash\Pi$.

Clearly, if there is an $S_{i}$ and a $T_{j}$ such that $S_{i}\nrightarrow
T_{j}$, then the sum can’t be transmitted to $T_{j}$ and $\text{RG}(D^{**})$
is unsolvable. So we assume that $S_{i}\rightarrow T_{j}$ for all
$i\in\\{1,2,3\\}$ and $j\in[n]$. Then by Lemma IV.5, $T_{j}\in
D^{**}\backslash\Pi$. Moreover, by Assumption 1, $T_{j}$ has no child. So
$T_{j}\nrightarrow T_{j^{\prime}}$ for all $j^{\prime}\neq j$. Thus, by (2) of
Definition IV.1, we have the following remark.

###### Remark IV.7

For each $j\in[n]$, we have $T_{j}\in\Omega_{j}$.

###  IV-B Terminal-separable Region Graph

In this subsection, we define a class of special region graph called
_terminal-separable region graph_ and prove that for such region graph, the
feasibility is determined by code on $\Pi$.

######  Definition IV.8 (Terminal-separable Region Graph)

The region graph $\text{RG}(D^{**})$ is said to be _terminal-separable_ if
$\Omega_{I}=\emptyset$ for all $I\subseteq[n]$ of size $|I|>1$.

By Theorem IV.3, it is $O(|D^{**}|)$ time complexity to determine whether
$\text{RG}(D^{**})$ is terminal-separable.

According to Example IV.2, the region graph in Fig. 4 (b) is terminal-
separable. However, the region graph in Fig. 4 (a) is not terminal-separable
because $\Omega_{2,3}=\\{Q\\}\neq\emptyset$.

In general, if a region graph is not terminal-separable, then it can be viewed
as a terminal-separable region graph with fewer terminal regions. If the new
one is feasible then the original one is feasible. However, if the new one is
infeasible then the original one is not necessarily infeasible. For example,
for the graph in Fig. 4 (a), we can view $T_{1}$ and $Q$ as two terminal
regions and construct a linear code to transmit the sum $\sum_{i=1}^{3}X_{i}$
to $T_{1}$ and $Q$. Then by Lemma III.13, the sum can be transmitted from $Q$
to $T_{2}$ and $T_{3}$. (See Example III.14.)

###### Lemma IV.9

Suppose $\text{RG}(D^{**})$ is terminal-separable. Then for each $j\in[n]$,
the following hold.

  * 1)

$T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$.

  * 2)

$|\Lambda_{j}|\geq 2$ and
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

  * 3)

For each $Q\in\Lambda_{j}$, there is a path $\\{Q,R_{1},\cdots,R_{K}\\}$ such
that $\\{R_{1},\cdots,R_{K}\\}\subseteq\Omega_{j}$ and $R_{K}=T_{j}$.

###### proof IV.10

1) By Remark IV.7, we have $T_{j}\in\Omega_{j}$.

Since $\text{RG}(D^{**})$ is terminal-separable, then for any
$R\in\Omega_{j}$, by Definition IV.8 and (2), (3) of Definition IV.1, we have
$\text{In}(R)\subseteq\Lambda_{j}\cup\Omega_{j}$. Denote
$\Omega_{j}=\\{R_{1},R_{2},\cdots,R_{N}\\}$ such that $\ell<\ell^{\prime}$ if
$R_{\ell}$ is a parent of $R_{\ell^{\prime}}$. Then we have
$\text{In}(R_{1})\subseteq\Lambda_{j}$. By Definition III.15,
$R_{i}\in\text{reg}^{\circ}(\Lambda_{j})$. Recursively, we have
$\text{In}(R_{i})\subseteq\Lambda_{j}\cup\\{R_{1},\cdots,R_{i-1}\\}$ and
$R_{i}\in\text{reg}^{\circ}(\Lambda_{j}),i=2,\cdots,N$. So
$\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$.

2) If $\Lambda_{j}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$, then by 1) and
Definition III.15,
$\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$,
which contradicts to (2) of Definition IV.1. So
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

If $|\Lambda_{j}|=1$, say $\Lambda_{j}=\\{Q\\}$, then by (1), (3) of
Definition IV.1, we have $Q\in\text{reg}(S_{i_{1}},S_{i_{2}})$ for some
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Thus,
$\Lambda_{j}=\\{Q\\}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$, which
contradicts to the proved result that
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$. So $|\Lambda_{j}|\geq
2$.

3) For each $Q\in\Lambda_{j}$, by (3) of Definition IV.1, $Q$ has a child, say
$R_{1}$, such that $R_{1}\in\Omega_{j}$. By (2) of Definition IV.1,
$R_{1}\rightarrow T_{j}$. Let $\\{R_{1},\cdots,R_{K}\\}$ be a path from
$R_{1}$ to $T_{j}$ such that $R_{K}=T_{j}$. Since $\text{RG}(D^{**})$ is
terminal-separable, then by Definition IV.8, $\Omega_{I}=\emptyset$ for all
$I\subseteq[n]$ of size $|I|>1$. So it must be that
$\\{R_{1},\cdots,R_{K}\\}\subseteq\Omega_{j}$.

Fig 6: Correspondence of equivalent classes, subclasses and coding vectors:
Given a partition
$\mathcal{I}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\cdots,\Delta_{K}\\}$ of
$\Pi$ such that $[S_{i}]=\Delta_{i}$ for $i\in\\{1,2,3\\}$, each equivalent
class is divided into some subclasses and each subclass corresponds to a
unique coding vector.

For further discussion, we need the following definition.

###### Definition IV.11

A collection of vectors $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$
is said to be a feasible code on $\Pi$ if it satisfies the following three
conditions:

  * (1)

$d_{S_{i}}=\alpha_{i}$ for each $i\in\\{1,2,3\\}$;

  * (2)

$d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all
$R\in\Pi\setminus\\{S_{1},S_{2},S_{3}\\}$;

  * (3)

$\bar{\alpha}\in\langle d_{R};R\in\Lambda_{j}\rangle$ for all $j\in[n]$.

The following theorem shows that to determine feasibility of
$\text{RG}(D^{**})$, it is sufficient to determine existence of a feasible
code on $\Pi$.

###### Theorem IV.12

Suppose $\text{RG}(D^{**})$ is terminal-separable. Then $\text{RG}(D^{**})$ is
feasible if and only if there exists a feasible code on $\Pi$.

###### proof IV.13

${}^{\prime\prime}\Rightarrow^{\prime\prime}$. Let
$\tilde{C}=\\{d_{R}\in\mathbb{F}^{3};R\in D^{**}\\}$ be a linear solution of
$\text{RG}(D^{**})$ and $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ be the
constraint of $\tilde{C}$ on $\Pi$. Then by Definition III.5,
$\tilde{C}_{\Pi}$ satisfies conditions (1), (2) of Definition IV.11. Moreover,
by 1) of Lemma IV.9,
$T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$ for all
$j\in[n]$. Then by Remark III.16, $\bar{\alpha}=d_{T_{j}}\in\langle
d_{R};R\in\Lambda_{j}\rangle$. So $\tilde{C}_{\Pi}$ satisfies condition (3) of
Definition IV.11. Thus, $\tilde{C}_{\Pi}$ is a feasible code on $\Pi$.

${}^{\prime\prime}\Leftarrow^{\prime\prime}$. Suppose $\tilde{C}_{\Pi}$ is a
feasible code on $\Pi$. Then for each $j\in[n]$ by condition (3) of Definition
IV.11, $\bar{\alpha}\in\langle d_{R};R\in\Lambda_{j}\rangle$. Moreover, for
each $Q\in\Lambda_{j}$, by 3) of Lemma IV.9, there is a path
$\mathcal{P}_{Q}=\\{Q,R_{1},\cdots,R_{K}=T_{j}\\}$ such that
$\\{R_{1},\cdots,R_{K}\\}\subseteq\Omega_{j}$. Then by Lemma III.19, we can
construct a code $\tilde{C}_{\Omega_{j}}=\\{d_{R};R\in\Omega_{j}\\}$ such that
$d_{T_{j}}=\bar{\alpha}$ and $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all $R\in\Omega_{j}$.
Note that $\Omega_{1},\cdots,\Omega_{n}$ are mutually disjoint (Theorem IV.3).
Then $\tilde{C}=\tilde{C}_{\Pi}\cup\tilde{C}_{1}\cup\cdots\cup\tilde{C}_{n}$
is a linear solution of $\text{RG}(D^{**})$ and $\text{RG}(D^{**})$ is
feasible.

Let $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ be a feasible code on $\Pi$. Since
$\text{RG}(D^{**})$ is acyclic and $d_{S_{i}}=\alpha_{i}\neq 0$ for
$i\in\\{1,2,3\\}$. If there is an $R\in\Pi$ such that $d_{R}=0$, then by
tracing the parents of all $R$ such that $d_{R}=0$, we can always find an
$R_{0}\in\Pi$ such that $d_{R_{0}}=0$ and $d_{R^{\prime}}\neq 0$ for some
$R^{\prime}\in\text{In}(R_{0})$. We redefine $d_{R_{0}}$ by letting
$d_{R_{0}}=d_{R^{\prime}}$. Then $d_{R_{0}}\neq 0$ and it is easy to see that
the resulted code is still a feasible code on $\Pi$. We can perform this
operation continuously until $d_{R}\neq 0$ for all $R\in\Pi$ and the resulted
code is still a feasible code on $\Pi$. Thus, we have the following remark.

###### Remark IV.14

Let $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be a feasible code
on $\Pi$. We can always assume that $d_{R}\neq 0$ for all $R\in\Pi$.

###### Lemma IV.15

Let $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be a feasible code
on $\Pi$. The following hold:

  * 1)

If $\Theta\subseteq\Pi$ and $R\in\text{reg}(\Theta)$, then $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\Theta\rangle$. Thus, if
$R\in\text{reg}(S_{i_{1}},S_{i_{2}})$ for some
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, then
$d_{R}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$. Moreover, If $\langle
d_{R^{\prime}}\rangle=\langle d_{R^{\prime\prime}}\rangle$ and
$R\in\text{reg}(R^{\prime},R^{\prime\prime})$, then $\langle
d_{R}\rangle=\langle d_{R^{\prime}}\rangle=\langle
d_{R^{\prime\prime}}\rangle$.

  * 2)

If $\\{R,R^{\prime}\\}=\Lambda_{j}$, then $\langle
d_{R},d_{R^{\prime}}\rangle=\langle\bar{\alpha},d_{R}\rangle=\langle\bar{\alpha},d_{R^{\prime}}\rangle$.

###### proof IV.16

1) is a direct consequence of Definition III.15 and conditions (1), (2) of
Definition IV.11.

2) By claim 1), we have
$\\{d_{R},d_{R^{\prime}}\\}\subseteq\langle\alpha_{1},\alpha_{2}\rangle\cup\langle\alpha_{1},\alpha_{3}\rangle\cup\langle\alpha_{2},\alpha_{3}\rangle$,
which implies that $\bar{\alpha}\notin\langle d_{R}\rangle$ and
$\bar{\alpha}\notin\langle d_{R^{\prime}}\rangle$. By condition (3) of
Definition IV.11, $\bar{\alpha}\in\langle d_{R},d_{R^{\prime}}\rangle$. So
$\bar{\alpha},d_{R}$ and $d_{R^{\prime}}$ are mutually linearly independent
and
$\langle\bar{\alpha},d_{R}\rangle=\langle\bar{\alpha},d_{R^{\prime}}\rangle=\langle
d_{R},d_{R^{\prime}}\rangle$.

##  V Weak Decentralized Code on $\Pi$

In this section, we generalize the weak decentralized code on one super region
(Definition III.21) to $\Pi$, which is the union of three super regions
(Definition IV.1). Our discussions begin with a most general partition of
$\Pi$ and its refinement. Then we define week decentralized code on the so
called ”R-closed partition of $\Pi$”(Definition V.6.). Note that the
construction of the R-closed partition of $\Pi$ will be left to next section.

###  V-A Partition of $\Pi$ and Its Refinement

Let $\mathcal{I}=\\{\Delta_{1},\cdots,\Delta_{K}\\}$ be a partition of $\Pi$.
As mentioned before, for each $\Delta_{i}\in\mathcal{I}$, we can choose an
arbitrary $R\in\Delta_{i}$ as a representative element and denote
$\Delta_{i}=[R]$. On the other hand, for each $R\in\Pi$, we have
$R\in\Delta_{i}$ for some $\Delta_{i}\in\mathcal{I}$. We will use $\Delta_{i}$
and $[R]$ interchangeably. We further assume that $[S_{i}]\neq[S_{j}]$ for
each pair $\\{i,j\\}\subseteq\\{1,2,3\\}$. Thus, $K\geq 3$ and by proper
naming, we can assume $\Delta_{i}=[S_{i}],~{}i=1,2,3$. For each
$[R]=\Delta_{i}\in\mathcal{I}$ and $\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$, we
denote

$\displaystyle\vspace{-0.1cm}[R]_{j_{1},j_{2}}=[\Delta_{i}]_{j_{1},j_{2}}=\Delta_{i}\cap\text{reg}(S_{j_{1}},S_{j_{2}}).$
(V.1)

For $i\in\\{1,2,3\\}$ and $\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$, we
denote

$\displaystyle\vspace{-0.1cm}[S_{i}]_{i}=[S_{i}]\cap(\text{reg}(S_{i},S_{j_{1}})\cup\text{reg}(S_{i},S_{j_{2}})).$
(V.2)

By (V.1) and (V.2), we have
$[S_{i}]_{i}=[S_{i}]_{i,j_{1}}\cup[S_{i}]_{i,j_{2}}$.

Given a partition $\mathcal{I}=\\{\Delta_{1},\cdots,\Delta_{K}\\}$ of $\Pi$ as
above, we can further refine it as follows:

######  Definition V.1 (Subclass)

For $i\in\\{1,2,3\\}$, $[S_{i}]$ is divided into two _subclasses_
$[S_{i}]_{i}$ and $[S_{i}]_{j_{1},j_{2}}$, where
$\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$; For $i\geq 4$, $\Delta_{i}$
is divided into three _subclasses_ $[\Delta_{i}]_{1,2},[\Delta_{i}]_{1,3}$ and
$[\Delta_{i}]_{2,3}$.

In what follows, an equivalent class of $\mathcal{I}$ refers to $\Delta_{i}$
(or $[R]$) and a subclass of $\mathcal{I}$ refers to the subclass of
$\Delta_{i}$ defined above. Moreover, we usually use $[[R]]$ to denote a
subclass of $[R]$. Note that a subclass of $[R]$ could be an empty set. The
correspondence of equivalent classes and subclasses are illustrated in Fig. 6.
By (IV.1), (IV.2), (V.1) and (V.2), the collection of all subclasses of
$\mathcal{I}$ is still a partition of $\Pi$.

Fig 7: An example of weak decentralized code on $\Pi$: (a) is the example
region graph, where the subset $\Pi$ is partitioned into five equivalent
classes, regions in the same equivalent class are drawn in the same color; (b)
is an illustration of the corresponding weak decentralized code.

###### Example V.2

Consider the region graph in Fig. 7 (a). One can check that
$\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},R_{1},R_{2},R_{6}$, $R_{7}\\}$,
$\text{reg}(S_{1},S_{3})=\\{S_{1},S_{3},R_{3},R_{8}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},R_{4},R_{5},R_{9}\\}$. Thus,
$\Pi=\\{S_{1},S_{2},S_{3}$, $R_{1},\cdots,R_{9}\\}$.

Let
$\mathcal{I}_{c}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\Delta_{4},\Delta_{5}\\}$,
where $\Delta_{1}=\\{S_{1}\\}$, $\Delta_{2}=\\{S_{2}\\}$,
$\Delta_{3}=\\{S_{3},R_{7},R_{8},R_{9}\\}$,
$\Delta_{4}=\\{R_{1},R_{2},R_{3},R_{5},R_{6}\\}$ and $\Delta_{5}=\\{R_{4}\\}$.
Then $\Delta_{1}$ has one nonempty subclass $[S_{1}]_{1}=\\{S_{1}\\}$;
$\Delta_{2}$ has one nonempty subclass $[S_{2}]_{2}=\\{S_{2}\\}$; $\Delta_{3}$
has two nonempty subclasses $[S_{3}]_{3}=\\{S_{3},R_{8},R_{9}\\}$ and
$[S_{3}]_{1,2}=\\{R_{7}\\}$; $\Delta_{4}$ has three nonempty subclasses
$[R_{1}]_{1,2}=\\{R_{1},R_{2},R_{6}\\}$, $[R_{1}]_{1,3}=\\{R_{3}\\}$ and
$[R_{1}]_{2,3}=\\{R_{5}\\}$; $\Delta_{5}$ has one nonempty subclass
$[R_{4}]_{2,3}=\\{R_{4}\\}$. All these subclasses form the desired refinement
of $\mathcal{I}_{c}$.

Let $\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$, where $[R]=\\{R\\}$ for all
$R\in\Pi$. We call $\mathcal{I}_{0}$ the _trivial partition_ of $\Pi$.
Clearly, each equivalent class $[R]\in\mathcal{I}_{0}$ has only one non-empty
subclass, i.e., itself.

###  V-B Weak Decentralized Code on $\Pi$

In this subsection, we construct weak decentralized code on $\Pi$. All coding
vectors will be taken from $\mathbb{F}^{3}$, where $\mathbb{F}$ is a
sufficient large field. Also note that for $k=3$, the vectors
$\alpha_{1}=(1,0,0),\alpha_{2}=(0,1,0),\alpha_{3}=(0,0,1)$ and
$\bar{\alpha}=(1,1,1)$.

First, we give a lemma for constructing coding vectors.

###### Lemma V.3

Let $\mathbb{F}$ be a sufficiently large field. Then for any $K\geq 3$, there
exist $K$ sets of vectors
$\mathcal{B}_{1}=\\{\alpha_{1},\alpha_{2}+\alpha_{3}\\}$,
$\mathcal{B}_{2}=\\{\alpha_{2},\alpha_{1}+\alpha_{3}\\}$,
$\mathcal{B}_{3}=\\{\alpha_{3},\alpha_{1}+\alpha_{2}\\}$,
$\mathcal{B}_{4}=\\{\beta^{(4)}_{1,2},\beta^{(4)}_{1,3},\beta^{(4)}_{2,3}\\}$,
$\cdots$,
$\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2},\beta^{(K)}_{1,3},\beta^{(K)}_{2,3}\\}\subseteq\mathbb{F}^{3}$
and the following properties are satisfied:

  * (1)

For any $\ell\in\\{4,\cdots,K\\}$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
$\beta^{(\ell)}_{i_{1},i_{2}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$;

  * (2)

If $\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{\ell}$ for some
$\ell\in\\{1,\cdots,K\\}$, then
$\bar{\alpha}\in\langle\gamma,\gamma^{\prime}\rangle$;

  * (3)

For any pair
$\\{\gamma,\gamma^{\prime}\\}\subseteq\cup_{\ell=1}^{K}\mathcal{B}_{\ell}$,
$\gamma$ and $\gamma^{\prime}$ are linearly independent.

  * (4)

If
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$
such that
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\neq\\{\beta^{(\ell)}_{1,2},\beta^{(\ell)}_{1,3},\beta^{(\ell)}_{2,3}\\}$
for all $\ell\in\\{4,\cdots,K\\}$, then $\gamma,\gamma^{\prime}$ and
$\gamma^{\prime\prime}$ are linearly independent;

###### proof V.4

The proof is given in Appendix A.

We give an example of sets of vectors satisfying properties (1)$-$(4) of Lemma
V.3. For simplicity, we assume that $\mathbb{F}=GF(p)$ for a sufficiently
large prime $p$.

###### Example V.5

Let
$\mathcal{B}_{1}=\\{\alpha_{1},\alpha_{2}+\alpha_{3}\\},\mathcal{B}_{2}=\\{\alpha_{2},\alpha_{1}+\alpha_{3}\\},\mathcal{B}_{3}=\\{\alpha_{3},\alpha_{1}+\alpha_{2}\\}$,
$\mathcal{B}_{4}=\\{\alpha_{1}+3\alpha_{2},2\alpha_{1}+3\alpha_{3}$,
$2\alpha_{2}-\alpha_{3}\\}$ and
$\mathcal{B}_{5}=\\{2\alpha_{1}+3\alpha_{2},\alpha_{1}+3\alpha_{3},\alpha_{2}-2\alpha_{3}\\}$.
Then
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3},\mathcal{B}_{4},\mathcal{B}_{5}\\}$
satisfies all conditions of Lemma V.3.

Convention: To unify the notations, we also denote
$\beta^{(1)}_{1}=\alpha_{1}$ and $\beta^{(1)}_{2,3}=\alpha_{2}+\alpha_{3}$.
Similarly, we denote $\beta^{(2)}_{2}=\alpha_{2}$,
$\beta^{(2)}_{1,3}=\alpha_{1}+\alpha_{3}$, $\beta^{(3)}_{3}=\alpha_{3}$ and
$\beta^{(3)}_{1,2}=\alpha_{1}+\alpha_{2}$.

###### Definition V.6

A partition
$\mathcal{I}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\cdots,\Delta_{K}\\}$ of
$\Pi$ is said to be R-_closed_ if $[S_{i_{1}}]\neq[S_{i_{2}}]$ and
$\text{reg}([\Delta_{j}]_{i_{1},i_{2}})=[\Delta_{j}]_{i_{1},i_{2}}$ for all
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and $j\in\\{1,\cdots,K\\}$.

For example, for the region graph in Fig. 7 (a), the partition
$\mathcal{I}_{c}$ in Example V.2 is an R-closed partition of $\Pi$.

Let
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3},\cdots,\mathcal{B}_{K}\\}$
be constructed as in Lemma V.3 and
$\mathcal{I}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\cdots,\Delta_{K}\\}$ be an
R-closed partition of $\Pi$. By proper naming, we can let
$\Delta_{i}=[S_{i}],i=1,2,3$. Then all subclasses of $\mathcal{I}$ are in one-
to-one correspondence with all vectors in
$\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$, where subclasses are defined as in
Definition V.1 (See Fig. 6.). Let $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ be
constructed by assigning each vector in
$\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$ to all regions in the corresponding
subclass. Specifically, let

  * •

$d_{R}=\beta^{(i)}_{i}$ for each $i\in\\{1,2,3\\}$ and $R\in[S_{i}]_{i}$;

  * •

$d_{R}=\beta^{(i)}_{j_{1},j_{2}}$ for each $i\in\\{1,2,3\\}$ and
$R\in[S_{i}]_{j_{1},j_{2}}$, where
$\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$;

  * •

$d_{R}=\beta^{(i)}_{j_{1},j_{2}}$ for each $i\in\\{4,\cdots,K\\}$, each subset
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$ and each
$R\in[\Delta_{i}]_{j_{1},j_{2}}$.

###### Definition V.7

The code $\tilde{C}_{\Pi}$ constructed as above is called an
$\mathcal{I}$-_weak decentralized code_ on $\Pi$.

Fig. 7 (b) illustrates an $\mathcal{I}_{c}$-weak decentralized code for the
region graph in Fig. 7 (a), where $\mathcal{I}_{c}$ is as in Example V.2.

To discuss the property of weak decentralized code on $\Pi$, we need the
following conception.

######  Definition V.8 (Independent Set)

Let $\mathcal{I}$ be an R-closed partition of $\Pi$. A subset
$\\{Q,Q^{\prime},Q^{\prime\prime}\\}\subseteq\Pi$ is called an
$\mathcal{I}$-_independent set_ if the following three conditions hold:

  * (1)

$|\\{Q,Q^{\prime},Q^{\prime\prime}\\}\bigcap[[R]]|\leq 1$ for any equivalent
class $[R]\in\mathcal{I}$ and any subclass $[[R]]$ of $[R]$, i.e., the three
regions $Q,Q^{\prime},Q^{\prime\prime}$ belongs to three different subclasses
of $\mathcal{I}$;

  * (2)

$\\{Q,Q^{\prime},Q^{\prime\prime}\\}\nsubseteq[R]$ for any equivalent class
$R\in\mathcal{I}$;

  * (3)

$\\{Q,Q^{\prime},Q^{\prime\prime}\\}\nsubseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
for any pair $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

###### Example V.9

Consider the partition $\mathcal{I}_{c}=\\{\Delta_{1},\Delta_{2},\Delta_{3}$,
$\Delta_{4},\Delta_{5}\\}$ in Example V.2. We can check that
$\\{S_{1},R_{2},R_{3}\\}$ is an $\mathcal{I}_{c}$-independent set. We can also
check that $\\{R_{1},R_{2},R_{4}\\}$ is not an $\mathcal{I}_{c}$-independent
set because
$|\\{R_{1},R_{2},R_{4}\\}\cap[\Delta_{4}]_{1,2}|=|\\{R_{1},R_{2}\\}|\geq 2$,
violating condition (1) of Definition V.8; $\\{R_{1},R_{3},R_{5}\\}$ is not an
$\mathcal{I}_{c}$-independent set because
$\\{R_{1},R_{3},R_{5}\\}\subseteq\Delta_{4}$, violating condition (2) of
Definition V.8; $\\{S_{1},R_{3},R_{9}\\}$ is not an
$\mathcal{I}_{c}$-independent set because
$\\{S_{1},R_{3},R_{9}\\}\subseteq[S_{3}]_{3}\bigcup\text{reg}(S_{1},S_{3})$,
violating condition (3) of Definition V.8.

The following theorem is an important property of weak decentralized code on
$\Pi$.

###### Theorem V.10

Let $\mathcal{I}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\cdots,\Delta_{K}\\}$ be
an R-closed partition of $\Pi$ and
$\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be an
$\mathcal{I}$-weak decentralized code on $\Pi$. The following hold:

  * 1)

$d_{S_{i}}=\alpha_{i},i=1,2,3$.

  * 2)

$d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all
$R\in\Pi\backslash\\{S_{1},S_{2},S_{3}\\}$.

  * 3)

If $Q$ and $Q^{\prime}$ belong to two different subclasses of some
$[R_{j}]\in\mathcal{I}$, then $\bar{\alpha}\in\langle
d_{Q},d_{Q^{\prime}}\rangle$.

  * 4)

If $\\{Q,Q^{\prime},Q^{\prime\prime}\\}$ is an $\mathcal{I}$-independent set,
then $d_{Q},d_{Q^{\prime}},d_{Q^{\prime\prime}}$ are linearly independent.
Hence, $\bar{\alpha}\in\langle
d_{Q},d_{Q^{\prime}},d_{Q^{\prime\prime}}\rangle$.

###### proof V.11

1), 3) are obvious by the construction of $\tilde{C}_{\Pi}$.

To prove 2), we fix $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. For each
$j\in\\{1,\cdots,K\\}$, let $\Delta^{\prime}_{j}=[\Delta_{j}]_{i_{1},i_{2}}$.
Since $\mathcal{I}$ is an R-closed partition of $\Pi$, then
$\mathcal{I}^{\prime}=\\{\Delta^{\prime}_{1},\Delta^{\prime}_{2},\cdots,\Delta^{\prime}_{K}\\}$
is an R-closed partition of $\text{reg}(S_{i_{1}},S_{i_{2}})$. By the
construction of $\tilde{C}_{\Pi}$, the subcode
$\tilde{C}_{S_{i_{1}},S_{i_{2}}}=\\{d_{R};R\in\text{reg}(S_{i_{1}},S_{i_{2}})\\}$
is an $\mathcal{I}^{\prime}$-weak decentralized code on
$\text{reg}(S_{i_{1}},S_{i_{2}})$. By Lemma III.22, $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all
$R\in\text{reg}^{\circ}(S_{i_{1}},S_{i_{2}})$. Note that $\\{i_{1},i_{2}\\}$
can be arbitrary subset of $\\{1,2,3\\}$. Then we have $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$ for all
$R\in\text{reg}^{\circ}(S_{1},S_{2})\cup\text{reg}^{\circ}(S_{1},S_{3})\cup\text{reg}^{\circ}(S_{2},S_{3})=\Pi\setminus\\{S_{1},S_{2},S_{3}\\}$.

4) By Definition V.7 and V.8, the three vectors $d_{Q},d_{Q^{\prime}}$ and
$d_{Q^{\prime\prime}}$ satisfy condition (4) of Lemma V.3, hence are linearly
independent. So $\bar{\alpha}\in\mathbb{F}^{3}=\langle
d_{Q},d_{Q^{\prime}},d_{Q^{\prime\prime}}\rangle$.

Note that in the construction of $\mathcal{I}$-weak decentralized code,
$\Lambda_{1},\Lambda_{2},\cdots,\Lambda_{n}$ are not taken into consideration.
So in general, an $\mathcal{I}$-weak decentralized code is not necessarily a
feasible code on $\Pi$. In the next section, we will construct a partition
$\mathcal{I}_{c}$ of $\Pi$, called a normal partition of $\Pi$, such that
$\text{RG}(D^{**})$ is feasible if and only if the $\mathcal{I}_{c}$-weak
decentralized code on $\Pi$ is a feasible code on $\Pi$.

##  VI Network Coding for $3$-source $n$-terminal Terminal-separable Sum-
network

In this section, we always assume $\text{RG}(D^{**})$ is a terminal-separable
region graph with $3$ source regions and $n$ terminal regions, where $n$ is an
positive integer. We will characterize the feasibility of $\text{RG}(D^{**})$
and show that it can be determined in polynomial time. Recall that by Theorem
IV.12, we just need to determine the existence of a feasible code on $\Pi$.

###  VI-A Some Examples

In this subsection, we use three examples to show the basic idea of
determining feasibility of $\text{RG}(D^{**})$.

###### Example VI.1

Let $\text{RG}(D^{**})$ be the region graph in Fig. 7 (a). In Example V.2, we
have seen that $\Pi=\\{S_{1},S_{2},S_{3}$, $R_{1},\cdots,R_{9}\\}$. By (2) of
Definition IV.1, $\Omega_{j}=\\{T_{j}\\}$ for $j\in\\{1,\cdots,6\\}$ and
$\Omega_{I}=\emptyset$ for all $I\subseteq\\{1,\cdots,6\\}$ of size $|I|\geq
2$. So $\text{RG}(D^{**})$ is terminal-separable. Moreover, by (3) of
Definition IV.1, $\Lambda_{1}=\\{R_{2},R_{5}\\}$,
$\Lambda_{2}=\\{R_{1},R_{5}\\}$, $\Lambda_{3}=\\{R_{7},R_{8}\\}$,
$\Lambda_{4}=\\{S_{3},R_{7}\\}$, $\Lambda_{5}=\\{R_{3},R_{6}\\}$,
$\Lambda_{6}=\\{R_{7},R_{9}\\}$.

Let $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be an arbitrary
feasible code on $\Pi$. By Remark IV.14, we assume $d_{R}\neq 0$ for all
$R\in\Pi$. The following process yields a partition of $\Pi$.

First, we consider $S_{3}$. Since $\\{S_{3},R_{7}\\}=\Lambda_{4}$, then by 2)
of Lemma IV.15, $\langle d_{R_{7}},\bar{\alpha}\rangle=\langle
d_{S_{3}},\bar{\alpha}\rangle.$ Similarly, $\\{R_{7},R_{8}\\}=\Lambda_{3}$ and
$\\{R_{7},R_{9}\\}=\Lambda_{6}$ imply that $\langle
d_{R_{8}},\bar{\alpha}\rangle=\langle d_{R_{7}},\bar{\alpha}\rangle=\langle
d_{R_{9}},\bar{\alpha}\rangle.$ So we have

$\langle d_{S_{3}},\bar{\alpha}\rangle=\langle
d_{R_{7}},\bar{\alpha}\rangle=\langle d_{R_{8}},\bar{\alpha}\rangle=\langle
d_{R_{9}},\bar{\alpha}\rangle.$

For the coding vectors $d_{S_{3}},d_{R_{7}},d_{R_{8}}$ and $d_{R_{9}}$, note
that if we know one of them, then we can use the above relation to obtain all
of them. As an example, let us see how $d_{S_{3}}$ determine $d_{R_{7}}$:
Since $R_{7}\in\text{reg}(S_{1},S_{2})$, then by 1) of Lemma IV.15,
$d_{R_{7}}\in\langle\alpha_{1},\alpha_{2}\rangle$. So $\langle
d_{R_{7}}\rangle=\langle
d_{S_{3}},\bar{\alpha}\rangle\cap\langle\alpha_{1},\alpha_{2}\rangle=\langle\alpha_{1}+\alpha_{2}\rangle.$

Second, consider $R_{1}$. Since $\\{R_{1},R_{5}\\}=\Lambda_{2}$ and
$\\{R_{2},R_{5}\\}=\Lambda_{1}$, then by 2) of Lemma IV.15, we have

$\langle d_{R_{1}},\bar{\alpha}\rangle=\langle
d_{R_{5}},\bar{\alpha}\rangle=\langle d_{R_{2}},\bar{\alpha}\rangle.$

Note that $\\{R_{1},R_{2}\\}\subseteq\text{reg}(S_{1},S_{2})$. Then by 1) of
Lemma IV.15, $d_{R_{1}},d_{R_{2}}\in\langle\alpha_{1},\alpha_{2}\rangle.$ So
$d_{R_{2}}\in\langle
d_{R_{1}},\bar{\alpha}\rangle\cap\langle\alpha_{1},\alpha_{2}\rangle=\langle
d_{R_{1}}\rangle$, which implies that $\langle d_{R_{1}}\rangle=\langle
d_{R_{2}}\rangle.$ Moreover, by Fig. 7 (a), $R_{6}\in\text{reg}(R_{1},R_{2})$.
Then by 1) of Lemma IV.15, $\langle d_{R_{6}}\rangle=\langle
d_{R_{2}}\rangle=\langle d_{R_{1}}\rangle.$ So $\langle
d_{R_{6}},\bar{\alpha}\rangle=\langle d_{R_{1}},\bar{\alpha}\rangle=\langle
d_{R_{5}},\bar{\alpha}\rangle=\langle d_{R_{2}},\bar{\alpha}\rangle.$ Again by
the condition $\\{R_{3},R_{6}\\}=\Lambda_{5}$ and 2) of Lemma IV.15, we have
$\langle d_{R_{3}},\bar{\alpha}\rangle=\langle d_{R_{6}},\bar{\alpha}\rangle.$
Thus,

$\langle d_{R_{3}},\bar{\alpha}\rangle=\langle
d_{R_{6}},\bar{\alpha}\rangle=\langle d_{R_{1}},\bar{\alpha}\rangle=\langle
d_{R_{5}},\bar{\alpha}\rangle=\langle d_{R_{2}},\bar{\alpha}\rangle.$

Let $\Delta_{1}=\\{S_{1}\\},\Delta_{2}=\\{S_{2}\\}$,
$\Delta_{3}=\\{S_{3},R_{7},R_{8},R_{9}\\}$,
$\Delta_{4}=\\{R_{1},R_{2},R_{3},R_{5},R_{6}\\}$, $\Delta_{5}=\\{R_{4}\\}$ and
$\mathcal{I}_{c}=\\{\Delta_{1},\Delta_{2},\Delta_{3},\Delta_{4},\Delta_{5}\\}$.
(See Fig. 7 (a).) Then for any $\Delta_{i}$, if we know the coding vector of
one region in $\Delta_{i}$, then we can obtain the coding vectors of all other
regions in $\Delta_{i}$.

Let $\tilde{C}_{\Pi}$ be the $\mathcal{I}_{c}$-weak decentralized code
constructed in Fig. 7 (b). It is easy to check that $\tilde{C}_{\Pi}$ is a
feasible code on $\Pi$. So $\text{RG}(D^{**})$ is feasible.

Fig 8: Two examples of infeasible region graph.

###### Example VI.2

Let $\text{RG}(D^{**})$ be the region graph in Fig. 8 (a). By Definition
III.15, $\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},P_{2},P_{3}\\}$,
$\text{reg}(S_{1},S_{3})=\\{S_{1},S_{3}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},P_{1}\\}$. By (2) of Definition IV.1,
$\Omega_{j}=\\{T_{j}\\}$ for $j\in\\{1,2,3\\}$ and $\Omega_{I}=\emptyset$ for
all $I\subseteq\\{1,2,3\\}$ of size $|I|\geq 2$. So $\text{RG}(D^{**})$ is
terminal-separable. By (3) of Definition IV.1,
$\Lambda_{1}=\\{S_{1},P_{1}\\}$, $\Lambda_{2}=\\{P_{1},P_{2}\\}$ and
$\Lambda_{3}=\\{S_{3},P_{3}\\}$.

Let $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be an arbitrary
feasible code on $\Pi$.

Consider $S_{1}$. Since $\\{S_{1},P_{1}\\}=\Lambda_{1}$ and
$\\{P_{1},P_{2}\\}=\Lambda_{2}$, then by 2) of Lemma IV.15, we have

$\langle d_{P_{2}},\bar{\alpha}\rangle=\langle
d_{P_{1}},\bar{\alpha}\rangle=\langle d_{S_{1}},\bar{\alpha}\rangle.$

So $d_{P_{2}}\in\langle d_{S_{1}},\bar{\alpha}\rangle.$ Note that
$P_{2}\in\text{reg}(S_{1},S_{2})$. Then by 1) of Lemma IV.15, we have
$d_{P_{2}}\in\langle\alpha_{1},\alpha_{2}\rangle.$ Thus,

$\langle d_{P_{2}}\rangle=\langle
d_{S_{1}},\bar{\alpha}\rangle\cap\langle\alpha_{1},\alpha_{2}\rangle=\langle
d_{S_{1}}\rangle.$

Moreover, since $P_{3}\in\text{reg}(S_{1},P_{2})$ (See Fig. 8 (a).), then by
1) of Lemma IV.15, $\langle d_{P_{3}}\rangle=\langle d_{P_{2}}\rangle=\langle
d_{S_{1}}\rangle$, which implies that

$\langle d_{P_{3}},\bar{\alpha}\rangle=\langle
d_{P_{2}},\bar{\alpha}\rangle=\langle d_{P_{1}},\bar{\alpha}\rangle=\langle
d_{S_{1}},\bar{\alpha}\rangle.$

Again by $\\{S_{3},P_{3}\\}=\Lambda_{3}$ and 2) of Lemma IV.15, we have

$\displaystyle\langle d_{S_{3}},\bar{\alpha}\rangle=\langle
d_{P_{3}},\bar{\alpha}\rangle=\langle d_{P_{2}},\bar{\alpha}\rangle=\langle
d_{P_{1}},\bar{\alpha}\rangle=\langle d_{S_{1}},\bar{\alpha}\rangle.$ (VI.1)

So we obtain a subset $[S_{1}]=\\{S_{1},P_{1},P_{2},P_{3},S_{3}\\}$. Let
$\mathcal{I}_{c}=\\{[S_{1}],[S_{2}]\\}$, where $[S_{2}]=\\{S_{2}\\}$. Note
that $[S_{1}]=[S_{3}]$.

We remark that (VI.1) can not be satisfied because we can check that
$d_{S_{1}}=\alpha_{1}\notin\langle\alpha_{3},\bar{\alpha}\rangle=\langle
d_{S_{3}},\bar{\alpha}\rangle$. So $\langle
d_{S_{3}},\bar{\alpha}\rangle\neq\langle d_{S_{1}},\bar{\alpha}\rangle$. Thus,
$\tilde{C}_{\Pi}$ can not be well constructed. By Theorem IV.12,
$\text{RG}(D^{**})$ is infeasible.

###### Example VI.3

Let $\text{RG}(D^{**})$ be the region graph in Fig. 8 (b). By Definition
III.15, $\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},P_{2},P_{3}\\}$,
$\text{reg}(S_{1},S_{3})=\\{S_{1},S_{3},P_{4},P_{5}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3}$, $P_{1}\\}$. By (2) of Definition
IV.1, $\Omega_{j}=\\{T_{j}\\}$ for $j\in\\{1,2,3\\}$ and
$\Omega_{I}=\emptyset$ for all $I\subseteq\\{1,2,3\\}$ of size $|I|\geq 2$. So
$\text{RG}(D^{**})$ is terminal-separable. Moreover, by (3) of Definition
IV.1, $\Lambda_{1}=\\{S_{1},P_{1}\\}$, $\Lambda_{2}=\\{P_{1},P_{2}\\}$ and
$\Lambda_{3}=\\{P_{3},P_{4},P_{5}\\}$.

Let $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ be an arbitrary
feasible code on $\Pi$. Consider $S_{1}\in\Pi$. By the same discussion as in
Example VI.2, we can find a subset $[S_{1}]=\\{S_{1},P_{1},P_{2},P_{3}\\}$
such that

$\displaystyle\langle d_{P_{3}},\bar{\alpha}\rangle=\langle
d_{P_{2}},\bar{\alpha}\rangle=\langle d_{P_{1}},\bar{\alpha}\rangle=\langle
d_{S_{1}},\bar{\alpha}\rangle.$

Let $\mathcal{I}_{c}=\\{[S_{1}],[S_{2}],[S_{3}],[P_{4}],[P_{5}]\\}$, where
$[S_{2}]=\\{S_{2}\\}$, $[S_{3}]=\\{S_{3}\\}$, $[P_{4}]=\\{P_{4}\\}$ and
$[P_{5}]=\\{P_{5}\\}$. Note that $[S_{1}]_{1}=\\{S_{1},P_{2},P_{3}\\}$ and
$\Lambda_{3}=\\{P_{3},P_{4},P_{5}\\}\subseteq[S_{1}]_{1}\bigcup\text{reg}(S_{1},S_{3})$.

We now derive a contradiction. Firstly, as in Example VI.2, we have $\langle
d_{P_{3}}\rangle=\langle d_{S_{1}}\rangle.$ Secondly, since
$P_{4},P_{5}\in\text{reg}(S_{1},S_{3})$, by 1) of Lemma IV.15, we have
$d_{P_{4}},d_{P_{5}}\in\langle\alpha_{1},\alpha_{3}\rangle$. Then by condition
(3) of Definition IV.11,
$\bar{\alpha}=\alpha_{1}+\alpha_{2}+\alpha_{3}\in\langle
d_{R};R\in\Lambda_{3}\rangle=\langle
d_{P_{3}},d_{P_{4}},d_{P_{5}}\rangle\subseteq\langle\alpha_{1},\alpha_{3}\rangle$,
a contradiction.

Thus, there exists no feasible code on $\Pi$ and we conclude that
$\text{RG}(D^{**})$ is infeasible.

In general, if $\text{RG}(D^{**})$ is terminal-separable, then we can always
find a partition $\mathcal{I}_{c}$ of $\Pi$ such that : If $[S_{i}]=[S_{j}]$
for some $\\{i,j\\}\subseteq\\{1,2,3\\}$, then $\text{RG}(D^{**})$ is
infeasible (Example VI.2); If
$\Lambda_{j}\subseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
for some $j\in[n]$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, then
$\text{RG}(D^{**})$ is infeasible (Example VI.3); Otherwise, the
$\mathcal{I}_{c}$-weak decentralized code on $\Pi$ is a feasible code on $\Pi$
and $\text{RG}(D^{**})$ is feasible (Example VI.1). —- In this sense, we call
$\mathcal{I}_{c}$ a normal partition of $\Pi$.

###  VI-B Determining Feasibility of $\text{RG}(D^{**})$

In this subsection we formally describe our method, which is a generalization
of the idea of last subsection.

Firstly, we need a definitions.

###### Definition VI.4

Let $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ be a partition
of $\Pi$ and $\\{[R^{\prime}],[R^{\prime\prime}]\\}\subseteq\mathcal{I}$. We
say that $[R^{\prime}]$ and $[R^{\prime\prime}]$ are _connected_ if one of the
following conditions hold:

  * (1)

There is a subclass $[[R^{\prime}]]$ of $[R^{\prime}]$ and a subclass
$[[R^{\prime\prime}]]$ of $[R^{\prime\prime}]$ such that
$\Lambda_{j}\subseteq[[R^{\prime}]]\cup[[R^{\prime\prime}]]$ for some
$j\in[n]$;

  * (2)

There is a subset $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ such that
$\text{reg}([R^{\prime}]_{i_{1},i_{2}})\cap\text{reg}([R^{\prime\prime}]_{i_{1},i_{2}})\neq\emptyset$.

Suppose $\mathcal{I}$ is a partition of $\Pi$ and
$\\{[R^{\prime}],[R^{\prime\prime}]\\}\subseteq\mathcal{I}$. By combining
$[R^{\prime}]$ and $[R^{\prime\prime}]$ into one equivalent class
$[R^{\prime}]\cup[R^{\prime\prime}]$, we obtain a partition
$\mathcal{I}^{\prime}=\mathcal{I}\cup\\{[R^{\prime}]\cup[R^{\prime\prime}]\\}\setminus\\{[R^{\prime}],[R^{\prime\prime}]\\}$
of $\Pi$. We call $\mathcal{I}^{\prime}$ a _contraction_ of $\mathcal{I}$ by
combining $[R^{\prime}]$ and $[R^{\prime\prime}]$.

###### Example VI.5

Consider again Example VI.3. We can check that $\mathcal{I}_{c}$ is obtained
from $\mathcal{I}_{0}$ by a series of contraction by combining two connected
equivalent classes, where $\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$ is the trivial
partition of $\Pi$. In fact, by condition (1) of Definition VI.4,
$[S_{1}]=\\{S_{1}\\}$ and $[P_{1}]=\\{P_{1}\\}$ are connected in
$\mathcal{I}_{0}$. So by combining $[S_{1}]$ and $[P_{1}]$ into
$[S_{1}]=\\{S_{1},P_{1}\\}$, we obtain a partition $\mathcal{I}_{1}$ of $\Pi$.
Similarly, $[S_{1}]=\\{S_{1},P_{1}\\}$ and $[P_{2}]=\\{P_{2}\\}$ are connected
in $\mathcal{I}_{1}$ and we can obtain a partition $\mathcal{I}_{2}$ of $\Pi$
by combining $[S_{1}]$ and $[P_{2}]$ into $[S_{1}]=\\{S_{1},P_{1},P_{2}\\}$.
Observing Fig. 8 (b), we have
$P_{3}\in\text{reg}(S_{1},P_{2})=\text{reg}([S_{1}]_{1,2})$. So by condition
(2) of Definition VI.4, $[S_{1}]=\\{S_{1},P_{1},P_{2}\\}$ and
$[P_{3}]=\\{P_{3}\\}$ are connected in $\mathcal{I}_{2}$ and we can obtain a
partition $\mathcal{I}_{3}$ of $\Pi$ by combining
$[S_{1}]=\\{S_{1},P_{1},P_{2}\\}$ and $[P_{3}]=\\{P_{3}\\}$ into
$[S_{1}]=\\{S_{1},P_{1},P_{2},P_{3}\\}$. We can check that no pair of
equivalent classes of $\mathcal{I}_{3}$ are connected.

The above example also gives an illustration of constructing normal partition
of $\Pi$. Let $\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$ be the trivial partition of
$\Pi$. A normal partition of $\Pi$ can be obtained from $\mathcal{I}_{0}$ by a
series of contraction. Specifically, we have the following definition.

######  Definition VI.6 (Normal Partition)

Let $\mathcal{I}_{0},\mathcal{I}_{1},\cdots,\mathcal{I}_{L}=\mathcal{I}_{c}$
be a sequence of partitions of $\Pi$ such that for each
$\ell\in\\{1,\cdots,L\\}$ and $\\{i,j\\}\subseteq\\{1,2,3\\}$,
$[S_{i}]\neq[S_{j}]$ in $\mathcal{I}_{\ell-1}$ and $\mathcal{I}_{\ell}$ is a
contraction of $\mathcal{I}_{\ell-1}$ by combining two connected equivalent
classes. The partition $\mathcal{I}_{c}$ is called a _normal partition_ of
$\Pi$ if one of the following conditions hold:

  * (1)

$[S_{i}]=[S_{j}]$ for some $\\{i,j\\}\subseteq\\{1,2,3\\}$;

  * (2)

No pair of equivalent classes in $\mathcal{I}_{c}$ are connected.

By previous discussion, the partition $\mathcal{I}_{c}$ in Example VI.3 is a
normal partition of $\Pi$. We can also check that the partition
$\mathcal{I}_{c}$ in Example VI.1 is a normal partition of $\Pi$.

Consider the partition $\mathcal{I}_{c}=\\{[S_{1}],[S_{2}]\\}$ in Example
VI.2, where $[S_{1}]=\\{S_{1},P_{1},P_{2},P_{3},S_{3}\\}$ and
$[S_{2}]=\\{S_{2}\\}$. It is easy to check that $\mathcal{I}_{c}$ is obtained
from $\mathcal{I}_{0}$ by a series of contraction by combining two connected
equivalent classes. In this example, we have
$[S_{1}]=\\{S_{1},P_{1},P_{2},P_{3},S_{3}\\}=[S_{3}]$. So $\mathcal{I}_{c}$ is
a normal partition of $\Pi$.

As we have seen in the last subsection, for a feasible code on $\Pi$, the
coding vectors of regions in two connected equivalent classes are determined
by each other. Thus, we can combine such two equivalent classes together.
Specifically, we have the following lemma.

###### Lemma VI.7

Let $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ be a feasible code on $\Pi$ and
$\mathcal{I}_{c}$ be a normal partition of $\Pi$. Then
$d_{Q^{\prime}}\in\langle d_{Q}\rangle$ for any $[R]\in\mathcal{I}_{c}$, any
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and any
$\\{Q,Q^{\prime}\\}\subseteq[R]_{i_{1},i_{2}}$.

###### proof VI.8

The proof is given in Appendix B.

By Definition VI.6, it is easy to check that the following Algorithm 3 outputs
a normal partition of $\Pi$.

Algorithm 3: Partitioning algorithm $(\Pi)$:$L=0$;Whilethere are
$R^{\prime},R^{\prime\prime}\in\mathcal{I}_{L}$ which are connected doLet
$~{}\mathcal{I}_{L+1}~{}$ be a contraction of $~{}\mathcal{I}_{L}~{}$ by
combining $R^{\prime}$and $R^{\prime\prime}$;If$[S_{i}]=[S_{j}]$for some
$\\{i,j\\}\subseteq\\{1,2,3\\}$then$\mathcal{I}_{c}=\mathcal{I}_{L}$;return$\mathcal{I}_{c}$;stop;else$L=L+1$;$\mathcal{I}_{c}=\mathcal{I}_{L}$;return$\mathcal{I}_{c}$;

Clearly, the While-loop of Algorithm 3 has at most $|\mathcal{I}_{0}|=|\Pi|$
rounds. In each round, we need to determine wether there are two connected
equivalent classes, which can be done in time $O(n)$ by Definition VI.4. So
Algorithm 3 can output $\mathcal{I}_{c}$ in $\\{|\Pi|,n\\}$-polynomial time.

Fig 9: An example of infeasible region graph.

We remark that for a given region graph, there could be several normal
partitions of $\Pi$. Consider the region graph in Fig. 9. Let
$\mathcal{I}_{c}=\\{[S_{1}],[S_{3}],[P_{1}]\\}$ such that
$[S_{1}]=\\{S_{1},P_{3}$,
$P_{2},S_{2}\\},[S_{3}]=\\{S_{3}\\},[P_{1}]=\\{P_{1}\\}$ and
$\mathcal{I}_{c}^{\prime}=\\{[S_{1}],[S_{2}],[P_{2}]\\}$ such that
$[S_{1}]=\\{S_{1},P_{3},P_{1},S_{3}\\},[S_{2}]=\\{S_{2}\\},[P_{2}]=\\{P_{2}\\}$.
Then $\mathcal{I}_{c}$ and $\mathcal{I}_{c}^{\prime}$ are both normal
partitions of $\Pi$. However, we will show that to determine whether
$\text{RG}(D^{**})$ is feasible, it is sufficient to construct one normal
partition of $\Pi$ (as Algorithm 3 does).

######  Definition VI.9 (Compatibility)

Suppose $\mathcal{I}=\\{[R_{1}],[R_{2}]$, $[R_{3}],\cdots,[R_{K}]\\}$ is a
partition of $\Pi$. We say that $\mathcal{I}$ is _compatible_ if the following
three conditions hold:

  * (1)

$[S_{i}]\neq[S_{j}]$ for all pair $\\{i,j\\}\subseteq\\{1,2,3\\}$;

  * (2)

No pair of equivalent classes of $\mathcal{I}$ are connected;

  * (3)

$\Lambda_{j}\nsubseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
for all $j\in[n]$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

The following theorem is one of the main results of this section.

###### Theorem VI.10

Let $\mathcal{I}_{c}$ be a normal partition of $\Pi$. Then $\text{RG}(D^{**})$
is feasible if and only if $\mathcal{I}_{c}$ is compatible. Moreover, it is
$\\{|\Pi|,n\\}$-polynomial time complexity to determine whether
$\text{RG}(D^{**})$ is feasible.

By Definition VI.6 and Theorem VI.10, to determine feasibility of
$\text{RG}(D^{**})$, we start with the trivial partition $\mathcal{I}_{0}$ of
$\Pi$ and combine the pair of connected equivalent classes step by step. If
$[S_{i}]=[S_{j}]$ for some $\\{i,j\\}\subseteq\\{1,2,3\\}$ in some step, then
$\text{RG}(D^{**})$ is infeasible. Else, by at most $|\Pi|$ steps, we can
obtain a partition $\mathcal{I}_{c}$ of $\Pi$ satisfying conditions (1), (2)
of Definition VI.9. If $\mathcal{I}_{c}$ further satisfies condition (3) of
Definition VI.9, then $\text{RG}(D^{**})$ is feasible. Otherwise,
$\text{RG}(D^{**})$ is infeasible.

Before proving Theorem VI.10, we first give some lemmas.

###### Lemma VI.11

If $\mathcal{I}$ is a compatible partition of $\Pi$, then we can construct an
$\mathcal{I}$-weak decentralized code on $\Pi$.

###### proof VI.12

Let $\mathcal{I}=\\{[R_{1}],[R_{2}],[R_{3}],\cdots,[R_{K}]\\}$. Then we have
$[R_{j}]_{i_{1},i_{2}}=\text{reg}([R_{j}]_{i_{1},i_{2}})$ for each
$j\in\\{1,2,\cdots,K\\}$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Otherwise, there exists an
$R^{\prime}\in\text{reg}([R_{\ell}]_{i_{1},i_{2}})\backslash[R_{\ell}]_{i_{1},i_{2}}$.
By condition (2) of Definition VI.4, $[R_{\ell}]$ and $[R^{\prime}]$ are
connected, which contradicts to condition (2) of Definition VI.9. Thus,
$\mathcal{I}$ is R-closed and we can construct an $\mathcal{I}$-weak
decentralized code on $\Pi$.

###### Lemma VI.13

If $\mathcal{I}$ is a compatible partition of $\Pi$, then the
$\mathcal{I}$-weak decentralized code is a feasible code on $\Pi$ and
$\text{RG}(D^{**})$ is feasible.

###### proof VI.14

Let $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ be an $\mathcal{I}$-weak
decentralized code on $\Pi$. We need to prove that $\tilde{C}_{\Pi}$ is a
feasible code on $\Pi$. Note that 1), 2) of Theorem V.10 corresponds to (1),
(2) of Definition IV.11 respectively. So we only need to prove that
$\tilde{C}_{\Pi}$ satisfies condition (3) of Definition IV.11, i.e.,
$\bar{\alpha}\in\langle d_{R};R\in\Lambda_{j}\rangle$ for all $j\in[n]$. We
have the following two cases:

Case 1: There is an $[R_{\ell}]\in\mathcal{I}_{c}$ such that $\Lambda_{j}$
intersects with at least two different subclasses of $[R_{\ell}]$. Suppose
$\\{Q,Q^{\prime}\\}\subseteq\Lambda_{j}$ and $Q,Q^{\prime}$ belong to two
different subclasses of $[R_{\ell}]$. By 3) of Theorem V.10,
$\bar{\alpha}\in\langle d_{Q},d_{Q^{\prime}}\rangle\subseteq\langle
d_{R};R\in\Lambda_{j}\rangle$.

Case 2: For each $[R_{\ell}]\in\mathcal{I}$, $\Lambda_{j}$ intersects with at
most one subclass of $[R_{\ell}]$. Then by condition (2) of Definition VI.9
and condition (1) of Definition VI.4, $\Lambda_{j}$ intersects with at least
three equivalent classes in $\mathcal{I}$. Moreover, by condition (3) of
Definition VI.9,
$\Lambda_{j}\nsubseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Then by Definition V.8, we
can find a subset $\\{Q,Q^{\prime},Q^{\prime\prime}\\}\subseteq\Lambda_{j}$
such that $\\{Q,Q^{\prime},Q^{\prime\prime}\\}$ is an
$\mathcal{I}$-independent set. By 4) of Theorem V.10, $\bar{\alpha}\in\langle
d_{Q},d_{Q^{\prime}},d_{Q^{\prime\prime}}\rangle\subseteq\langle
d_{R};R\in\Lambda_{j}\rangle$.

By the above discussion, $\tilde{C}_{\Pi}$ satisfies conditions (1)-(3) of
Definition IV.11. So $\tilde{C}_{\Pi}$ is a feasible code on $\Pi$.

Now we can prove Theorem VI.10.

######  proof VI.15 (Proof of Theorem VI.10)

If $\mathcal{I}_{c}$ is compatible, then by Lemma VI.13, $\text{RG}(D^{**})$
is feasible.

Conversely, suppose $\text{RG}(D^{**})$ is feasible. By Theorem IV.12, there
is a feasible code $\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ on
$\Pi$. We shall prove $\mathcal{I}_{c}$ satisfies conditions (1)-(3) of
Definition VI.9.

For $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, if $[S_{i_{1}}]=[S_{i_{2}}]$,
then $S_{i_{1}}\in[S_{i_{2}}]$. By Definition III.5 and Lemma VI.7,
$d_{S_{i_{1}}}=\alpha_{i_{1}}\in\langle
d_{S_{i_{2}}}\rangle=\langle\alpha_{i_{2}}\rangle$, a contradiction. So
$[S_{i_{1}}]\neq[S_{i_{2}}]$ for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Moreover, by Definition VI.6, no pair of equivalent classes of
$\mathcal{I}_{c}$ are connected. Thus, $\mathcal{I}_{c}$ satisfies conditions
(1), (2) of Definition VI.9.

We can prove condition (3) by contradiction. Suppose
$\Lambda_{j}\subseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
for some $j\in[n]$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. By Lemma VI.7
and (V.2), we have

$d_{Q}\in\langle d_{S_{i_{1}}}\rangle=\langle\alpha_{i_{1}}\rangle,\forall
Q\in[S_{i_{1}}]_{i_{1}}$

and

$d_{Q}\in\langle d_{S_{i_{2}}}\rangle=\langle\alpha_{i_{2}}\rangle,\forall
Q\in[S_{i_{2}}]_{i_{2}}.$

Moreover, since $\tilde{C}_{\Pi}$ is a feasible code on $\Pi$, by 1) of Lemma
IV.15, we have $d_{Q}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall
Q\in\text{reg}(S_{i_{1}},S_{i_{2}})$. Since we assume
$\Lambda_{j}\subseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$,
then $d_{Q}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$ for all
$Q\in\Lambda_{j}$ and by condition (3) of Definition IV.11,
$\bar{\alpha}=\alpha_{1}+\alpha_{2}+\alpha_{3}\in\langle
d_{Q};Q\in\Lambda_{j}\rangle=\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$, a
contradiction. So
$\Lambda_{j}\nsubseteq[S_{i_{1}}]_{i_{1}}\bigcup[S_{i_{2}}]_{i_{2}}\bigcup\text{reg}(S_{i_{1}},S_{i_{2}})$
and $\mathcal{I}_{c}$ satisfies condition (3) of Definition VI.9.

By the above discussion, $\mathcal{I}_{c}$ is compatible. Finally, we prove
the time complexity. We have seen that Algorithm 3 can output
$\mathcal{I}_{c}$ in $\\{|\Pi|,n\\}$-polynomial time. Moreover, it is easy to
see that conditions (1)-(3) of Definition VI.9 can be checked in time $O(n)$.
Thus, it is $\\{|\Pi|,n\\}$-polynomial time complexity to determine whether of
$\text{RG}(D^{**})$ is feasible.

###  VI-C Some Simple Cases of Three-source Sum-network

The following theorem gives some families of terminal-separable region graph
that is feasible.

###### Theorem VI.16

Suppose $\text{RG}(D^{**})$ is terminal-separable. Then it is feasible if one
of the following conditions hold:

  * (1)

$\Lambda_{j_{1}}\cap\Lambda_{j_{2}}=\emptyset$ for all pair
$\\{j_{1},j_{2}\\}\subseteq[n]$ such that
$|\Lambda_{j_{1}}|=|\Lambda_{j_{2}}|=2$.

  * (2)

$\Lambda_{j}\subseteq\Pi\backslash\\{S_{1},S_{2},S_{3}\\}$ for all $j\in[n]$.

  * (3)

There is an $\\{\ell^{\prime},\ell^{\prime\prime}\\}\subseteq\\{1,2,3\\}$ such
that for all $j\in[n]$,
$\Lambda_{j}\cap\text{reg}^{\circ}(S_{\ell^{\prime}},S_{\ell^{\prime\prime}})\neq\emptyset$.

  * (4)

$n\leq 2$.

###### proof VI.17

1) Suppose condition (1) holds. Let $A$ be the subset of $[n]$ such that
$|\Lambda_{j}|=2$ for all $j\in A$ and $|\Lambda_{j}|>2$ for all
$j\in[n]\backslash A$. Let $\mathcal{I}=\\{\Lambda_{j};j\in
A\\}\cup\\{[R];R\in\Pi\backslash(\cup_{j\in A}\Lambda_{j})\\}$, where
$[R]=\\{R\\}$ for all $R\in\Pi\backslash(\cup_{j\in A}\Lambda_{j})$. Then for
each $j\in A$, $\Lambda_{j}$ is an equivalent class and for each
$R\in\Pi\backslash(\cup_{j\in A}\Lambda_{j})$, $\\{R\\}$ is an equivalent
class. By Definition VI.9, $\mathcal{I}$ is compatible. By Lemma VI.13,
$\text{RG}(D^{**})$ is feasible. Fig. 10 is an example of such region graph
and feasible code.

2) Suppose condition (2) holds. Let $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}]$,
$[R]\\}$, where $[S_{i}]=\\{S_{i}\\}$ for $i\in\\{1,2,3\\}$ and
$[R]=\Pi\backslash\\{S_{1},S_{2},S_{3}\\}$. Then by Definition VI.9,
$\mathcal{I}$ is compatible. By Lemma VI.13, $\text{RG}(D^{**})$ is feasible.
Fig. 11 (a) is an example of such region graph and feasible code.

3) Suppose condition (3) holds. Without loss of generality, assume
$\ell=1,\ell^{\prime}=2$ and $\ell^{\prime\prime}=3$. Let
$\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}]\\}$, where
$[S_{1}]=\Pi\backslash\\{S_{2},S_{3}\\}$, $[S_{2}]=\\{S_{2}\\}$ and
$[S_{3}]=\\{S_{3}\\}$. Then by Definition VI.9, $\mathcal{I}$ is compatible.
So by Lemma VI.13, $\text{RG}(D^{**})$ is feasible. Fig. 11 (b) is an example
of such region graph and feasible code.

4) Suppose condition (4) holds. If $n=1$, the conclusion is trivial. So we
assume $n=2$. We have the following three cases:

Case 1: $|\Lambda_{1}|>2$ or $|\Lambda_{2}|>2$. In this case, the condition
(1) holds and by proved result, $\text{RG}(D^{**})$ is feasible.

Case 2: $|\Lambda_{1}|=|\Lambda_{2}|=2$ and
$\Lambda_{1}\cap\Lambda_{2}=\emptyset$. In this case, the condition (1) holds
and by proved result, $\text{RG}(D^{**})$ is feasible.

Case 3: $|\Lambda_{1}|=|\Lambda_{2}|=2$ and
$\Lambda_{1}\cap\Lambda_{2}\neq\emptyset$. If $\Lambda_{1}=\Lambda_{2}$, then
the conclusion is trivial. So we assume $\Lambda_{1}\neq\Lambda_{2}$. Thus, we
can assume $\Lambda_{1}=\\{Q_{1},Q_{2}\\}$ and
$\Lambda_{2}=\\{Q_{1},Q_{3}\\}$. We have the following two subcases:

Case 3.1: $Q_{1}=S_{i}$ for some $i\in\\{1,2,3\\}$. Without loss of
generality, assume $Q_{1}=S_{1}$. By 2) of Lemma IV.9,
$\\{Q_{1},Q_{2}\\}=\Lambda_{1}\nsubseteq\text{reg}(S_{1},S_{2})$ and
$\\{Q_{1},Q_{2}\\}=\Lambda_{1}\nsubseteq\text{reg}(S_{1},S_{3})$. Then we have
$Q_{2}\in\text{reg}^{\circ}(S_{2},S_{3})$. Similarly, we have
$Q_{3}\in\text{reg}^{\circ}(S_{2},S_{3})$. So condition (3) holds and by the
proved result, $\text{RG}(D^{**})$ is feasible.

Case 3.2: $Q_{1}\neq S_{i}$ for all $i\in\\{1,2,3\\}$. Then
$Q_{1}\in\text{reg}^{\circ}(S_{i_{1}},S_{i_{2}})$ for some
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. So condition (3) holds and by the
proven result, $\text{RG}(D^{**})$ is feasible.

###### Remark VI.18

We remark that if the number of different subsets in
$\\{\Lambda_{1},\Lambda_{2},\cdots,\Lambda_{n}\\}$ is at most $2$, then we can
still construct a feasible code on $\Pi$. So $\text{RG}(D^{**})$ is still
feasible.

For example, if $\\{\Lambda_{1}\neq\Lambda_{2}=\cdots=\Lambda_{n}\\}$. Then
consider the subgraph $\text{RG}(D^{**})^{\prime}$ formed by
$\Pi\cup\Omega_{1}\cup\Omega_{2}$. By (4) of Theorem VI.16,
$\text{RG}(D^{**})^{\prime}$ is feasible. So by Theorem IV.12, there exists a
feasible code on $\Pi$. Again by Theorem IV.12, $\text{RG}(D^{**})$ is
feasible.

Fig 10: An example of weak decentralized code: (a) is a region graph with
$\Pi=\\{S_{1},S_{2},S_{3},Q_{1},R_{1},Q_{2},W,P,R_{2}\\}$ and
$\Lambda_{1}=\\{\\{S_{2},P\\},\Lambda_{2}=\\{W,P,R_{2}\\}$,
$\Lambda_{3}=\\{Q_{1},Q_{2}\\},\Lambda_{4}=\\{R_{1},R_{2}\\}$. Let
$\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],[Q_{1}],[R_{1}],[W]\\}$, where
$[S_{1}]=\\{S_{1}\\}$, $[S_{2}]=\\{S_{2},P\\}$, $[S_{3}]=\\{S_{3}\\}$,
$[Q_{1}]=\\{Q_{1},Q_{2}\\}$, $[R_{1}]=\\{R_{1},R_{2}\\}$ and $[W]=\\{W\\}$.
Then $\mathcal{I}$ is compatible. (b) illustrates the $\mathcal{I}$-weak
decentralized code, where
$\mathcal{B}_{1}=\\{\beta^{(1)}_{1},\beta^{(1)}_{2,3}\\},\cdots,\mathcal{B}_{6}=\\{\beta^{(6)}_{1,2},\beta^{(6)}_{1,3},\beta^{(6)}_{2,3}\\}$
are as in Lemma V.3.

Fig 11: Examples of weak decentralized code: In (a),
$\Lambda_{j}\subseteq\Pi\backslash\\{S_{1},S_{2},S_{3}\\}$ for
$j\in\\{1,2,3\\}$; In (b),
$\Lambda_{j}\cap\text{reg}^{\circ}(S_{2},S_{3})\neq\emptyset,j=1,2,3$.

As a simple corollary of (4) of Theorem VI.16, we can characterize solvability
of $3$s$/2$t sum-network (not necessarily terminal-separable) as follows.

###### Corollary VI.19

If $G$ is a $3$s$/2$t sum-network, then the basic region graph
$\text{RG}(D^{**})$ is feasible.

###### proof VI.20

Since $G$ is a $3$s$/2$t sum-network, then $\text{RG}(D^{**})$ has at most two
terminal regions. If $\text{RG}(D^{**})$ has only one terminal region, then
clearly, it is feasible. So we assume that $\text{RG}(D^{**})$ has two
terminal regions, say $T_{1}$ and $T_{2}$. Then we have the following two
cases:

Case 1: $\Omega_{1,2}\neq\emptyset$. Pick a $P\in\Omega_{1,2}$. By (2) of
Definition IV.1, $P\in D^{**}\backslash\Pi$. Then by Lemma IV.5,
$S_{i}\rightarrow P$ for all $i\in\\{1,2,3\\}$ and by Lemma III.19, the sum
$\sum_{i=1}^{3}X_{i}$ can be transmitted from $\\{S_{1},S_{2},S_{3}\\}$ to
$P$. Moreover, by (2) of Definition IV.1, we have $P\rightarrow T_{j},j=1,2$.
So by Lemma III.13, $\text{RG}(D^{**})$ is feasible.

Case 2: $\Omega_{1,2}=\emptyset$. Then $\text{RG}(D^{**})$ is terminal
separable and by (4) of Theorem VI.16, $\text{RG}(D^{**})$ is feasible.

By the above discussion, $\text{RG}(D^{**})$ is feasible.

Recall that in this paper we assumed $S_{i}\rightarrow T_{j}$ for all
$i\in\\{1,2,3\\}$ and $j\in[n]$ (Assumption 2). On the other hand, if
$S_{i}\nrightarrow T_{j}$ for some $i\in\\{1,2,3\\}$ and $j\in[n]$, then
clearly $\text{RG}(D^{**})$ is infeasible. So by Corollary VI.19, a $3$s$/2$t
sum-network is feasible if and only if each source-terminal pair is connected,
which is a special case of the result of [12].

When $n=3$, we can give a graph theoretic characterization for feasibility of
$\text{RG}(D^{**})$.

###### Theorem VI.21

Suppose $\text{RG}(D^{**})$ is terminal separable and has three terminal
regions. Then $\text{RG}(D^{**})$ is infeasible if and only if by proper
naming, the following condition (C-IR) hold:
(C-IR) There is a $P_{1}\in\text{reg}^{\circ}(S_{2},S_{3})$ and a
$P_{2}\in\text{reg}^{\circ}(S_{1},S_{2})$ such that
$\Lambda_{1}=\\{S_{1},P_{1}\\},\Lambda_{2}=\\{P_{1},P_{2}\\}$ and
$\Lambda_{3}\subseteq\text{reg}(S_{1},P_{2})\cup\text{reg}(S_{1},S_{3})$.

###### proof VI.22

The proof is given in Appendix C.

A new characterization on the solvability of a $3$s$/3$t sum-network $G$ (not
necessarily terminal-separable) can be derived as a corollary of Theorem
VI.21.

###### Corollary VI.23

For a $3$s$/3$t sum-network $G$, $\text{RG}(D^{**})$ is infeasible if and only
if it is terminal separable and satisfies condition (C-IR).

###### proof VI.24

Since $G$ is a $3$s$/3$t sum-network, then $\text{RG}(D^{**})$ has at most $3$
terminal regions. If $\text{RG}(D^{**})$ has at most two terminal regions,
then by Corollary VI.19, it is feasible. So we assume $\text{RG}(D^{**})$ has
three terminal regions. Then one of the following three cases holds:

Case 1: $\Omega_{1,2,3}\neq\emptyset$. Pick a $P\in\Omega_{1,2,3}$. As in the
proof of Corollary VI.19, the sum $\sum_{i=1}^{3}X_{i}$ can be transmitted
from $\\{S_{1},S_{2},S_{3}\\}$ to $P$. Moreover, by (2) of Definition IV.1, we
have $P\rightarrow T_{j},j=1,2,3$. So by Lemma III.13, $\text{RG}(D^{**})$ is
feasible.

Case 2: $\Omega_{1,2,3}=\emptyset$ and $\Omega_{i_{1},i_{2}}\neq\emptyset$ for
some $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Pick a
$Q\in\Omega_{i_{1},i_{2}}$. By Corollary VI.19, the sum $\sum_{i=1}^{3}X_{i}$
can be transmitted from $\\{S_{1},S_{2},S_{3}\\}$ to $\\{Q,T_{i_{3}}\\}$
simultaneously, where $\\{i_{3}\\}=\\{1,2,3\\}\backslash\\{i_{1},i_{2}\\}$.
Moreover, by (2) of Definition IV.1, $P\rightarrow T_{j},j=i_{1},i_{2}$. So by
Lemma III.13, $\text{RG}(D^{**})$ is feasible.

Case 3: $\text{RG}(D^{**})$ is terminal separable. By Theorem VI.21,
$\text{RG}(D^{**})$ is infeasible if and only if the condition (C-IR) holds.

By the above discussion, $\text{RG}(D^{**})$ is infeasible if and only if it
is terminal separable and satisfies condition (C-IR).

Fig. 8 are two examples of infeasible region graph with three source regions
and three terminal regions.

The first necessary and sufficient condition for solvability of $3$s$/3$t sum-
network is given by Shenvi and Dey [18, Th.1]. We remark that the conditions
in [18] can be easily derived from Corollary VI.23. In fact, by interchanging
the name of $S_{2}$ and $S_{3}$ and replacing the name of $T_{1},T_{2},T_{3}$
by $T_{2},T_{3},T_{1}$ respectively, condition (C-IR) can be restated as
(C-IR′) There is a $P_{1}\in\text{reg}^{\circ}(S_{2},S_{3})$ and a
$P_{2}\in\text{reg}^{\circ}(S_{1},S_{3})$ such that
$\Lambda_{2}=\\{S_{1},P_{1}\\},\Lambda_{3}=\\{P_{1},P_{2}\\}$ and
$\Lambda_{1}\subseteq\text{reg}(S_{1},P_{2})\cup\text{reg}(S_{1},S_{2})$.
Let $e_{1}=\text{lead}(P_{2})$ and $e_{2}=\text{lead}(P_{1})$. Then we can
check that $e_{1},e_{2}$ satisfy the conditions 1)$-$6) of [18, Th.1].

For example, for the network in Fig. 2 (a), its basic region graph is in Fig.
3 (a) and satisfies the condition (C-IR′). Let
$e_{1}=\text{lead}(P_{2})=(v_{1},v_{3})$ and
$e_{2}=\text{lead}(P_{1})=(v_{2},v_{4})$. Then $e_{1},e_{2}$ satisfy the
conditions 1)$-$6) of [18, Th.1].

Similarly, for the network in Fig. 2 (b), its basic region graph is in Fig. 3
(b) and satisfies the condition (C-IR′). Let
$e_{1}=\text{lead}(P_{2})=(v_{1},v_{4})$ and
$e_{2}=\text{lead}(P_{1})=(v_{3},v_{5})$. Then $e_{1},e_{2}$ satisfy the
conditions 1)$-$6) of [18, Th.1].

Note that by Theorem III.9, the basic region graph $\text{RG}(D^{**})$ can be
obtained in time $O(|E|)$. Moreover, by Theorem IV.3, it is $O(|D^{**}|)$ time
complexity to determine whether $\text{RG}(D^{**})$ is terminal-separable. So
by Corollary VI.23, it is $O(|E|)$ time complexity to determine solvability of
a $3$s$/3$t sum-network, where $E$ is the link set. However, by [18, Th.1], it
needs $O(|E|^{3})$ time complexity. Thus, our result gives a faster method to
determine solvability of $G$.

##  VII Conclusions and Discussions

We investigated the network coding problem of $3$s$/n$t sum-network. We
obtained a computationally simple sufficient and necessary condition for
solvability of a class of $3$s$/n$t sum-network by developing the region
decomposition method in [22, 23] and generalizing the decentralized coding
method in [21]. The condition was characterized by some simple structural
properties of some certain partitions on a part of the region graph and also
can be judged using a very simple polynomial time algorithm. As a result, the
solvability of $3$s$/3$t sum-networks was characterized by using a single
forbidden structure. Our method can further develop a completely
characterization on the solvability of $3$s$/4$t sum-networks. Limited by the
space, we leave it to a future paper.

## References

  * [1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” _IEEE Trans. Inf. Theory_ , vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
  * [2] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” _IEEE Trans. Inf. Theory_ , vol. 49, no. 2, pp. 371-381, Feb. 2003\.
  * [3] J. Korner and K. Marton, “How to encode the modulo-two sum of binary sources,” _IEEE Trans. Inf. Theory_ , vol. 25, no. 2, pp. 219-221, 1979.
  * [4] R. G. Gallager, “Finding parity in a simple broadcast network,” _IEEE Trans. Inf. Theory_ , vol. 34, pp. 176-180, 1988.
  * [5] A. Orlitsky and J. R. Roche, “Coding for computing,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 3, pp. 903-917, 2001.
  * [6] H. Feng, M. Effros and S. A. Savari, “Functional source coding for networks with receiver side information,” in _Proc. Allerton Conf. Commun., Contr., Comput._ , Sep. 2004.
  * [7] A. Giridhar and P. R. Kumar, “Computing and communicating functions over sensor networks,” _IEEE J. Select. Areas Commun._ , vol. 23, no. 4, pp. 755-764, 2005.
  * [8] Y. Kanoria and D. Manjunath, “On distributed computation in noisy random planar networks,” in _Proc. ISIT_ , Nice, France, 2008\.
  * [9] R. Appuswamy, M. Franceschetti, N. Karamchandani and K. Zeger, “Network computing capacity for the reverse butterfly network,” in _Proc ISIT_ , Seoul, Korea, 2009.
  * [10] R. Appuswamy, M. Franceschetti, N. Karamchandani and K. Zeger, “Network coding for computing: cut-set bounds,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 2, pp. 1015-1030, Feb. 2011.
  * [11] S. Kannan and P. Viswanath, “Multi-session function computation and multicasting in undirected graphs,” _IEEE J. Select. Areas Commun._ , vol. 31, no. 4, pp. 702-713, 2013.
  * [12] A. Ramamoorthy, “Communicating the sum of sources over a network,” in _Proc ISIT_ , Toronto, Canada, July 06-11, pp. 1646-1650, 2008.
  * [13] B. K. Rai, B. K. Dey, and A. Karandikar, “Some results on communicating the sum of sources over a network,” in _Proc NetCod_ 2009\.
  * [14] B. K. Rai and B. K. Dey, “Feasible alphabets for communicating the sum of sources over a network,” in _Proc ISIT_ , Seoul, Korea, 2009.
  * [15] M. Langberg and A. Ramamoorthy, “Communicating the sum of sources in a 3-sources/3-terminals network,” in _Proc ISIT_ , Seoul, Korea, 2009.
  * [16] M. Langberg and A. Ramamoorthy, “Communicating the sum of sources in a 3-sources/3-terminals network; revisited,” in _Proc ISIT_ , Austin, Texas, U.S.A, 2010.
  * [17] B. K. Rai, B. K. Dey, and S. Shenvi, “Some bounds on the capacity of communicating the sum of sources,” in _Proc IEEE Information Theory Workshop_ , 2010.
  * [18] S. Shenvi and B. K. Dey, “A necessary and sufficient condition for solvability of a 3s/3t sum-network,” in _Proc ISIT_ , Texas, U.S.A, 2010.
  * [19] B. K. Rai and B. K. Dey, “On Network Coding for Sum-Networks,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 1, pp. 50-63, Jan. 2012\.
  * [20] B. K. Rai and N. Das, “Sum-Networks: Min-Cut=2 Does Not Guarantee Solvability,” _IEEE Communications Letters_ , vol. 17, no. 11, pp. 2144-2147, Nov. 2013.
  * [21] C. Fragouli and E. Soljanin,“Information flow decomposition for network coding,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 3, pp. 829-848, Mar. 2006.
  * [22] W. Song, K. Cai, R. Feng and C. Yuen, “The Complexity of Network Coding With Two Unit-Rate Multicast Sessions,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 9, pp. 5692-5707, Sept. 2013.
  * [23] W. Song, R. Feng, K. Cai and J. Zhang, “Network Coding for 2-unicast with Rate (1,2)” in _Proc. ISIT_ , Boston, 2012.

##  Appendix A Proof of Lemma V.3

######  proof A.1 (Proof of Lemma V.3)

Clearly, when $K=3$, the sets
$\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}$ satisfy properties (1)$-$(4)
of Lemma V.3.

Now suppose $K>3$ and the sets $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1}$
satisfy properties (1)$-$(4). We want to construct a subset
$\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2},\beta^{(K)}_{1,3},\beta^{(K)}_{2,3}\\}$
such that the sets $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$
satisfy properties (1)$-$(4). The key is to carefully choose a vector
$\beta^{(K)}\in\mathbb{F}^{3}\backslash\langle\bar{\alpha}\rangle$ and let
$0\neq\beta^{(K)}_{i_{1},i_{2}}\in\langle\beta^{(K)},\bar{\alpha}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for each $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

Let $\Phi_{K-1}$ be the set of all pairs
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$
such that
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Note that
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1}$ satisfy property (3) of Lemma V.3.
Then $\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly independent.
So $\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle$ is an $2$-dimensional
subspace of $\mathbb{F}^{3}$ and
$\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle\neq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$.
Thus,
$\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
is an $1$-dimensional subspace of $\mathbb{F}^{3}$. Let

$\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{i_{1},i_{2}}=\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$

and let

$\displaystyle\Psi_{K-1}=\bigcup_{\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\in\Phi_{K-1}}\\{\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,2},\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,3},\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{2,3}\\}.$

Then
$\Psi_{K-1}\subseteq\langle\alpha_{1},\alpha_{2}\rangle\cup\langle\alpha_{1},\alpha_{3}\rangle\cup\langle\alpha_{2},\alpha_{3}\rangle$.
Since $\mathbb{F}$ is sufficiently large, there exists a
$\beta^{(K)}\in\mathbb{F}^{3}$ such that
$\beta^{(K)}\notin\langle\bar{\alpha},\gamma\rangle$ for all
$\gamma\in\Psi_{K-1}$. Then we have

$\displaystyle\gamma\notin\langle\bar{\alpha},\beta^{(K)}\rangle,~{}\forall\gamma\in\Psi_{K-1}.$
(A.1)

For each $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, let

$\displaystyle
0\neq\beta^{(K)}_{i_{1},i_{2}}\in\langle\beta^{(K)},\bar{\alpha}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle.$
(A.2)

Let $\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2}$, $\beta^{(K)}_{1,3}$,
$\beta^{(K)}_{2,3}\\}$. We shall prove
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfy properties
(1)$-$(4) of Lemma V.3.

By (A.2),
$\beta^{(K)}_{i_{1},i_{2}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$ for
all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. So
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfy property
(1).

By assumption, $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1}$ satisfy property (2)
of Lemma V.3, then for any $\ell\in\\{1,\cdots,K-1\\}$ and
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\mathcal{B}_{\ell}$, the
pair $\\{\gamma^{\prime},\gamma^{\prime\prime}\\}$ is in $\Phi_{K-1}$.
Moreover, since $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1}$ satisfy property
(1) of Lemma V.3, then
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\mathcal{B}_{\ell}\subseteq\langle\alpha_{1},\alpha_{2}\rangle\cup\langle\alpha_{1},\alpha_{3}\rangle\cup\langle\alpha_{2},\alpha_{3}\rangle$.
So
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\\{\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,2}$,
$\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,3}$,
$\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{2,3}\\}$. Thus,
$\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}\subseteq\Psi_{K-1}$ and by (A.1),

$\displaystyle\gamma\notin\langle\beta^{(K)},\bar{\alpha}\rangle,~{}\forall\gamma\in\textstyle{\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}}.$
(A.3)

Note that $\alpha_{i}\in\mathcal{B}_{i},i=1,2,3$. Then
$\alpha_{i}\notin\langle\beta^{(K)},\bar{\alpha}\rangle,i=1,2,3$. So by (A.2),
$\beta^{(K)}_{1,2}$, $\beta^{(K)}_{1,3}$ and $\beta^{(K)}_{2,3}$ are mutually
linearly independent and $\bar{\alpha}\in\langle\gamma,\gamma^{\prime}\rangle$
for all $\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{K}$. Thus,
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfy property
(2).

Now, we prove that $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$
satisfy property (4). Suppose
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$
such that
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\neq\\{\beta^{(\ell)}_{1,2}$,
$\beta^{(\ell)}_{1,3}$, $\beta^{(\ell)}_{2,3}\\}$ for all
$\ell\in\\{4,\cdots,K\\}$. We have the following three cases:

Case 1:
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$.
By induction assumption, $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$
are linearly independent.

Case 2:
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$
and $\gamma\in\mathcal{B}_{K}$. We have the following two subcases:

Case 2.1:
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for some $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. By assumption of
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}$, we have
$\gamma\notin\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$. So
$\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly independent.

Case 2.2:
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Then the pair
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}$ is in the set $\Phi_{K-1}$ and
$\gamma^{\prime},\gamma^{\prime\prime}$ are linearly independent. Note that
$\gamma\in\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2}$,
$\beta^{(K)}_{1,3},\beta^{(K)}_{2,3}\\}$. Then by (A.2),
$\gamma\in\langle\alpha_{1},\alpha_{2}\rangle\cup\langle\alpha_{1},\alpha_{3}\rangle\cup\langle\alpha_{2},\alpha_{3}\rangle$.
So $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly
independent. Otherwise, we have
$\gamma\in\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle$ and
$\gamma\in\\{\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,2},\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{1,3},\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle_{2,3}\\}\subseteq\Psi_{K-1}$.
By (A.2), $\gamma\in\langle\bar{\alpha},\beta^{(K)}\rangle$, which contradicts
to (A.1).

Case 3: $\gamma^{\prime\prime}\in\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$ and
$\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{K}$. Then by the proven
result, $\gamma$ and $\gamma^{\prime}$ are linearly independent. So by (A.2),
$\langle\beta^{(K)},\bar{\alpha}\rangle=\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle$.
From (A.3), we have
$\gamma\notin\langle\beta^{(K)},\bar{\alpha}\rangle=\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle$.
Thus, $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly
independent.

In all cases, $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are
linearly independent. Thus, $\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$ satisfies
condition (4).

Clearly, if $\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfy
property (4), then for any
$\\{\gamma,\gamma^{\prime}\\}\subseteq\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$,
we can always find a vector
$\gamma^{\prime\prime}\in\bigcup_{\ell=1}^{K}\mathcal{B}_{\ell}$ such that
$\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly independent.
So $\gamma$ and $\gamma^{\prime}$ are linearly independent and
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfy property
(3).

Thus, we can always find $K$ sets
$\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}$ satisfying
properties (1)$-$(4) of Lemma V.3 for all $K\geq 3$.

We give an example of the above construction. For simplicity, we let
$\mathbb{F}=GF(p)$ for a sufficiently large prime $p$.

When $K=4$, we have
$\bigcup_{\ell=1}^{K-1}\mathcal{B}_{\ell}=\\{\alpha_{1},\alpha_{2}+\alpha_{3},\alpha_{2},\alpha_{1}+\alpha_{3},\alpha_{3},\alpha_{1}+\alpha_{2}\\}$.
So
$\Phi_{3}=\\{\\{\alpha_{1},\alpha_{2}+\alpha_{3}\\},\\{\alpha_{2},\alpha_{1}+\alpha_{3}\\},\\{\alpha_{3},\alpha_{1}+\alpha_{2}\\},\\{\alpha_{1}+\alpha_{2},\alpha_{1}+\alpha_{3}\\},\\{\alpha_{1}+\alpha_{2},\alpha_{2}+\alpha_{3}\\},\\{\alpha_{1}+\alpha_{3},\alpha_{2}+\alpha_{3}\\}\\}$.
Correspondingly, we have
$\Psi_{3}=\\{\langle\alpha_{1}\rangle,\langle\alpha_{2}+\alpha_{3}\rangle\\}\cup\\{\langle\alpha_{2}\rangle,\langle\alpha_{1}+\alpha_{3}\rangle\\}\cup\\{\langle\alpha_{3}\rangle,\langle\alpha_{1}+\alpha_{2}\rangle\\}\cup\\{\langle\alpha_{1}+\alpha_{2}\rangle,\langle\alpha_{1}+\alpha_{3}\rangle,\langle\alpha_{2}-\alpha_{3}\rangle\\},\\{\langle\alpha_{1}+\alpha_{2}\rangle,\langle\alpha_{2}+\alpha_{3}\rangle,\langle\alpha_{1}-\alpha_{3}\rangle\\},\\{\langle\alpha_{1}+\alpha_{3}\rangle,\langle\alpha_{2}+\alpha_{3}\rangle,\langle\alpha_{1}-\alpha_{2}\rangle\\}\\}$.
Let $\beta^{(4)}=\alpha_{1}+3\alpha_{2}$. Then $\beta^{(4)}$ satisfies (A.1).
By (A.2), we have $\beta^{(4)}_{1,2}=\alpha_{1}+3\alpha_{2}$,
$\beta^{(4)}_{1,3}=2\alpha_{1}+3\alpha_{3}$ and
$\beta^{(4)}_{2,3}=2\alpha_{2}-\alpha_{3}$. So we can obtain
$\mathcal{B}_{4}=\\{\alpha_{1}+3\alpha_{2},2\alpha_{1}+3\alpha_{3},2\alpha_{2}-\alpha_{3}\\}$.
Similarly, we can construct
$\mathcal{B}_{5}=\\{2\alpha_{1}+3\alpha_{2},\alpha_{1}+3\alpha_{3},\alpha_{2}-2\alpha_{3}\\}$
(See Example V.5.), and so on.

##  Appendix B Proof of Lemma VI.7

In what follows, we suppose
$\tilde{C}_{\Pi}=\\{d_{R}\in\mathbb{F}^{3};R\in\Pi\\}$ is a feasible code on
$\Pi$. By Remark IV.14, we can assume that $d_{R}\neq 0$ for all $R\in\Pi$.

To prove Lemma VI.7, the key is to prove that all equivalent class
$[R]\in\mathcal{I}_{c}$ satisfies the following property:
(P1) : For any pair $\\{Q,Q^{\prime}\\}\subseteq[R]$,
$d_{Q^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$.

To prove this, we first prove three lemmas.

###### Lemma B.1

Let $\mathcal{I}$ be a partition of $\Pi$ and $[R]\in\mathcal{I}$ satisfying
(P1). Then for any $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and any pair
$\\{Q,Q^{\prime}\\}\subseteq[R]_{i_{1},i_{2}}$, $d_{Q^{\prime}}\in\langle
d_{Q}\rangle$. Moreover, for any subclass $[[R]]$ of $[R]$ and any pair
$\\{Q,Q^{\prime}\\}\subseteq[[R]]$, $d_{Q^{\prime}}\in\langle d_{Q}\rangle$.

###### proof B.2

By (V.1),
$\\{Q,Q^{\prime}\\}\subseteq[R]_{i_{1},i_{2}}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$.
So by 1) of Lemma IV.15,
$d_{Q},d_{Q^{\prime}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$.
Meanwhile, since $[R]\in\mathcal{I}$ satisfies (P1), then
$d_{Q^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$. So
$d_{Q^{\prime}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle\cap\langle
d_{Q},\bar{\alpha}\rangle=\langle d_{Q}\rangle$ and the first claim is true.

Now, we prove the second claim. Suppose $\\{Q,Q^{\prime}\\}\subseteq[[R]]$. If
$[R]\neq[S_{i}]$ for all $i\in\\{1,2,3\\}$, then by Definition V.1,
$[[R]]=[R]_{i_{1},i_{2}}$ for some $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and
by the proven result, $d_{Q^{\prime}}\in\langle d_{Q}\rangle$. If
$[R]=[S_{i}]$ for some $i\in\\{1,2,3\\}$, then by Definition V.1, we have the
following two cases:

Case 1: $[[R]]=[S_{i}]_{i}$. By (V.1) and (V.2),
$[[R]]=[S_{i}]_{i,j_{1}}\cup[S_{i}]_{i,j_{2}}$, where
$\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. By the proven result, we
have $\alpha_{i}=d_{S_{i}}\in\langle d_{Q}\rangle$ and
$d_{Q^{\prime}}\in\langle d_{S_{i}}\rangle$. So $d_{Q^{\prime}}\in\langle
d_{Q}\rangle$.

Case 2: $[[R]]=[S_{i}]_{j_{1},j_{2}}$, where
$\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. By the proven result, we
have $d_{Q^{\prime}}\in\langle d_{Q}\rangle$.

In both cases, we have $d_{Q^{\prime}}\in\langle d_{Q}\rangle$, which proves
the second claim.

###### Lemma B.3

Let $\mathcal{I}$ be a partition of $\Pi$ and
$\\{[R^{\prime}],[R^{\prime\prime}]\\}\subseteq\mathcal{I}$ such that
$[R^{\prime}]$ and $[R^{\prime\prime}]$ satisfy (P1). If there is a $j\in[n]$
such that $\Lambda_{j}\subseteq[[R^{\prime}]]\cup[[R^{\prime\prime}]]$, where
$[[R^{\prime}]]~{}($resp. $[[R^{\prime\prime}]])$ is a subclass of
$[R^{\prime}]~{}($resp. $[R^{\prime\prime}])$. Then $\bar{\alpha}\in\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$ for any
$P^{\prime}\in[[R^{\prime}]]$ and $P^{\prime\prime}\in[[R^{\prime\prime}]]$.

###### proof B.4

By Lemma B.1, $d_{Q^{\prime}}\in\langle d_{P^{\prime}}\rangle$ for all
$Q^{\prime}\in[[R^{\prime}]]$ and $d_{Q^{\prime\prime}}\in\langle
d_{P^{\prime\prime}}\rangle$ for all
$Q^{\prime\prime}\in[[R^{\prime\prime}]]$. Then we have $\langle
d_{Q};Q\in[[R^{\prime}]]\cup[[R^{\prime\prime}]]\rangle=\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$. Note that by assumption,
$\Lambda_{j}\subseteq[[R^{\prime}]]\cup[[R^{\prime\prime}]]$. Then $\langle
d_{Q};Q\in\Lambda_{j}\rangle\subseteq\langle
d_{Q};Q\in[[R^{\prime}]]\cup[[R^{\prime\prime}]\rangle=\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$. Now, since $\tilde{C}_{\Pi}$ is a
feasible code on $\Pi$, then we have $\bar{\alpha}\in\langle
d_{Q};Q\in\Lambda_{j}\rangle\subseteq\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$.

###### Lemma B.5

Let $\mathcal{I}$ be a partition of $\Pi$ and $\mathcal{I}^{\prime}$ be a
contraction of $\mathcal{I}$ by combining two connected equivalent classes in
$\mathcal{I}$. If all equivalent classes in $\mathcal{I}$ satisfy (P1), then
all equivalent classes in $\mathcal{I}^{\prime}$ satisfy (P1).

###### proof B.6

Suppose $[R^{\prime}],[R^{\prime\prime}]\in\mathcal{I}$ are connected and
$\mathcal{I}^{\prime}$ is obtained by combining $[R^{\prime}]$ and
$[R^{\prime\prime}]$.

Suppose $[R]\in\mathcal{I}^{\prime}$. If
$[R]\neq[R^{\prime}]\cup[R^{\prime\prime}]$, then $[R]\in\mathcal{I}$, and by
assumption, $[R]$ satisfies (P1). So we only need to prove that
$[R]=[R^{\prime}]\cup[R^{\prime\prime}]$ satisfies (P1), i.e.,
$d_{Q^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$ for any pair
$\\{Q,Q^{\prime}\\}\subseteq[R^{\prime}]\cup[R^{\prime\prime}]$. Note that by
assumption, $[R^{\prime}],[R^{\prime\prime}]\in\mathcal{I}$ satisfy (P1). So
if $\\{Q,Q^{\prime}\\}\subseteq[R^{\prime}]$ or
$\\{Q,Q^{\prime}\\}\subseteq[R^{\prime\prime}]$, then
$d_{Q^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$. Thus, we can assume
$\\{Q,Q^{\prime}\\}\nsubseteq[R^{\prime}]$ and
$\\{Q,Q^{\prime}\\}\nsubseteq[R^{\prime\prime}]$. By proper naming, we can
assume $Q\in[R^{\prime}]$ and $Q^{\prime}\in[R^{\prime\prime}]$. Since,
$[R^{\prime}]$ and $[R^{\prime\prime}]$ are connected, by Definition VI.4, we
have two cases:

Case 1: There is a
$\Lambda_{j}\subseteq[[R^{\prime}]]\cup[[R^{\prime\prime}]]$, where
$[[R^{\prime}]]~{}($resp. $[[R^{\prime\prime}]])$ is a subclass of
$[R^{\prime}]~{}($resp. $[R^{\prime\prime}])$. By Lemma B.3,
$\bar{\alpha}\in\langle d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$, where
$P^{\prime}\in[[R^{\prime}]]$ and $P^{\prime\prime}\in[[R^{\prime\prime}]]$.
Similar to 2) of Lemma IV.15, we have $\langle
d_{P^{\prime}},\bar{\alpha}\rangle=\langle
d_{P^{\prime\prime}},\bar{\alpha}\rangle$. Since
$Q^{\prime},P^{\prime\prime}\in[R^{\prime\prime}]$ and $[R^{\prime\prime}]$
satisfy (P1), then $d_{Q^{\prime}}\in\langle
d_{P^{\prime\prime}},\bar{\alpha}\rangle=\langle
d_{P^{\prime}},\bar{\alpha}\rangle$. Similarly, since
$Q,P^{\prime}\in[R^{\prime}]$ and $[R^{\prime}]$ satisfy (P1), then
$d_{P^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$. Thus,
$d_{Q^{\prime}}\in\langle d_{P^{\prime}},\bar{\alpha}\rangle\subseteq\langle
d_{Q},\bar{\alpha}\rangle$.

Case 2: There is a subset $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ such that
$\text{reg}([R^{\prime}]_{i_{1},i_{2}})\cap\text{reg}([R^{\prime\prime}]_{i_{1},i_{2}})\neq\emptyset$.
Suppose
$Q_{0}\in\text{reg}([R^{\prime}]_{i_{1},i_{2}})\cap\text{reg}([R^{\prime\prime}]_{i_{1},i_{2}})$.
Pick a $P_{1}\in\text{reg}([R^{\prime}]_{i_{1},i_{2}})$. By Lemma B.1,
$d_{P^{\prime}}\in\langle d_{P_{1}}\rangle,\forall
P^{\prime}\in[R^{\prime}]_{i_{1},i_{2}}$. Then by 1) of Lemma IV.15,
$d_{Q_{0}}\in\langle
d_{P^{\prime}};P^{\prime}\in[R^{\prime}]_{i_{1},i_{2}}\rangle=\langle
d_{P_{1}}\rangle$, which implies that $\langle d_{P_{1}}\rangle=\langle
d_{Q_{0}}\rangle$. Note that by assumption, $[R^{\prime}]$ satisfies (P1).
Then $d_{P_{1}}\in\langle d_{Q},\bar{\alpha}\rangle$. By 1) of Lemma IV.15,
$d_{P_{1}},d_{Q}\notin\langle\bar{\alpha}\rangle$. So we have $\langle
d_{Q},\bar{\alpha}\rangle=\langle d_{P_{1}},\bar{\alpha}\rangle=\langle
d_{Q_{0}},\bar{\alpha}\rangle$. Similarly, Pick a
$P_{2}\in\text{reg}([R^{\prime\prime}]_{i_{1},i_{2}})$ and we have $\langle
d_{Q^{\prime}},\bar{\alpha}\rangle=\langle
d_{P_{2}},\bar{\alpha}\rangle=\langle d_{Q_{0}},\bar{\alpha}\rangle$. So
$d_{Q^{\prime}}\in\langle d_{Q_{0}},\bar{\alpha}\rangle=\langle
d_{Q},\bar{\alpha}\rangle$.

In both cases, $[R]=[R^{\prime}]\cup[R^{\prime\prime}]$ satisfies (P1). Thus,
all equivalent classes in $\mathcal{I}^{\prime}$ satisfy (P1).

Now we can prove Lemma VI.7.

######  proof B.7 (Proof of Lemma VI.7)

First, for the trivial partition $\mathcal{I}_{0}$ of $\Pi$, since
$[R]=\\{R\\},\forall[R]\in\mathcal{I}_{0}$, so $[R]$ naturally satisfies
property (P1) and $[S_{i}]\neq[S_{j}],\forall\\{i,j\\}\subseteq\\{1,2,3\\}$.

By Definition VI.6, $\mathcal{I}_{c}=\mathcal{I}_{L}$, where
$\mathcal{I}_{0},\mathcal{I}_{1},\cdots,\mathcal{I}_{L}$ is a sequence of
partitions of $\Pi$ such that for each $\ell\in\\{1,\cdots,L\\}$ and
$\\{i,j\\}\subseteq\\{1,2,3\\}$, $[S_{i}]\neq[S_{j}]$ in
$\mathcal{I}_{\ell-1}$ and $\mathcal{I}_{\ell}$ is a contraction of
$\mathcal{I}_{\ell-1}$ by combining two connected equivalent classes. So by
Lemma B.5, all equivalent classes in $\mathcal{I}_{\ell}$ satisfy (P1). In
particular, all equivalent classes in $\mathcal{I}_{c}=\mathcal{I}_{L}$
satisfies (P1). Then Lemma VI.7 is derived from Lemma B.1.

##  Appendix C Proof of Theorem VI.21

In what follows, we always assume $G$ has three terminal regions $T_{1},T_{2}$
and $T_{3}$. If $\Lambda_{j_{1}}=\Lambda_{j_{2}}$ for some
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$, then by Remark VI.18,
$\text{RG}(D^{**})$ is feasible. So we always assume that
$\Lambda_{1},\Lambda_{2},\Lambda_{3}$ are mutually different.

We first give some lemmas, which will help to prove Theorem VI.21.

###### Lemma C.1

For any $j\in\\{1,2,3\\}$, the following hold.

  * 1)

If $\Lambda_{j}=\\{S_{j_{1}},P\\}$ for some $j_{1}\in\\{1,2,3\\}$, then
$P\in\text{reg}^{\circ}(S_{j_{2}},S_{j_{3}})$, where
$\\{j_{2},j_{3}\\}=\\{1,2,3\\}\backslash\\{j_{1}\\}$.

  * 2)

If
$\Lambda_{j}=\\{P^{\prime},P^{\prime\prime}\\}\subseteq\Pi\setminus\\{S_{1},S_{2},S_{3}\\}$
and $P^{\prime}\in\text{reg}^{\circ}(S_{j_{1}},S_{j_{2}})$ for some
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$, then
$P^{\prime\prime}\in\text{reg}^{\circ}(S_{j_{1}},S_{j_{3}})$ or
$P^{\prime\prime}\in\text{reg}^{\circ}(S_{j_{2}},S_{j_{3}})$, where
$\\{j_{3}\\}=\\{1,2,3\\}\backslash\\{j_{1},j_{2}\\}$.

###### proof C.2

1) By 2) of Lemma IV.9, $\Lambda_{j}\nsubseteq\text{reg}(S_{j_{1}},S_{j_{2}})$
and $\Lambda_{j}\nsubseteq\text{reg}(S_{j_{1}},S_{j_{3}})$. So if
$\Lambda_{j}=\\{S_{j_{1}},P\\}$, then
$P\notin\text{reg}(S_{j_{1}},S_{j_{2}})\cup\text{reg}(S_{j_{1}},S_{j_{3}})$.
Thus, we have
$P\in\Pi\setminus(\text{reg}(S_{j_{1}},S_{j_{2}})\cup\text{reg}(S_{j_{1}},S_{j_{2}}))=\text{reg}^{\circ}(S_{j_{2}},S_{j_{3}})$.

2) By 2) of Lemma IV.9,