# Network Coding for $3$s$/n$t Sum-Networks

Wentu Song1, Chau Yuen1, Kai Cai2, and Rongquan Feng3  1Singapore University
of Technology and Design  2Department of Mathematics, University of Hong Kong
3School of Mathematical Sciences, Peking University, Peking, China
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A sum-network is a directed acyclic network where each source independently
generates one symbol from a given field $\mathbb{F}$ and each terminal wants
to receive the sum $($over $\mathbb{F})$ of the source symbols. For sum-
networks with two sources or two terminals, the solvability is characterized
by the connection condition of each source-terminal pair [3]. A necessary and
sufficient condition for the solvability of the $3$-source $3$-terminal
$(3$s$/3$t$)$ sum-networks was given by Shenvi and Dey [6]. However, the
general case of arbitrary sources/sinks is still open. In this paper, we
investigate the sum-network with three sources and $n$ sinks using a region
decomposition method. A sufficient and necessary condition is established for
a class of $3$s$/n$t sum-networks. As a direct application of this result, a
necessary and sufficient condition of solvability is obtained for the special
case of $3$s$/3$t sum-networks.

##  I Introduction

Network coding allows intermediate nodes of a communication network to combine
the incoming information before forwarding it, and was shown to have
significant throughput advantages as opposed to the conventional store-and-
forward scheme [1, 2].

Most of the existent works of network coding focus on how the terminal nodes
recover the whole or part of the original messages. Recently, network coding
for communicating the sum of source messages to the terminal nodes was
investigated [3]-[8]. Such a network is called as a sum-network. The problem
of communicating sums over networks is in fact a subclass of the problem of
distributed function computation, which has been considered in different
contexts [9]-[12].

It was shown in [3] that for directed acyclic graphs with unit capacity edges
and independent, unit-entropy sources, if there are two sources or two
terminals in the network, then the network is solvable if and only if every
source is connected to every terminal. For the $3$-source $3$-terminal
$(3$s$/3$t$)$ sum-networks, a necessary and sufficient condition for the
solvability over any field is given in [6]. However, for networks with
arbitrary number of sources and terminals, no necessary and sufficient
condition is known.

In this paper, we consider the sum-networks with three sources using the
technique of region decomposition [14, 15]. We give a necessary and sufficient
condition for the solvability of a subclass of $3$s$/n$t sum-networks. As a
result, we give a simple characterization of solvability for the special case
of $3$s$/3$t sum-networks.

This paper is organized as follows. In Section II, we introduce the network
model and the notations. The methodology is proposed in section III. The main
result is presented in Section IV. The paper is concluded in Section V.

##  II Models and Notations

We consider a directed, acyclic, finite graph $G=(V,E)$ with a set of $k$
sources $\\{s_{1},\cdots,s_{k}\\}$ and a set of $n$ terminals (sinks)
$\\{t_{1},\cdots,t_{n}\\}$. 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}$, where $\mathbb{F}$ is a finite field. We assume that
each link is error-free, delay-free and can carry one symbol from the field in
each use. We call such network as a $k$s$/n$t sum-network.

For a 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. 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 the $X_{i}$ source link $($or a _source link_ for short$)$, and
each terminal $t_{j}$ has an imaginary outgoing link, called a 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, we call $e$ a _non-source
link_.

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,17\\},T_{1}=\\{18\\},T_{2}=\\{19\\},T_{3}=\\{20\\}$
and
$D^{\prime}=\\{S_{1},S_{2},S_{3},R_{1}^{\prime},R_{2}^{\prime},T_{1},T_{2},T_{3}\\}$.

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\\}$, we 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 let
$\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 along any link $e$ is a
linear combination $M_{e}=\sum_{i=1}^{k}c_{i}X_{i}$ of the source messages and
we use the corresponding coding vector $d_{e}=(c_{1},\cdots,c_{k})$ to
represent the message, where $c_{i}\in\mathbb{F}$. 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)

Let $G=(V,E)$ be a $k$s$/n$t sum-network. A _linear code_ (LC) of $G$ over the
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}$.

##  III Region Decomposition and Network Coding

In this section, we present the region decomposition approach, which will take
a key role in our discussion. The basic idea of region decomposition is
proposed in [14, 15].

###  III-A Region Decomposition and Region Graph

######  Definition III.1 (Region and 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$ and $e\neq 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, we call $R$ a
coding region. If $R$ is not a source region, we call $R$ a _non-source
region_.

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. We will always denote
the $k$ source regions as $S_{1},\cdots,S_{k}$ and the $n$ terminal regions as
$T_{1},\cdots,T_{n}$.

######  Definition III.2 (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)$.

Consider the example network $G_{1}$ in Fig. 1 (a). Examples of two region
graphs are shown in Fig. 1 (b) and (c). In general, $G$ may have many region
decompositions.

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$. For $R\in D$, we use
$\text{In}(R)$ to denote the set of parents of $R$ in $\text{RG}(D)$. Since
the source links have no incoming link, then 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_{p}=R\\}$ such that
$R_{i-1}$ is a parent of $R_{i},i=1,\cdots,p$. 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 regard $R\rightarrow
R$ for all $R\in D$.

###  III-B Network Coding on Region Graph

######  Definition III.3 (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}$, where $S_{i}$ is the $X_{i}$ source region for each
$i\in\\{1,\cdots,k\\}$;

  * (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}=\\{d_{R}\in\mathbb{F}^{k};R\in D\\}$ is said to be a
_linear solution_ of $\text{RG}(D)$ if $d_{T_{j}}=\bar{\alpha}$ for each
terminal region $T_{j}$.

The vector $d_{R}$ is called the global encoding vector of $R$. The region
graph $\text{RG}(D)$ is said to be feasible if it has a linear solution over
some finite field $\mathbb{F}$.

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

Let $D$ be a region decomposition of $G$. Clearly, any linear solution of
$\text{RG}(D)$ can be extended to a linear solution of $G$ by letting
$d_{e}=d_{R}$ for each $R\in D$ and each $e\in R$. So if $\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 letting $d_{e}=d_{R}$ for each $R\in D$ and each $e\in
R$. However, the region graph $\text{RG}(D^{\prime})$ in Fig. 1 (c) is not
feasible because for any linear code, by conditions (1), (2) of Definition
III.3, $d_{T_{1}}\in\langle\alpha_{1},\alpha_{3}\rangle$. So it is impossible
that $d_{T_{1}}=\bar{\alpha}$.

In the following, 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.4 (Basic Region Decomposition[14])

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) a the basic region graph of $G_{1}$.

The basic region decomposition $D^{**}$ can be decided within time
$O(|E|)~{}($See Algorithm 5 in [14]. Note that this Algorithm can be
generalized to networks with any $k$ sources directely.$)$. The following two
theorems were also derived in [14] $($See Theorem 4.4 and 4.5 of [14]
respectively.$)$ and we omit their proof.

###### Theorem III.5

$G$ has a unique basic region decomposition, hence has a unique basic region
graph.

###### Theorem III.6

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

###  III-C Super Region

In this subsection, we always assume that $D$ is a region decomposition of $G$
such that each non-source region has at least two parents in $\text{RG}(D)$.

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

Let $D$ be a region decomposition of $G$ and $\emptyset\neq\Theta\subseteq D$.
The super region generated by $\Theta$, denoted by $\text{reg}(\Theta)$, 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 $\Theta=\\{R_{1},\cdots,R_{k}\\}$, then we denote
$\text{reg}(\Theta)=\text{reg}(R_{1},\cdots,R_{k})$.

Since $\text{RG}(D)$ is acyclic, then $\text{reg}(\Theta)$ is well defined.

Fig 2: An example of region graph.

Consider the region graph in Fig. 2. We have
$\text{reg}(S_{1},S_{2})=\\{S_{1},S_{2},R_{1},R_{4}\\}$. and
$\text{reg}(S_{2},R_{3})=\\{S_{2},S_{3},R_{3}\\}$.

###### Remark III.8

From Definition III.3 and III.7, it is easy to see 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)$.

###### Lemma III.9

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}).$

###### proof III.10

Clearly, $\Theta\subseteq\text{reg}(\Theta_{1})$ and
$\Theta\subseteq\text{reg}(\Theta_{2})$. Then by Definition III.7, we have
$\text{reg}(\Theta)\subseteq\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})$.

Now, suppose
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\neq\text{reg}(\Theta)$. Then
there is an $R_{0}$ such that

$R_{0}\in\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\backslash\text{reg}(\Theta).$

By assumption of $\Theta$, we have $R_{0}\notin\Theta_{1}\cup\Theta_{2}$.
$($Otherwise, without loss of generality, assume $R_{0}\in\Theta_{1}$. Then
$R_{0}\in(\text{reg}(\Theta_{2})\cap\Theta_{1})\subseteq\Theta\subseteq\text{reg}(\Theta)$,
which contradict to the assumption of $R_{0}\notin\text{reg}(\Theta).)$ So
$R_{0}\in\text{reg}^{\circ}(\Theta_{1})\cap\text{reg}^{\circ}(\Theta_{2})$.
Then by Definition III.7, we have

$\text{In}(R_{0})\subseteq\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2}).$

Since $R_{0}\notin\text{reg}(\Theta)$, then by Definition III.7, there exists
an $R_{1}\in\text{In}(R_{0})$ such that $R_{1}\notin\text{reg}(\Theta)$. Then

$R_{1}\in\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\setminus\text{reg}(\Theta).$

Similarly, $R_{1}$ has a parent $R_{2}$ such that

$R_{2}\in\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\setminus\text{reg}(\Theta).$

By repeating this process, we can find a series of infinite regions $R_{0}$,
$R_{1}$, $R_{2}$, $\cdots$ such that $R_{i}$ is a parent of $R_{i-1}$ and

$R_{i}\in\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})\setminus\text{reg}(\Theta),~{}i=1,2,\cdots.$

This contradicts to the fact that $\text{RG}(D)$ is a finite graph. So
$\text{reg}(\Theta_{1})\cap\text{reg}(\Theta_{2})=\text{reg}(\Theta)$.

##  IV A Sufficient and Necessary Condition for a Subclass of $3$-source Sum-
networks

Throughout this section, we always assume that $G$ is a $3$s$/n$t sum-network
and $D^{**}$ is the basic region decomposition of $G$. By Theorem III.6, $G$
is solvable if and only if $\text{RG}(D^{**})$ is feasible. So we only need to
consider coding on $\text{RG}(D^{**})$.

Since $G$ is a $3$s$/n$t sum-network, then $\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.
Let $S_{i}~{}(i\in\\{1,2,3\\})$ denote the $X_{i}$ source region and
$T_{j},j=1,\cdots,n,$ denote the $n$ terminal regions. For any
$i\in\\{1,2,3\\}$, by Lemma III.9, we have

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

where $\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. Thus

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

i.e., $\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. Denote
$\\{1,\cdots,n\\}=[n]$ for any positive integer $n$.

###### Definition IV.1

We define 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 any $I\subseteq[n]$, $\Omega_{I}$ is the set of all $R\in
D^{**}\backslash\Pi$ such that $R\rightarrow T_{j},\forall j\in I$, and
$R\nrightarrow T_{j^{\prime}},\forall 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}$.

We also denote $\Omega_{I}=\Omega_{i_{1},\cdots,i_{p}}$ and
$\Lambda_{I}=\Lambda_{i_{1},\cdots,i_{p}}$ if the subset
$I=\\{i_{1},\cdots,i_{p}\\}$.

From the above definition, the following remark is obvious.

###### Remark IV.2

If $I,I^{\prime}\subseteq[n]$ and $I\neq I^{\prime}$, then
$\Omega_{I}\cap\Omega_{I^{\prime}}=\emptyset$.

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},i=1,2,3$, $R_{N-n+j}=T_{j},j=1,2,\cdots,n,$ and
$\ell<\ell^{\prime}$ if $R_{\ell}$ is a parent of $R_{\ell^{\prime}}$. For all
$I\subseteq[n]$, we can determine $\Omega_{I}$ by a the following simple
labelling algorithm.

Algorithm 1: Labelling Algorithm $(\text{RG}(D^{**}))$:

$j\leftarrow$ from $1$ to $n$

Label $R_{N-n+j}$ with $j$;

$\ell\leftarrow$ from $N$ to $1$;

if $R_{\ell}$ has a child $R_{\ell^{\prime}}$ such that $R_{\ell^{\prime}}$ is
labelled with $j$ for

some $j\in[n]$ then

Label $R_{\ell}$ with $j$;

Note that for each $R\in D^{**}$ and $j\in[n]$, if $R$ has a child
$R^{\prime}$ such that $R^{\prime}\rightarrow T_{j}$, then $R\rightarrow
T_{j}$. So $R\rightarrow T_{j}$ if and only if $R$ is labelled with $j$ by
Algorithm 1. Let $I_{R}=\\{j\in[n];R\text{~{}is labelled with~{}}j\\}$. Then
for each $I\subseteq[n]$, $R\in\Omega_{I}$ if and only if $I_{R}=I$. Thus, by
Algorithm 1, we can easily determine $\Omega_{I}$ for all $I\subseteq[n]$.
Clearly, the run time of Algorithm 1 is $O(|D^{**}|)$.

Consider the region graph in Fig. 2. We have $\Omega_{i}=\\{T_{i}\\}$ for
$i\in\\{1,2,3\\}$, $\Omega_{2,3}=\\{R_{5}\\}$ and
$\Omega_{1,2}=\Omega_{1,3}=\Omega_{1,2,3}=\emptyset$. Thus, we have
$\Lambda_{1}=\\{R_{1},R_{3}\\}$, $\Lambda_{2}=\\{R_{4}\\}$,
$\Lambda_{3}=\\{R_{3}\\}$, $\Lambda_{2,3}=\\{R_{2},R_{3}\\}$ and
$\Lambda_{1,2}=\Lambda_{1,3}=\Lambda_{1,2,3}=\emptyset$.

If $\tilde{C}=\\{d_{R}\in\mathbb{F}^{k};R\in D\\}$ is a linear solution of
$\text{RG}(D^{**})$, $\\{i,j\\}\subseteq\\{1,2,3\\}$ and
$R\in\text{reg}(S_{i},S_{j})$, then by Remark III.8, $\bar{\alpha}\neq
d_{R}\in\langle\alpha_{i},\alpha_{j}\rangle$. So
$T_{\ell}\notin\text{reg}(S_{i},S_{j})$ for all terminal region $T_{\ell}$,
which implies that $T_{\ell}\in D^{**}\backslash\Pi,\forall\ell\in[n]$. For
this reason, in this section, we assume:

_Assumption_ 1: $T_{j}\notin\Pi$ for all $j\in[n]$.

###### Definition IV.3

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

For example, the region graph in Fig. 3 is terminal-separable. However, the
region graph in Fig. 2 is not because $\Omega_{2,3}=\\{R_{5}\\}\neq\emptyset$.

We shall give a necessary and sufficient condition of feasibility for
terminal-separable region graph, by which it is easy to check whether a
terminal-separable region graph is feasible.

###### Remark IV.4

Terminal-separable region graphs is of interesting because, if a region graph
$\text{RG}(D)$ is not terminal-separable, then we can view it as a region
graph with fewer terminal regions. For example, for the region graph in Fig.
2, we can view $T_{1}$ and $R_{5}$ as two terminal regions and construct a
linear solution of $\text{RG}(D)$. Then the sum of sources can be transmitted
from $R_{5}$ to $T_{2}$ and $T_{3}$. In fact, let
$d_{R_{1}}=d_{R_{2}}=\alpha_{1},d_{R_{3}}=\alpha_{2}+\alpha_{3}$ and
$d_{R_{5}}=\alpha_{1}+\alpha_{2}+\alpha_{3}$. Then $\\{d_{R};R\in D\\}$ is a
linear solution of $\text{RG}(D)$.

###### Lemma IV.5

If $\text{RG}(D^{**})$ is terminal-separable, then for all $j\in[n]$ and
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, we have
$T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$ and
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$. In particular, we have
$|\Lambda_{j}|\geq 2$.

###### proof IV.6

Since $T_{j}\rightarrow T_{j}$ and $\text{RG}(D^{**})$ is terminal-separable,
then $T_{j}\nrightarrow T_{j^{\prime}},\forall
j^{\prime}\in[n]\backslash\\{j\\}$. So $T_{j}\in\Omega_{j}$.

We now prove $\Omega_{j}\subseteq\text{reg}(\Lambda_{j})$ by contradiction.
For this purpose, suppose there is an $R\in\Omega_{j}$ such that
$R\notin\text{reg}(\Lambda_{j})$. Then by Definition III.7, $R$ has a parent,
say $P_{1}$, such that $P_{1}\notin\text{reg}(\Lambda_{j})$. Clearly,
$P_{1}\notin\Pi$. $($Otherwise, by the definition of $\Lambda_{j}$,
$P_{1}\in\Lambda_{j}\subseteq\text{reg}(\Lambda_{j})$, which contradicts to
the assumption that $P_{1}\notin\text{reg}(\Lambda_{j})$.$)$ Since
$\text{RG}(D^{**})$ is terminal-separable and $P_{1}\rightarrow R\rightarrow
T_{j}$, then $P_{1}\nrightarrow T_{j^{\prime}},\forall j^{\prime}\neq j$. So
$P_{1}\in\Omega_{j}$. Similarly, $P_{1}$ has a parent $P_{2}$ such that
$P_{2}\notin\text{reg}(\Lambda_{j})$ and $P_{2}\in\Omega_{j}$. By repeating
this process, we can obtain a series of infinite regions, $P_{1},P_{2},\cdots$
such that $P_{i}\notin\text{reg}(\Lambda_{j})$ and $P_{i}\in\Omega_{j}$, which
contradicts to the fact that $\text{RG}(D^{**})$ is a finite graph. So
$\Omega_{j}\subseteq\text{reg}(\Lambda_{j})$.

Note that $\Omega_{j}\subseteq D^{**}\setminus\Pi$ and
$\Lambda_{j}\subseteq\Pi$. So $\Omega_{j}\cap\Lambda_{j}=\emptyset$. Thus, we
have $T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$.

Moreover, if $\Lambda_{j}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$, then by
Definition III.7, we have
$T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$,
which contradicts to Assumption 1. So
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$.

Finally, if $|\Lambda_{j}|=1$, say $\Lambda_{j}=\\{Q\\}$, then by the
definition of $\Pi$ and $\Lambda_{j}$, 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$.

###### Lemma IV.7

Suppose $\text{RG}(D^{**})$ is terminal-separable. Then $\text{RG}(D^{**})$ is
feasible if and only if there is a collection of vectors
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfying the
following three conditions:

  * (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,\forall
R\in\Pi\setminus\\{S_{1},S_{2},S_{3}\\}$;

  * (3)

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

###### proof IV.8

Suppose $\text{RG}(D^{**})$ is feasible and $\tilde{C}=\\{d_{R};R\in
D^{**}\\}$ is a linear solution of $\text{RG}(D^{**})$. By Lemma IV.5,
$T_{j}\in\Omega_{j}\subseteq\text{reg}^{\circ}(\Lambda_{j})$ and
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$, $\forall j\in[n]$ and
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. By Remark III.8,
$\bar{\alpha}=d_{T_{j}}\in\langle d_{R};R\in\Lambda_{j}\rangle$. Let
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$. Then $\tilde{C}_{\Pi}$ satisfies
conditions (1)-(3).

Conversely, suppose there is a collection
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfying
conditions (1)-(3). We can construct a linear solution of $\text{RG}(D^{**})$
as follows:

Since $\text{RG}(D^{**})$ is terminal-separable, for each $j\in[n]$ and
$Q\in\Lambda_{j}$, by the Definition of $\Lambda_{j}$ and $\Omega_{j}$, we can
find a path $\\{R_{1},\cdots,R_{\ell}\\}\subseteq\Omega_{j}$ such that
$R_{\ell}=T_{j}$ and $Q$ is a parent of $R_{1}$. Let $\Gamma_{j}$ be the union
of all such paths. Then $\Gamma_{j}\subseteq\Omega_{j}$. Since
$\bar{\alpha}\in\langle d_{R};R\in\Lambda_{j}\rangle$, then we can construct a
code $\tilde{C}_{\Gamma_{j}}=\\{d_{R};R\in\Gamma_{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\Gamma_{j}$. By
Remark IV.2, $\Omega_{j},j=1,\cdots,n,$ are mutually disjoint. So
$\Gamma_{j},j=1,\cdots,n,$ are mutually disjoint and
$\tilde{C}=\tilde{C}_{\Pi}\cup\tilde{C}_{\Gamma_{1}}\cup\cdots\cup\tilde{C}_{\Gamma_{n}}$
is a linear solution of $\text{RG}(D^{**})$. Thus, $\text{RG}(D^{**})$ is
feasible.

###  IV-A Partitioning of $\Pi$

To give a simple characterization of feasibility of $\text{RG}(D^{**})$, we
need to make some discussion on partitioning $\Pi$.

Let $\mathcal{I}=\\{\Delta_{1},\cdots,\Delta_{K}\\}$ be a partition of $\Pi$.
For the sake of convenience, we shall call each $\Delta_{i}$ an _equivalent
class_ of $\mathcal{I}$. If $R\in\Delta_{i}$, we denote $\Delta_{i}=[R]$.
Thus, for each $\Delta_{i}$, we can choose an $R_{i}\in\Delta_{i}$ and denote
$\mathcal{I}=\\{[R_{1}],\cdots,[R_{K}]\\}$.

Let $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ be an arbitrary
partition of $\Pi$.111When we use the notation
$\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$, we always assume
that $[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]$ are mutually different. For each
equivalent class $[R]\in\mathcal{I}$ and each subset
$\\{i,j\\}\subseteq\\{1,2,3\\}$, we denote

$\displaystyle\vspace{-0.1cm}[R]_{i,j}=[R]\cap\text{reg}(S_{i},S_{j}).$ (3)

For each $i\in\\{1,2,3\\}$, we denote

$\displaystyle\vspace{-0.1cm}[S_{i}]_{i}=[S_{i}]_{i,j_{1}}\cup[S_{i}]_{i,j_{2}}$
(4)

where $\\{j_{1},j_{2}\\}=\\{1,2,3\\}\backslash\\{i\\}$. Then we can divide
each equivalent class as follows:

###### Definition IV.9

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\in\\{4,\cdots,K\\}$,
$[R_{i}]$ is divided into three _subclasses_ $[R_{i}]_{1,2},[R_{i}]_{1,3}$ and
$[R_{i}]_{2,3}$.

Fig 3: An example of terminal-separable region graph: By Definition III.7, we
can check that $\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},R_{7}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},R_{3},R_{5},R_{6}\\}$. By Definition
IV.1, we have $\Omega_{j}=\\{T_{j}\\},j=1,\cdots,6$ and
$\Omega_{I}=\emptyset,\forall I\subseteq\\{1,\cdots,6\\}$ such that $|I|\geq
2$. So this region graph is terminal-separable.

For any equivalent class $[R]\in\mathcal{I}$, we use $[[R]]$ to denote a
subclass of $[R]$. Note that a subclass $[[R]]$ of $[R]$ is possibly an empty
set. By Equations (1)$-$(4), each equivalent class is a disjoint union of its
all subclasses. Thus, $\\{[S_{1}]_{1},[S_{1}]_{2,3}\\}\cup\\{[S_{2}]_{2}$,
$[S_{2}]_{1,3}\\}\cup\\{[S_{3}]_{3},[S_{3}]_{1,2}\\}\cup(\cup_{i=4}^{K}\\{[R_{i}]_{1,2},[R_{i}]_{1,3},[R_{i}]_{2,3}\\})$
is still a partition of $\Pi$.

###### Example IV.10

Consider the region graph in Fig. 3. By Definition III.7,
$\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},R_{7}\\}$ and
$\text{reg}(S_{2},S_{3})=\\{S_{2},S_{3},R_{3},R_{5},R_{6}\\}$. Let
$[S_{1}]=\\{S_{1},R_{1},R_{3},R_{4},R_{5},R_{7}\\}$, $[S_{2}]=\\{S_{2}\\}$,
$[S_{3}]=\\{S_{3}\\}$, $[R_{2}]=\\{R_{2},R_{6}\\}$ and
$\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],[R_{2}]\\}$. Then $\mathcal{I}$ is a
partition of $\Pi$ and $[S_{1}]_{1}=\\{S_{1},R_{1},R_{4},R_{7}\\}$,
$[S_{1}]_{2,3}=\\{R_{3},R_{5}\\}$, $[S_{2}]_{2}=\\{S_{2}\\}$,
$[S_{2}]_{1,3}=\emptyset$, $[S_{3}]_{3}=\\{S_{3}\\}$,
$[S_{3}]_{1,2}=\emptyset$, $[R_{2}]_{1,2}=\emptyset$,
$[R_{2}]_{1,3}=\\{R_{2}\\}$, $[R_{2}]_{2,3}=\\{[R_{6}]\\}$ are all subclasses
of $\mathcal{I}$ and they also form a partition of $\Pi$.

###### Definition IV.11

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

  * (1)

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}])$;

  * (2)

There is an $\\{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$.

###### Definition IV.12

Let $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ be a partition
of $\Pi$. $\mathcal{I}$ is said to be _compatible_ if the following two
conditions hold:

  * (1)

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

  * (2)

$\Lambda_{j}\nsubseteq[S_{i_{1}}]_{i_{1}}\cup[S_{i_{2}}]_{i_{2}}\cup(\cup_{\ell=4}^{K}[R_{\ell}]_{i_{1},i_{2}})$
for all $j\in[n]$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.

Clearly, in Example IV.10, the partition $\mathcal{I}$ of $\Pi$ is compatible.

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}]$.

###  IV-B Main Result

Let $\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$, where $[R]=\\{R\\},\forall R\in\Pi$.
Then $\mathcal{I}_{0}$ is a partition of $\Pi$. We call $\mathcal{I}_{0}$ the
trivial partition of $\Pi$.

###### Definition IV.13

Let $\mathcal{I}_{0},\mathcal{I}_{1},\cdots,\mathcal{I}_{L}=\mathcal{I}_{c}$
be a sequence of partitions of $\Pi$ such that $\mathcal{I}_{\ell}$ is a
contraction of $\mathcal{I}_{\ell-1}$ by combining two connected equivalent
classes in $\mathcal{I}_{\ell-1}$ and, for any
$\\{i,j\\}\subseteq\\{1,2,3\\}$, $[S_{i}]\neq[S_{j}]$ in
$\mathcal{I}_{\ell-1}$, where $\ell=1,\cdots,L$. $\mathcal{I}_{c}$ is called a
character 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.

###### Example IV.14

Consider the region graph in Fig. 4 (a). We have
$\Pi=\\{S_{1},S_{2},S_{3},R_{1},R_{2},R_{3},R_{4}\\}$ and
$\Lambda_{2}=\\{S_{2},R_{1}\\}\subseteq([S_{2}]_{2}\cup[R_{1}]_{1,3})$. By (1)
of Definition IV.11, $[S_{2}]$ and $[R_{1}]$ are connected. So
$\mathcal{I}_{1}=\\{\\{S_{1}\\},\\{S_{2},R_{1}\\},\\{S_{3}\\},\\{R_{2}\\}$,
$\\{R_{3}\\},\\{R_{4}\\}\\}$ is obtained from $\mathcal{I}_{0}$ by combining
$[S_{2}]$ and $[R_{1}]$, where $\mathcal{I}_{0}$ is the trivial partition of
$\Pi$. Similarly, let
$\mathcal{I}_{2}=\\{\\{S_{1}\\},\\{S_{2},R_{1},R_{2}\\},\\{S_{3}\\},\\{R_{3}\\},\\{R_{4}\\}\\}$
and
$\mathcal{I}_{3}=\\{\\{S_{1}\\},\\{S_{2},R_{1},R_{2},R_{3}\\},\\{S_{3}\\},\\{R_{4}\\}\\}$.
Then $\mathcal{I}_{j},j=2,3,$ is obtained from $\mathcal{I}_{j-1}$ by
combining two connected equivalent classes. Note that in $\mathcal{I}_{3}$,
$\text{reg}([S_{2}]_{2,3})=\text{reg}(R_{2},R_{3})=\\{R_{2},R_{3},R_{4}\\}$
and $\text{reg}([R_{4}]_{2,3})=\text{reg}(R_{4})=\\{R_{4}\\}$. So by (2) of
Definition IV.11, $[S_{2}]$ and $[R_{4}]$ are connected and
$\mathcal{I}_{4}=\\{\\{S_{1}\\}$,
$\\{S_{2},R_{1},R_{2},R_{3},R_{4}\\},\\{S_{3}\\}\\}$ is obtained from
$\mathcal{I}_{3}$ by combining two connected equivalent classes. In
$\mathcal{I}_{4}$, again by (1) of Definition IV.11, $[S_{2}]$ and $[S_{1}]$
are connected and $\mathcal{I}_{5}=\\{\\{S_{1},S_{2},R_{1},R_{2},R_{3}$,
$R_{4}\\}$, $\\{S_{3}\\}\\}$ is obtained from $\mathcal{I}_{4}$ by combining
two connected equivalent classes. Thus,
$\mathcal{I}_{0},\mathcal{I}_{1},\cdots,\mathcal{I}_{5}$ satisfy the
conditions of Definition IV.13. So $\mathcal{I}_{c}=\mathcal{I}_{5}$ is a
character partition of $\Pi$. Since $[S_{1}]=[S_{2}]$, then $\mathcal{I}_{c}$
is not compatible.

Similarly, for the region graph in Fig. 4 (b), we can find that
$\mathcal{I}_{c}=\\{\\{S_{1},P_{1},P_{2},P_{3},P_{4}\\},\\{S_{2}\\},\\{S_{3}\\}\\}$
is a character partition of $\Pi$. Since $\Lambda_{2}\subseteq[S_{1}]_{1}$,
then $\mathcal{I}_{c}$ is not compatible.

Fig 4: Examples of region graph.

###### Lemma IV.15

Let $\mathcal{I}$ be a partition of $\Pi$. If $\mathcal{I}$ is compatible,
then $\text{RG}(D^{**})$ is feasible.

###### proof IV.16

The proof is given in Appendix A.

###### Lemma IV.17

Suppose $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfies
the conditions of Lemma IV.7 and $\mathcal{I}_{c}$ is a character partition of
$\Pi$. For any $[R]\in\mathcal{I}_{c}$ and
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, if $Q\in[R]_{i_{1},i_{2}}$ and
$d_{Q}\neq 0$, then $d_{Q^{\prime}}\in\langle d_{Q}\rangle,\forall
Q^{\prime}\in[R]_{i_{1},i_{2}}$.

###### proof IV.18

The proof is given in Appendix B.

###### Theorem IV.19

Let $\text{RG}(D^{**})$ be terminal-separable and $\mathcal{I}_{c}$ be a
character 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 feasibility of $\text{RG}(D^{**})$.

###### proof IV.20

If $\mathcal{I}_{c}$ is compatible, then by Lemma IV.15, $\text{RG}(D^{**})$
is feasible. Conversely, suppose $\text{RG}(D^{**})$ is feasible and
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfies the
conditions of Lemma IV.7. We shall prove that $\mathcal{I}_{c}$ is compatible.

For any $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, if $[S_{i_{1}}]=[S_{i_{2}}]$,
then $S_{i_{1}}\in[S_{i_{2}}]_{i_{1},i_{2}}$. By Definition III.3 and Lemma
IV.17, $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}}]$. Thus, by proper naming, we can assume
$\mathcal{I}_{c}=\\{[S_{1}],[S_{2}],[S_{3}],[R_{4}],\cdots,[R_{K}]\\}$.
Moreover, by Definition IV.13, no pair of equivalent classes of
$\mathcal{I}_{c}$ are connected.

For any $j\in[n]$ and $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, suppose
$\Lambda_{j}\subseteq[S_{i_{1}}]_{i_{1}}\cup[S_{i_{2}}]_{i_{2}}\cup(\cup_{\ell=4}^{K}[R_{\ell}]_{i_{1},i_{2}})$.
Then by Lemma IV.17 and Equation (4), we have

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

and

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

Note that $\tilde{C}_{\Pi}$ satisfies condition (2) of Lemma IV.7. By Equation
(5), (6) and Definition III.7, we can easily see that
$d_{R}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$ for all
$R\in[S_{i_{1}}]_{i_{1}}\cup[S_{i_{2}}]_{i_{2}}\cup(\cup_{\ell=4}^{K}[R_{\ell}]_{i_{1},i_{2}})$.
Then $d_{R}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$ for all
$R\in\Lambda_{j}$ and $\bar{\alpha}\notin\langle
d_{R};R\in\Lambda_{j}\rangle$, which contradicts to the assumption that
$\tilde{C}_{\Pi}$ satisfies condition (3) of Lemma IV.7. Thus,
$\Lambda_{j}\nsubseteq[S_{i_{1}}]_{i_{1}}\cup[S_{i_{2}}]_{i_{2}}\cup(\cup_{\lambda=4}^{K}[R_{\lambda}]_{i_{1},i_{2}})$.
By Definition IV.12, $\mathcal{I}_{c}$ is compatible.

By Definition IV.13, the following algorithm output a character partition of
$\Pi$.

Algorithm 2: Partitioning algorithm $(\Pi,\mathcal{S})$:

$L=0$;

While there are $R^{\prime},R^{\prime\prime}\in\mathcal{I}_{L}$ which are
$\mathcal{S}-$connected do

Let $\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, there are at most $|\Pi|$ rounds in Algorithm 2 before output
$\mathcal{I}_{c}$. In each round, we need to determine wether there are two
$\mathcal{S}$-connected equivalent classes, which can be done in time
$O(|\mathcal{S}|)=O(n)$ by Definition IV.11. Thus, it is
$\\{|\Pi|,n\\}$-polynomial time complexity to determine whether
$\text{RG}(D^{**})$ is feasible.

Consider the region graph in Fig. 3. We can check that the partition
$\mathcal{I}$ in Example IV.10 is a character partition of $\Pi$. Since
$\mathcal{I}$ is compatible, so the region graph is feasible. Let
$\mathbb{F}=GF(p)$ for a sufficiently large prime $p$. Let
$d_{R_{1}}=d_{R_{4}}=d_{R_{7}}=\alpha_{1}$,
$d_{R_{2}}=2\alpha_{1}+3\alpha_{3}$,
$d_{R_{3}}=d_{R_{5}}=\alpha_{2}+\alpha_{3}$,
$d_{R_{6}}=\alpha_{1}+3\alpha_{2}$. Then $\\{d_{R};R\in\Pi\\}$ is a linear
solution of the graph.

Similar to the information flow decomposition technique used in [13], we can
reduce any compatible partition of $\Pi$ into a minimal compatible partition
$\mathcal{I}_{m}$, i.e., $\mathcal{I}_{m}$ is a compatible partition of $\Pi$
but any contraction of $\mathcal{I}_{m}$ is not compatible. Then we can
construct an optimal linear solution of $\text{RG}(D^{**})$ on
$\mathcal{I}_{m}$ using the method in the proof of Lemma IV.15.

For the two region graphs in Fig. 4, we have seen that there is a character
partition of $\Pi$ that is not compatible. So by Theorem IV.19, these two
region graphs are not feasible.

In [6], a necessary and sufficient condition for solvability of a $3$s$/3$t
sum-network was given based on a set of connection conditions. By our method,
we can give another sufficient and necessary condition for solvability of
$3$s$/3$t sum-networks which is different from [6]:

###### Theorem IV.21

Suppose $\text{RG}(D^{**})$ has three terminal regions. Then
$\text{RG}(D^{**})$ is not feasible if and only if it is terminal separable
and the following condition (C-IR) hold:
(C-IR) By proper naming, 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 IV.22

The proof is given in Appendix C.

Fig. 4 (b) is an illustration of infeasible region graph of $3$s$/3$t sum-
network.

##  V Conclusions and Discussions

We investigated the network coding problem of a special subclass of $3$s$/n$t
sum-networks termed as terminal-separable networks using a network region
decomposition method. We give a necessary and sufficient condition for
solvability of terminal separable networks as well as a simple
characterization of solvability of $3$s$/3$t sum-networks. The region
decomposition method is shown to be an efficient tool for analyzing the
structure of a network and helps to investigate the network coding problem of
a communication network. By more intensive analysis, we can also give a
characterization of solvability of $3$s$/4$t sum-networks, which is our future
work.

## 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] A. Ramamoorthy, “Communicating the sum of sources over a network,” in _Proc ISIT_ , Toronto, Canada, July 06-11, pp. 1646-1650, 2008.
  * [4] B. K. Rai, B. K. Dey, and A. Karandikar, “Some results on communicating the sum of sources over a network,” in _Proc NetCod_ 2009\.
  * [5] M. Langberg and A. Ramamoorthy, “Communicating the sum of sources in a 3-sources/3-terminals network,” in _Proc ISIT_ , Seoul, Korea, 2009.
  * [6] 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.
  * [7] 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\.
  * [8] 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.
  * [9] 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.
  * [10] Y. Kanoria and D. Manjunath, “On distributed computation in noisy random planar networks,” in _Proc. ISIT_ , Nice, France, 2008\.
  * [11] 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.
  * [12] 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.
  * [13] C. Fragouli and E. Soljanin,“Information flow decomposition for network coding,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 3, pp. 829-848, Mar. 2006.
  * [14] 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.
  * [15] 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 IV.15

Here, we prove Lemma IV.15. First, we prove two lemmas.

###### Lemma A.1

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}\\}$ and $K\geq 3$ is an
integer. If $\mathbb{F}$ is sufficiently large, then there are $K-3$ subsets
$\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}$
such that
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3},\cdots,\mathcal{B}_{K}\\}$
satisfies the following conditions:

  * (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)

For any $\ell\in\\{1,\cdots,K\\}$ and
$\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{\ell}$,
$\bar{\alpha}\in\langle\gamma,\gamma^{\prime}\rangle$;

  * (3)

If
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\cup_{\ell=1}^{K}\mathcal{B}_{\ell}$
such that
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall\\{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}\\},\forall\ell\in\\{4,\cdots,K\\}$,
then $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly
independent;

  * (4)

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

###### proof A.2

We can prove this lemma by induction.

Clearly, when $K=3$, the collection
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}\\}$ satisfies conditions
(1)$-$(4).

Now suppose $K>3$ and there is a collection $\\{\mathcal{B}_{1}$, $\cdots$,
$\mathcal{B}_{K-1}\\}$ which satisfies conditions (1)$-$(4). We want to
construct a subset
$\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2},\beta^{(K)}_{1,3},\beta^{(K)}_{2,3}\\}\subseteq\mathbb{F}^{3}$
such that the collection
$\\{\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}\\}$ satisfies
conditions (1)$-$(4). The subset $\mathcal{B}_{K}$ can be constructed as
follows:

Let $\Phi_{K-1}$ be the set of all pairs
$\\{\gamma,\gamma^{\prime}\\}\subseteq\cup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$
such that
$\\{\gamma,\gamma^{\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Then
$\langle\gamma,\gamma^{\prime}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
is an 1-dimensional subspace of $\mathbb{F}^{3}$. Let
$\langle\gamma,\gamma^{\prime}\rangle_{i_{1},i_{2}}$ be a fixed non-zero
vector in
$\langle\gamma,\gamma^{\prime}\rangle\cap\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$.
Let

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

Since $\mathbb{F}$ is sufficiently large, then there exists a
$\beta^{(K)}\in\mathbb{F}^{3}$ such that

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

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$
(8)

where $0$ is the zero vector of $\mathbb{F}^{3}$. Let
$\mathcal{B}_{K}=\\{\beta^{(K)}_{1,2}$,
$\beta^{(K)}_{1,3},\beta^{(K)}_{2,3}\\}$. We shall prove that the collection
$\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1}$, $\mathcal{B}_{K}\\}$
satisfies conditions (1)$-$(4).

By Equation (8), we have
$\beta^{(K)}_{i_{1},i_{2}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
So $\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1}$, $\mathcal{B}_{K}\\}$
satisfies condition (1).

By assumption, $\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1}\\}$
satisfies condition (2), then for any $\ell\in\\{1,\cdots,K-1\\}$ and
$\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{\ell}$, the pair
$\\{\gamma,\gamma^{\prime}\\}$ is in $\Phi_{K-1}$. Moreover, since
$\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1}\\}$ satisfies condition
(1), then
$\\{\gamma,\gamma^{\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,\gamma^{\prime}\\}\subseteq\\{\langle\gamma,\gamma^{\prime}\rangle_{1,2}$,
$\langle\gamma,\gamma^{\prime}\rangle_{1,3}$,
$\langle\gamma,\gamma^{\prime}\rangle_{2,3}\\}$. Thus, we have
$\cup_{\ell=1}^{K-1}\mathcal{B}_{\ell}\subseteq\Psi_{K-1}$. By Equation (7),
for any $\gamma\in\cup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$,

$\displaystyle\gamma\notin\langle\beta^{(K)},\bar{\alpha}\rangle.$ (9)

In particular, we have
$\alpha_{j}\notin\langle\beta^{(K)},\bar{\alpha}\rangle,j=1,2,3$. So by
Equation (8), $\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,\forall\\{\gamma,\gamma^{\prime}\\}\subseteq\mathcal{B}_{K}$.
Thus, $\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1},$
$\mathcal{B}_{K}\\}$ satisfies condition (2).

Now, we prove that $\cup_{\ell=1}^{K}\mathcal{B}_{\ell}$ satisfies condition
(3). Suppose
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\cup_{\ell=1}^{K}\mathcal{B}_{\ell}$
such that
$\\{\gamma,\gamma^{\prime},\gamma^{\prime\prime}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
for any $\\{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 any
$\ell\in\\{1,\cdots,K\\}$. We have the following three cases:

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

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

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

Case 2.2:
$\\{\gamma,\gamma^{\prime}\\}\nsubseteq\langle\alpha_{\ell_{1}},\alpha_{\ell_{2}}\rangle,\forall\\{\ell_{1},\ell_{2}\\}\subseteq\\{1,2,3\\}$.
Then the pair $\\{\gamma,\gamma^{\prime}\\}$ is in the set $\Phi_{K-1}$. So we
have
$\gamma^{\prime\prime}\notin\langle\gamma,\gamma^{\prime}\rangle.~{}($Otherwise,
$\gamma^{\prime\prime}\in\\{\langle\gamma,\gamma^{\prime}\rangle_{1,2},\langle\gamma,\gamma^{\prime}\rangle_{1,3},\langle\gamma,\gamma^{\prime}\rangle_{2,3}\\}\subseteq\Psi_{K-1}$
and by Equation (8),
$\beta^{(K)}\in\langle\bar{\alpha},\gamma^{\prime\prime}\rangle$, which
contradicts to Equation (7).$)$ Thus, $\gamma,\gamma^{\prime}$ and
$\gamma^{\prime\prime}$ are linearly independent.

Case 3: $\gamma\in\cup_{\ell=1}^{K-1}\mathcal{B}_{\ell}$ and
$\\{\gamma^{\prime},\gamma^{\prime\prime}\\}\subseteq\mathcal{B}_{K}$. By
Equations (8) and (9),
$\gamma\notin\langle\beta^{(K)},\bar{\alpha}\rangle=\langle\gamma^{\prime},\gamma^{\prime\prime}\rangle$.
So $\gamma,\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are linearly
independent.

Thus, $\\{\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}\\}$
satisfies conditions (3).

Clearly, if $\\{\mathcal{B}_{1},\cdots,\mathcal{B}_{K-1},\mathcal{B}_{K}\\}$
satisfies conditions (3), then for any
$\\{\gamma,\gamma^{\prime}\\}\subseteq\cup_{\ell=1}^{K}\mathcal{B}_{\ell}$, we
can find a $\gamma^{\prime\prime}\in\cup_{\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}\\}$ satisfies
conditions (4).

By induction, for all $K\geq 3$, we can always find a collection
$\\{\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K-1}$, $\mathcal{B}_{K}\\}$
which satisfies conditions (1)$-$(4).

We give an example of Lemma A.1 in the below. To simplify our discussion, we
assume that $\mathbb{F}=GF(p)$, where $p$ is a sufficiently large prime.

###### Example A.3

According to Lemma A.1,
$\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}\\}$.
Then
$\Phi_{3}=\\{\\{\alpha_{1},\alpha_{2}+\alpha_{3}\\},\\{\alpha_{2},\alpha_{1}+\alpha_{3}\\},\\{\alpha_{3},\alpha_{1}+\alpha_{2}\\},\\{\alpha_{2}+\alpha_{3},\alpha_{1}+\alpha_{3}\\},\\{\alpha_{2}+\alpha_{3},\alpha_{1}+\alpha_{2}\\},\\{\alpha_{1}+\alpha_{3},\alpha_{1}+\alpha_{2}\\}\\}$
and
$\Psi_{3}=\\{\alpha_{1},\alpha_{2}+\alpha_{3}\\}\cup\\{\alpha_{2},\alpha_{1}+\alpha_{3}\\}\cup\\{\alpha_{3},\alpha_{1}+\alpha_{2}\\}\cup\\{\alpha_{2}+\alpha_{3},\alpha_{1}+\alpha_{3},\alpha_{1}-\alpha_{2}\\}\cup\\{\alpha_{2}+\alpha_{3},\alpha_{1}+\alpha_{2},\alpha_{1}-\alpha_{3}\\}\cup\\{\alpha_{1}+\alpha_{3},\alpha_{1}+\alpha_{2},\alpha_{2}-\alpha_{3}\\}$.
We can check that
$\alpha_{1}+3\alpha_{2}\notin\langle\bar{\alpha},\gamma\rangle,\forall\gamma\in\Psi_{3}$.
Let $\beta^{(4)}=\alpha_{1}+3\alpha_{2}$ and
$\mathcal{B}_{4}=\\{\alpha_{1}+3\alpha_{2},2\alpha_{1}+3\alpha_{3},2\alpha_{2}-\alpha_{3}\\}$.
Then the collection
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3},\mathcal{B}_{4}\\}$
satisfies conditions (1)$-$(4) of Lemma A.1.

Similarly, we can construct a subset
$\mathcal{B}_{5}=\\{2\alpha_{1}+3\alpha_{2},\alpha_{1}+3\alpha_{3},\alpha_{2}-2\alpha_{3}\\}$
such that the collection
$\\{\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3},\mathcal{B}_{4},\mathcal{B}_{5}\\}$
satisfies conditions (1)$-$(4) of Lemma A.1.

###### Lemma A.4

Let $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and
$\\{\Delta_{1},\cdots,\Delta_{K}\\}$ be a partition of
$\text{reg}(S_{i_{1}},S_{i_{2}})$ such that
$\text{reg}(\Delta_{i})=\Delta_{i},i=1,\cdots,K$. Let
$\tilde{C}_{i_{1},i_{2}}=\\{d_{R};R\in\text{reg}(S_{i_{1}},S_{i_{2}})\\}\subseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$
be such that:

  * (1)

If $\\{R,R^{\prime}\\}\subseteq\Delta_{i}$ for some $i\in[K]$, then
$d_{R}=d_{R^{\prime}}$;

  * (2)

If $\\{R,R^{\prime}\\}\nsubseteq\Delta_{i}$ for any $i\in[K]$, then $d_{R}$
and $d_{R^{\prime}}$ are linearly independent.

Then $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle,~{}\forall
R\in\text{reg}^{\circ}(S_{i_{1}},S_{i_{2}}).$

###### proof A.5

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

Case 1: $\text{In}(R)\subseteq\Delta_{i}$ for some $i\in\\{1,\cdots,K\\}$.
Then by Definition III.7, $R\in\text{reg}(\Delta_{i})$. Since by the
assumption of this lemma, $\text{reg}(\Delta_{i})=\Delta_{i}$, then
$R\in\Delta_{i}$ and, by condition (1), $d_{R}=d_{R^{\prime}}$ for all
$R^{\prime}\in\text{In}(R)$. Thus, $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$.

Case 2: $\text{In}(R)\nsubseteq\Delta_{i}$ for any $i\in\\{1,\cdots,K\\}$. By
Definition III.4, each non-source region has at least two parents. Since
$\\{\Delta_{1},\cdots,\Delta_{K}\\}$ is a partition of
$\text{reg}(S_{i_{1}},S_{i_{2}})$, then there exists a subset
$\\{i_{1},i_{2}\\}\subseteq\\{1,\cdots,K\\}$ such that
$\text{In}(R)\cap\Delta_{i_{1}}\neq\emptyset$ and
$\text{In}(R)\cap\Delta_{i_{2}}\neq\emptyset$. Assume
$R^{\prime}_{1}\in\text{In}(R)\cap\Delta_{i_{1}}$ and
$R^{\prime}_{2}\in\text{In}(R)\cap\Delta_{i_{2}}$. Then by condition (2),
$d_{R^{\prime}_{1}}$ and $d_{R^{\prime}_{2}}$ are linearly independent and
$d_{R}\in\langle
d_{R^{\prime}_{1}},d_{R^{\prime}_{2}}\rangle=\langle\alpha_{1},\alpha_{2}\rangle$.
So $d_{R}\in\langle d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle$.

###### Definition A.6

Let $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ be a 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}\\}\cap[[R]]|\leq 1$ for any equivalent
class $[R]\in\mathcal{I}$ and any subclass $[[R]]$ of $[R]$;

  * (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}]_{i}\cup[S_{j}]_{j}\cup(\cup_{\ell=4}^{K}[R_{\ell}]_{i,j})$
for any pair $\\{i,j\\}\subseteq\\{1,2,3\\}$.

Now we can prove Lemma IV.15

######  proof A.7 (Proof of Lemma IV.15)

Since $\mathcal{I}$ is compatible, by Definition IV.12, we can assume
$\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$. Let
$\mathcal{B}_{1}$, $\cdots$, $\mathcal{B}_{K}$ be as in Lemma A.1. We
construct a code $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$
as follows:

  * •

For $j\in\\{1,2,3\\}$ and $R\in[S_{j}]_{j}$, let $d_{R}=\alpha_{j}$;

  * •

For $j\in\\{1,2,3\\}$ and $R\in[S_{j}]_{i_{1},i_{2}}$, let
$d_{R}=\alpha_{i_{1}}+\alpha_{i_{2}}$, where
$\\{i_{1},i_{2}\\}=\\{1,2,3\\}\backslash\\{j\\}$;

  * •

For $j\in\\{4,\cdots,K\\}$, $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$ and
$R\in[R_{j}]_{i_{1},i_{2}}$, let $d_{R}=\beta^{(j)}_{i_{1},i_{2}}$.

We shall prove that
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfies the
conditions of Lemma IV.7.

By the construction of $\tilde{C}_{\Pi}$, we have
$d_{S_{j}}=\alpha_{j},j=1,2,3$. Moreover, since $\mathcal{I}$ is compatible,
then for each $[R_{\ell}]\in\mathcal{I}$ and
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, we have
$[R_{\ell}]_{i_{1},i_{2}}=\text{reg}([R_{\ell}]_{i_{1},i_{2}})$. $($Otherwise,
by Definition III.7, there is an
$R\in\text{reg}([R_{\ell}]_{i_{1},i_{2}})\backslash[R_{\ell}]_{i_{1},i_{2}}$.
By condition (2) of Definition IV.11, $[R_{\ell}]$ and $[R]$ are connected,
which contradicts to the assumption that $\mathcal{I}$ is compatible.$)$ Now,
let $\Delta_{i}=[R_{i}]_{i_{1},i_{2}},i=1,\cdots,K$, where
$[R_{i}]=[S_{i}],i=1,2,3$. By the construction,
$\tilde{C}_{i_{1},i_{2}}=\\{d_{R};R\in\text{reg}(S_{i_{1}},S_{i_{2}})\\}$
satisfies the conditions of Lemma A.4. So $d_{R}\in\langle
d_{R^{\prime}};R^{\prime}\in\text{In}(R)\rangle,\forall
R\in\text{reg}^{\circ}(S_{i_{1}},S_{i_{2}})$.

Finally, we prove that $\tilde{C}_{\Pi}$ satisfies condition (3) of Lemma
IV.7. For each $\Lambda_{j},j\in[n]$, we have the following two cases:

Case 1: There is an $[R_{\ell}]\in\mathcal{I}$ such that $\Lambda_{j}$
intersects with at least two subclasses of $[R_{\ell}]$. Suppose
$Q_{1}\in\Lambda_{j}\cap[[R_{\ell}]]_{1}$ and
$Q_{2}\in\Lambda_{j}\cap[[R_{\ell}]]_{2}$, where $[[R_{\ell}]]_{1}$ and
$[[R_{\ell}]]_{2}$ are two different subclasses of $[R_{\ell}]$. Then by the
construction of $\tilde{C}_{\Pi}$,
$\\{d_{Q_{1}},d_{Q_{2}}\\}\subseteq\mathcal{B}_{\ell}$ and
$\bar{\alpha}\in\langle d_{Q_{1}},d_{Q_{2}}\rangle$.

Case 2: For each $[R_{\ell}]\in\mathcal{I}$, $\Theta_{j}$ intersects with at
most one subclass of $[R_{\ell}]$. Since $\mathcal{I}$ is compatible, then we
can always find a subset $\\{Q_{1},Q_{2},Q_{3}\\}\subseteq\Lambda_{j}$ such
that $\\{Q_{1},Q_{2},Q_{3}\\}$ is an $\mathcal{I}-$independent set. By the
construction of $\tilde{C}_{\Pi}$,
$\\{d_{Q_{1}},d_{Q_{2}},d_{Q_{3}}\\}\nsubseteq\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
and
$\\{d_{Q_{1}},d_{Q_{2}},d_{Q_{3}}\\}\neq\\{\beta^{(\ell)}_{1,2},\beta^{(\ell)}_{1,3},\beta^{(\ell)}_{2,3}\\},\forall\ell\in\\{4,\cdots,K\\}$.
So $d_{Q_{1}},d_{Q_{2}}$ and $d_{Q_{3}}$ are linearly independent. Thus,
$\bar{\alpha}\in\langle d_{Q_{1}},d_{Q_{2}},d_{Q_{3}}\rangle=\mathbb{F}^{3}$.

By the above discussion, $\tilde{C}_{\Pi}$ satisfies the conditions of Lemma
IV.7. So $\text{RG}(D^{**})$ is feasible.

Here, we make an example to illustrate the construction of $\tilde{C}_{\Pi}$
in the proof of Lemma IV.15.

##  Appendix B Proof of Lemma IV.17

Here, we prove Lemma IV.17.

Suppose $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ is a
collection that satisfies the conditions of Lemma IV.7. Note that
$\text{RG}(D^{**})$ is acyclic and $d_{S_{i}}=\alpha_{i}\neq 0,i=1,2,3$. If
there is an $R\in\Pi$ such that $d_{R}=0$, then we can always find an
$R_{0}\in\Pi$ such that $d_{R_{0}}=0$ and $d_{R^{\prime}}\neq 0,\forall
R^{\prime}\in\text{In}(R_{0})$. We redefine $d_{R_{0}}$ by letting
$d_{R_{0}}=d_{R^{\prime}}$ for a fixed $R^{\prime}\in\text{In}(R_{0})$. Then
the resulted code $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ still satisfies the
conditions of Lemma IV.7 and $d_{R_{0}}\neq 0$. We can perform this operation
continuously until $d_{R}\neq 0$ for all $R\in\Pi$ and the resulted code
$\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}$ still satisfies the conditions of Lemma
IV.7. So we can assume, without loss of generality, that $d_{R}\neq 0$ for all
$R\in\Pi$.

To prove Lemma IV.17, the key is to prove that all equivalent class
$[R]\in\mathcal{I}_{c}$ satisfies the following property:

  * •

_Property (a)_ : For any pair $\\{Q,Q^{\prime}\\}\subseteq[R]$,
$d_{Q^{\prime}}\in\langle d_{Q},\bar{\alpha}\rangle$.

To prove this, we first prove the following two lemmas.

###### Lemma B.1

Let $\mathcal{I}$ be a partition of $\Pi$ and $[R]\in\mathcal{I}$ satisfies
Property (a). 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

Since $\tilde{C}_{\Pi}$ satisfies conditions (1) and (2) of Lemma IV.7, then
by Definition III.7, we have
$d_{W}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle,\forall
W\in\text{reg}(S_{i_{1}},S_{i_{2}})$. By assumption and Equation (3),
$\\{Q,Q^{\prime}\\}\subseteq[R]_{i_{1},i_{2}}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$.
So $d_{Q},d_{Q^{\prime}}\in\langle\alpha_{i_{1}},\alpha_{i_{2}}\rangle$.
Meanwhile, since $[R]\in\mathcal{I}$ satisfies Property (a), 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.

We now prove the second claim. If $[R]\neq[S_{i}],\forall i\in\\{1,2,3\\}$,
then by Definition IV.9, $[[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 IV.9, we have the following two cases:

Case 1: $[[R]]=[S_{i}]_{i}=[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$. So the second
claim is true.

###### Lemma B.3

Suppose $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ is a
partition of $\Pi$ in which all equivalent classes satisfy Property (a).
Suppose $\\{[R],[R^{\prime}]\\}\subseteq\mathcal{I}$ and there is a
$\Lambda_{j}$ 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\Lambda_{j}\cap[[R^{\prime}]]$ and
$P^{\prime\prime}\in\Lambda_{j}\cap[[R^{\prime\prime}]]$.

###### proof B.4

Since $\tilde{C}_{\Pi}$ satisfies condition (3) of Lemma IV.7 and
$\Lambda_{j}\subseteq[[R^{\prime}]]\cup[[R^{\prime\prime}]]$, then
$\bar{\alpha}\in\langle d_{R};R\in\Lambda_{j}\rangle=\langle
d_{R};R\in(\Lambda_{j}\cap[[R^{\prime}]])\cup(\Lambda_{j}\cap[[R^{\prime\prime}]])\rangle$.
By Lemma B.1, $\langle
d_{R};R\in(\Lambda_{j}\cap[[R^{\prime}]])\cup(\Lambda_{j}\cap[[R^{\prime\prime}]])\rangle=\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$. So $\bar{\alpha}\in\langle
d_{P^{\prime}},d_{P^{\prime\prime}}\rangle$.

###### Lemma B.5

Suppose $\mathcal{I}=\\{[S_{1}],[S_{2}],[S_{3}],\cdots,[R_{K}]\\}$ is a
partition of $\Pi$ and $\mathcal{I}^{\prime}$ is a contraction of
$\mathcal{I}$ by combining two connected equivalent classes $[R^{\prime}]$ and
$[R^{\prime\prime}]$ in $\mathcal{I}$. If all equivalent classes in
$\mathcal{I}$ satisfy Property (a), then all equivalent classes in
$\mathcal{I}^{\prime}$ satisfy Property (a).

###### proof B.6

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 property (a). Now we suppose
$[R]=[R^{\prime}]\cup[R^{\prime\prime}]$. Since, $[R^{\prime}]$ and
$[R^{\prime\prime}]$ are connected, by Definition IV.11, we have the following
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\Lambda_{j}\cap[[R^{\prime}]]$ and
$P^{\prime\prime}\in\Lambda_{j}\cap[[R^{\prime\prime}]]$. Then
$d_{P^{\prime\prime}}\in\langle d_{P^{\prime}},\bar{\alpha}\rangle$ and
$d_{P^{\prime}}\in\langle d_{P^{\prime\prime}},\bar{\alpha}\rangle$. Since, by
assumption, $[R^{\prime}]$ and $[R^{\prime\prime}]$ satisfy property (a), then
$\langle d_{Q},\bar{\alpha}\rangle=\langle
d_{P^{\prime}},\bar{\alpha}\rangle=\langle
d_{P^{\prime\prime}},\bar{\alpha}\rangle$ and $d_{Q^{\prime}}\in\langle
d_{Q},\bar{\alpha}\rangle,\forall\\{Q,Q^{\prime}\\}\subseteq[R]=[R^{\prime}]\cup[R^{\prime\prime}]$.

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$.
Pick a
$Q_{0}\in\text{reg}([R^{\prime}]_{i_{1},i_{2}})\cap\text{reg}([R^{\prime\prime}]_{i_{1},i_{2}})$.
Since, by assumption, $[R^{\prime}]$ and $[R^{\prime\prime}]$ satisfy property
(a), then $\langle d_{Q},\bar{\alpha}\rangle=\langle
d_{Q_{0}},\bar{\alpha}\rangle=\langle d_{Q^{\prime}},\bar{\alpha}\rangle$ and
$d_{Q^{\prime}}\in\langle
d_{Q},\bar{\alpha}\rangle,\forall\\{Q,Q^{\prime}\\}\subseteq[R]=[R^{\prime}]\cup[R^{\prime\prime}]$.

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

Now we can prove Lemma IV.17.

######  proof B.7 (Proof of Lemma IV.17)

Since each equivalent class $[R]$ in $\mathcal{I}_{0}$ contains exactly one
region $R$, so $[R]$ naturally satisfies property (a) and $[S_{i}]\neq[S_{j}]$
for all $\\{i,j\\}\subseteq\\{1,2,3\\}$.

By Definition IV.13, $\mathcal{I}_{c}=\mathcal{I}_{L}$, where
$\mathcal{I}_{0},\mathcal{I}_{1},\cdots,\mathcal{I}_{L}=\mathcal{I}_{c}$ is a
sequence of partitions of $\Pi$ such that $\mathcal{I}_{\ell}$ is a
contraction of $\mathcal{I}_{\ell-1}$ by combining two connected equivalent
classes in $\mathcal{I}_{\ell-1}$ and, for any
$\\{i,j\\}\subseteq\\{1,2,3\\}$, $[S_{i}]\neq[S_{j}]$ in
$\mathcal{I}_{\ell-1}$, $\ell=1,\cdots,L$. So by Lemma B.5, all equivalent
classes in $\mathcal{I}_{\ell}$ satisfy Property (a). In particular, all
equivalent classes in $\mathcal{I}_{c}=\mathcal{I}_{L}$ satisfies property
(a). Then the conclusion of Lemma IV.17 is obtained by Lemma B.1.

##  Appendix C Proof of Theorem IV.21

Here, we prove Theorem IV.21. First, we prove some lemmas.

###### Lemma C.1

If $\text{RG}(D^{**})$ has two terminal regions, then $\text{RG}(D^{**})$ is
feasible.

###### proof C.2

Suppose $\text{RG}(D^{**})$ has two terminal regions $T_{1}$ and $T_{2}$. We
have the following two cases:

Case 1: $\Omega_{1,2}\neq\emptyset$. Then there is a $Q\in
D^{**}\backslash\Pi$ such that $Q\rightarrow T_{i},i=1,2$. Similar to what we
did in Remark IV.4, we can first construct a code on the set $\\{R\in
D^{**};R\rightarrow Q\\}$ such that $d_{Q}=\bar{\alpha}$. Then for all $R$
such that $Q\rightarrow R\rightarrow T_{i}$ for some $i\in\\{1,2\\}$, let
$d_{R}=\bar{\alpha}$. By this construction, we obtain a solution of
$\text{RG}(D^{**})$. So $\text{RG}(D^{**})$ is feasible.

Case 2: $\Omega_{1,2}=\emptyset$. Then $\text{RG}(D^{**})$ is terminal
separable. From Lemma IV.5, we have
$\Lambda_{j}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\},$
and $|\Lambda_{j}|\geq 2,j=1,2$. By enumerating, we have the following three
subcases:

Case 2.1: $|\Lambda_{1}|>2$ and $|\Lambda_{2}|>2$. Let
$\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$, where $[R]=\\{R\\}$ for all $R\in\Pi$.
Clearly, $\mathcal{I}_{0}$ is a partition of $\Pi$ and is compatible. By Lemma
IV.15, $\text{RG}(D^{**})$ is feasible.

Case 2.2: $|\Lambda_{1}|>2$ and $|\Lambda_{2}|=2$. Let
$\mathcal{I}=\\{\Lambda_{2}\\}\cup\\{[R];R\in\Pi\backslash\Lambda_{2}\\}$,
where $[R]=\\{R\\}$ for all $R\in\Pi\backslash\Lambda_{2}$. Clearly,
$\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma IV.15,
$\text{RG}(D^{**})$ is feasible.

Case 2.3: $|\Lambda_{1}|=|\Lambda_{2}|=2$ and
$\Lambda_{1}\cap\Lambda_{2}=\emptyset$. Let
$\mathcal{I}=\\{\Lambda_{1},\Lambda_{2}\\}\cup\\{[R];R\in\Pi\backslash(\Lambda_{1}\cup\Lambda_{2})\\}$,
where $[R]=\\{R\\}$ for all $R\in\Pi\backslash(\Lambda_{1}\cup\Lambda_{2})$.
Clearly, $\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma
IV.15, $\text{RG}(D^{**})$ is feasible.

Case 2.4: $|\Lambda_{1}|=|\Lambda_{2}|=2$ and
$\Lambda_{1}\cap\Lambda_{2}\neq\emptyset$. If $\Lambda_{1}=\Lambda_{2}$, then
it is easy to construct a code $\tilde{C}_{\Pi}$ satisfies the conditions of
Lemma IV.7. So $\text{RG}(D^{**})$ is feasible. Thus, we can assume
$\Lambda_{1}\neq\Lambda_{2}$. Then by proper naming, we can assume
$\Lambda_{1}=\\{Q_{1},Q_{2}\\}$ and $\Lambda_{2}=\\{Q_{1},Q_{3}\\}$. By Lemma
IV.5, $\\{Q_{1},Q_{2}\\}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$ and
$\\{Q_{1},Q_{3}\\}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$ for all
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Then one of the following two cases
hold:

Case 2.4.1: $\\{Q_{2},Q_{3}\\}\subseteq\text{reg}(S_{i_{1}},S_{i_{2}})$ for
some $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Let
$\mathcal{I}=\\{[Q_{1}]\\}\cup\\{[R];R\in\Pi\backslash[Q_{1}]\\}$, where
$[Q_{1}]=\\{Q_{1}\\}\cup\text{reg}(Q_{2},Q_{3})$ and $[R]=\\{R\\}$ for all
$R\in\Pi\backslash[Q_{1}]$. Clearly, $\mathcal{I}$ is a partition of $\Pi$ and
is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is feasible.

Case 2.4.2: $\\{Q_{2},Q_{3}\\}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$ for
all $\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$. Let
$\mathcal{I}=\\{[Q_{1}]\\}\cup\\{[R];R\in\Pi\backslash[Q_{1}]\\}$, where
$[Q_{1}]=\\{Q_{1},Q_{2},Q_{3}\\}$ and $[R]=\\{R\\}$ for all
$R\in\Pi\backslash[Q_{1}]$. Clearly, $\mathcal{I}$ is a partition of $\Pi$ and
is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is feasible.

By the above discussions, we proved that $\text{RG}(D^{**})$ is feasible.

###### Lemma C.3

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

  * (1)

$|\Lambda_{j_{1}}|\geq 3$ and $|\Lambda_{j_{2}}|\geq 3$ for some
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$;

  * (2)

For any $\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$, if
$|\Lambda_{j_{1}}|=|\Lambda_{j_{2}}|=2$, then
$\Lambda_{j_{1}}\cap\Lambda_{j_{2}}=\emptyset$;

  * (3)

$S_{i}\notin\Lambda_{j}$ for all $i,j\in\\{1,2,3\\}$;

  * (4)

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

###### proof C.4

1) Suppose condition (1) holds. Let
$j_{3}\in\\{1,2,3\\}\backslash\\{j_{1},j_{2}\\}$. From Lemma IV.5, we have
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\},$
and $|\Lambda_{j_{3}}|\geq 2$. Then we have the following two cases:

Case 1: $|\Lambda_{j_{3}}|>2$. Let $\mathcal{I}_{0}=\\{[R];R\in\Pi\\}$, where
$[R]=\\{R\\}$ for all $R\in\Pi$. Clearly, $\mathcal{I}_{0}$ is a partition of
$\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is feasible.

Case 2: $|\Lambda_{j_{3}}|=2$. Let
$\mathcal{I}=\\{\Lambda_{j_{3}}\\}\cup\\{[R];R\in\Pi\backslash\Lambda_{j_{3}}\\}$,
where $[R]=\\{R\\}$ for all $R\in\Pi\backslash\Lambda_{j_{3}}$. Clearly,
$\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma IV.15,
$\text{RG}(D^{**})$ is feasible.

2) Suppose condition (2) holds. Let $A\subseteq\\{1,2,3\\}$ be such that
$|\Lambda_{j}|=2,\forall j\in A$, and $|\Lambda_{j}|>2,\forall
j\in\\{1,2,3\\}\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})$. Clearly,
$\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma IV.15,
$\text{RG}(D^{**})$ is feasible.

3) Suppose condition (3) 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}\\}$. Clearly, $\mathcal{I}$ is a
partition of $\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is
feasible.

4) 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}]=\text{reg}(S_{1},S_{2})\cup\text{reg}(S_{1},S_{3})\cup\text{reg}^{\circ}(S_{2},S_{3})$,
$[S_{2}]=\\{S_{2}\\}$ and $[S_{3}]=\\{S_{3}\\}$. Clearly, $\mathcal{I}$ is a
partition of $\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is
feasible.

###### Lemma C.5

Suppose $\text{RG}(D^{**})$ has three terminal regions and is terminal
separable. If $\text{RG}(D^{**})$ is not feasible, then the condition (C-IR)
holds.

###### proof C.6

If $\Lambda_{j_{1}}=\Lambda_{j_{2}}$ for some
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$, then by lemma C.1, we can construct a
code $\tilde{C}_{\Pi}$ satisfies the conditions of Lemma IV.7. So
$\text{RG}(D^{**})$ is feasible. Thus, we assume $\Lambda_{1},\Lambda_{2}$ and
$\Lambda_{3}$ are mutually different. Since $\text{RG}(D^{**})$ is not
feasible, then by (1), (2) of Lemma C.3, there is a
$\\{j_{1},j_{2}\\}\subseteq\\{1,2,3\\}$ such that

$\displaystyle|\Lambda_{j_{1}}|=|\Lambda_{j_{2}}|=2~{}\text{and}~{}|\Lambda_{j_{1}}\cap\Lambda_{j_{2}}|=1.$
(10)

Let $j_{3}\in\\{1,2,3\\}\backslash\\{j_{1},j_{2}\\}$. By enumerating, we can
divide our discussion into the following cases:

Case 1:
$\Lambda_{j_{1}}\cup\Lambda_{j_{2}}\subseteq\text{reg}^{\circ}(S_{1},S_{2})\cup\text{reg}^{\circ}(S_{1},S_{3})\cup\text{reg}^{\circ}(S_{2},S_{3}).$
By (10), we can assume

$\displaystyle\Lambda_{j_{1}}=\\{P_{1},P_{2}\\}~{}\text{and}~{}\Lambda_{j_{2}}=\\{P_{0},P_{2}\\}.$
(11)

By Lemma IV.5,
$\Lambda_{j_{1}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Then by proper naming, we can assume

$\displaystyle
P_{2}\in\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})~{}\text{and}~{}P_{1}\in\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}}).$
(12)

where $\\{\ell_{1},\ell_{2},\ell_{3}\\}$ is a fixed permutation of
$\\{1,2,3\\}$. Also, by Lemma IV.5,
$\Lambda_{j_{2}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Then for $P_{0}$, we have the following subcases:

Case 1.1: $P_{0}\in\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})$. We can
further divide this case into the following two subcases:

Case 1.1.1:
$\Lambda_{j_{3}}\cap(\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}}))\neq\emptyset$.
By (4) of Lemma C.3, $\text{RG}(D^{**})$ is feasible.

Case 1.1.2:
$\Lambda_{j_{3}}\cap(\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}}))=\emptyset$.
Then
$\Lambda_{j_{3}}\subseteq\text{reg}(S_{\ell_{1}},S_{\ell_{3}})\cup\\{S_{\ell_{2}}\\}$.
Moreover, since by Lemma IV.5,
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then either $\Lambda_{j_{3}}=\\{S_{1},S_{2},S_{3}\\}$ or
$\\{Q,S_{\ell_{2}}\\}\subseteq\Lambda_{j_{3}}$ for some
$Q\in\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{3}})$.

Let $\mathcal{I}=\\{[S_{\ell_{1}}],[S_{\ell_{2}}],[S_{\ell_{3}}],[P_{2}]\\}$,
where $[S_{\ell_{1}}]=\\{S_{\ell_{1}}\\}$,
$[S_{\ell_{2}}]=\\{S_{\ell_{2}}\\}\cup\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{3}})$,
$[S_{\ell_{3}}]=\\{S_{\ell_{3}}\\}$ and
$[P_{2}]=\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})$.
Clearly, $\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma
IV.15, $\text{RG}(D^{**})$ is feasible.

Case 1.2: $P_{0}\in\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{3}})$. This case
can be further divided into the following subcases:

Case 1.2.1: $|\Lambda_{j_{3}}|=3$ or
$\Lambda_{j_{3}}\subseteq\\{P_{0},P_{1},P_{2}\\}$. Let
$\mathcal{I}=\\{[P_{2}]\\}\cup\\{[R];R\in\Pi\backslash[P_{0}]\\}$, where
$[P_{2}]=\\{P_{0},P_{1},P_{2}\\}$ and $[R]=\\{R\\},\forall
R\in\Pi\backslash[P_{2}]$. Clearly, $\mathcal{I}$ is a partition of $\Pi$ and
is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is feasible.

Case 1.2.2: $|\Lambda_{j_{3}}|=2$ and
$\Lambda_{j_{3}}\cap\\{P_{0},P_{1},P_{2}\\}=\emptyset$. Assume
$\Lambda_{j_{3}}=\\{P_{3},P_{4}\\}$. Let
$\mathcal{I}=\\{[P_{2}],[P_{3}]\\}\cup\\{[R];R\in\Pi\backslash([P_{2}]\cup[P_{3}])\\}$,
where $[P_{2}]=\\{P_{0},P_{1},P_{2}\\},[P_{3}]=\\{P_{3},P_{4}\\}$ and
$[R]=\\{R\\},\forall R\in\Pi\backslash([P_{2}]\cup[P_{3}])$. Clearly,
$\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma IV.15,
$\text{RG}(D^{**})$ is feasible.

Case 1.2.3: $|\Lambda_{j_{3}}|=2$ and
$\Lambda_{j_{3}}\cap\\{P_{0},P_{1},P_{2}\\}=\\{P_{2}\\}$. By (4) of Lemma C.3,
$\text{RG}(D^{**})$ is feasible.

Case 1.2.4: $|\Lambda_{j_{3}}|=2$ and
$\Lambda_{j_{3}}\cap\\{P_{0},P_{1},P_{2}\\}=\\{P_{1}\\}~{}($or $\\{P_{0}\\})$.
By proper naming, we can assume $\Lambda_{j_{3}}=\\{P_{1},P_{3}\\}$, where
$P_{3}\notin\\{P_{0},P_{1},P_{2}\\}$. If $P_{3}\neq
S_{\ell},\forall\ell\in\\{1,2,3\\}$, then by (3) of Lemma C.3,
$\text{RG}(D^{**})$ is feasible. So we assume $P_{3}=S_{\ell}$ for some
$\ell\in\\{1,2,3\\}$. Since
$P_{1}\in\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})$ and, by Lemma IV.5,
$\Lambda_{j_{3}}=\\{P_{1},P_{3}\\}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then $P_{3}=S_{\ell_{1}}$. Let $j_{3}=1,j_{1}=2,j_{2}=3$ and
$\ell_{i}=i~{}(i=1,2,3)$. Then the condition (C-IR) holds.

Case 2: There is an $\ell_{1}\in\\{1,2,3\\}$ such that
$S_{\ell_{1}}\in\Lambda_{j_{1}}\cup\Lambda_{j_{2}}$. Let
$\\{\ell_{2},\ell_{3}\\}=\\{1,2,3\\}\backslash\\{\ell_{1}\\}$. We can further
divide this case into the following subcases:

Case 2.1: $S_{\ell_{1}}\in\Lambda_{j_{1}}\cap\Lambda_{j_{2}}$. By proper
naming, we assume

$\displaystyle\Lambda_{j_{1}}=\\{S_{\ell_{1}},P_{1}\\}~{}\text{and}~{}\Lambda_{j_{2}}=\\{S_{\ell_{1}},P_{2}\\}.$
(13)

Since, by Lemma IV.5, $\Lambda_{j_{1}}$,
$\Lambda_{j_{2}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then we have

$\displaystyle P_{1},P_{2}\in\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}}).$
(14)

If
$\Lambda_{j_{3}}\cap\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})\neq\emptyset$,
then by (4) of Lemma C.3, $\text{RG}(D^{**})$ is feasible. So we assume
$\Lambda_{j_{3}}\cap\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})=\emptyset$.
Then

$\displaystyle\Lambda_{j_{3}}\subseteq\text{reg}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}(S_{\ell_{1}},S_{\ell_{3}}).$
(15)

We have the following two subcases:

Case 2.1.1:
$\Lambda_{j_{3}}\cap(\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{3}}))\neq\emptyset$.
Without loss of generality, assume
$Q_{1}\in\Lambda_{j_{3}}\cap\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})$.
Since, by Lemma IV.5,
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then there is a
$Q_{2}\in\text{reg}(S_{\ell_{1}},S_{\ell_{3}})\backslash\\{S_{\ell_{1}}\\}$
such that $Q_{2}\in\Lambda_{j_{3}}$. Let
$\mathcal{I}=\\{[S_{\ell_{1}}],[S_{\ell_{3}}]\\}\cup\\{[R];R\in\Pi\backslash([S_{\ell_{1}}]\cup[S_{\ell_{3}}])\\}$,
where $[S_{\ell_{1}}]=\\{S_{\ell_{1}}\\}\cup\text{reg}(P_{1},P_{2})$,
$[S_{\ell_{3}}]=\\{Q_{1}\\}\cup\text{reg}(S_{\ell_{1}},S_{\ell_{3}})\backslash\\{S_{\ell_{1}}\\}$
and $[R]=\\{R\\},\forall R\in\Pi\backslash([S_{\ell_{1}}]\cup[S_{\ell_{3}}])$.
Clearly, $\mathcal{I}$ is a partition of $\Pi$ and is compatible. By Lemma
IV.15, $\text{RG}(D^{**})$ is feasible.

Case 2.1.2:
$\Lambda_{j_{3}}\cap(\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{3}}))=\emptyset$.
By (15), $\Lambda_{j_{3}}\subseteq\\{S_{1},S_{2},S_{3}\\}$. Since, by Lemma
IV.5,
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then $\Lambda_{j_{3}}=\\{S_{1},S_{2},S_{3}\\}$. Let
$\mathcal{I}=\\{[S_{\ell_{1}}]\\}\cup\\{[R];R\in\Pi\backslash[S_{\ell_{1}}]\\}$,
where $[S_{\ell_{1}}]=\\{S_{\ell_{1}}\\}\cup\text{reg}(P_{1},P_{2})$ and
$[R]=\\{R\\},\forall R\in\Pi\backslash[S_{\ell_{1}}]$. Clearly, $\mathcal{I}$
is a partition of $\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$
is feasible.

Case 2.2: $S_{\ell_{1}}\notin\Lambda_{j_{1}}\cap\Lambda_{j_{2}}$. Since
$S_{\ell_{1}}\in\Lambda_{j_{1}}\cup\Lambda_{j_{2}}$, then by (10) and proper
naming, we can assume
$\Lambda_{j_{1}}=\\{S_{\ell_{1}},P_{1}\\},\Lambda_{j_{2}}=\\{P_{1},P_{2}\\}$.
Since, by Lemma IV.5,
$\Lambda_{j_{1}},\Lambda_{j_{2}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$,
then $P_{1}\in\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})$ and, by proper
naming, we can assume $P_{2}\in\text{reg}^{\circ}(S_{\ell_{1}},S_{\ell_{2}})$,
where $\\{\ell_{2},\ell_{3}\\}=\\{1,2,3\\}\backslash\\{\ell_{1}\\}$. Let
$j_{3}\in\\{1,2,3\\}\backslash\\{j_{1},j_{2}\\}$. If
$\Lambda_{j_{3}}\cap\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})\neq\emptyset$,
then by (4) of Lemma C.3, $\text{RG}(D^{**})$ is feasible. So we assume
$\Lambda_{j_{3}}\cap\text{reg}^{\circ}(S_{\ell_{2}},S_{\ell_{3}})=\emptyset$.
Then

$\displaystyle\Lambda_{j_{3}}\subseteq\text{reg}(S_{\ell_{1}},S_{\ell_{2}})\cup\text{reg}(S_{\ell_{1}},S_{\ell_{3}}).$
(16)

Now, suppose

$\displaystyle\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{\ell_{1}},P_{2})\cup\text{reg}(S_{\ell_{1}},S_{\ell_{3}}).$
(17)

We shall prove $\text{RG}(D^{**})$ is feasible. We have the following three
subcases:

Case 2.2.1: $\Lambda_{j_{3}}\cap\text{reg}(S_{\ell_{1}},P_{2})\neq\emptyset$.
Since, by Lemma IV.5,
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}})$ for all
$\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$, then by (16),
$\Lambda_{j_{3}}\cap(\text{reg}(S_{\ell_{1}},S_{\ell_{3}})\backslash\\{S_{\ell_{1}}\\})\neq\emptyset.$
Moreover, by (17),
$\Lambda_{j_{3}}\cap(\text{reg}(S_{\ell_{1}},S_{\ell_{2}})\backslash\text{reg}(S_{\ell_{1}},P_{2}))\neq\emptyset$.
Let
$\mathcal{I}=\\{[S_{\ell_{1}}]\\}\cup\\{[R];R\in\Pi\backslash[S_{\ell_{1}}]\\}$,
where $[S_{\ell_{1}}]=\text{reg}(S_{\ell_{1}},P_{2})\cup\\{P_{1}\\}$ and
$[R]=\\{R\\},\forall R\in\Pi\backslash[S_{\ell_{1}}]\\}$. Then $\mathcal{I}$
is a partition of $\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$
is feasible.

Case 2.2.2: $\Lambda_{j_{3}}\cap\text{reg}(S_{\ell_{1}},P_{2})=\emptyset$ and
$|\Lambda_{j_{3}}|\geq 3.$ As in Case 2.2.1, we can prove $\mathcal{S}$ is
regular.

Case 2.2.3: $\Lambda_{j_{3}}\cap\text{reg}(S_{\ell_{1}},P_{2})=\emptyset$ and
$|\Lambda_{j_{3}}|=2.$ Since, by Lemma IV.5,
$\Lambda_{j_{3}}\nsubseteq\text{reg}(S_{i_{1}},S_{i_{2}}),\forall\\{i_{1},i_{2}\\}\subseteq\\{1,2,3\\}$.
Then by Equations (16), (17) and proper naming, we can assume
$\Lambda_{j_{3}}=\\{P_{3},P_{4}\\}$, where
$P_{3}\in\text{reg}(S_{\ell_{1}},S_{\ell_{2}})\backslash(\text{reg}(S_{\ell_{1}},P_{2})\cup\\{S_{\ell_{2}}\\})$
and
$P_{4}\in\text{reg}(S_{\ell_{1}},S_{\ell_{3}})\backslash\\{S_{\ell_{1}}\\}$.
Let
$\mathcal{I}=\\{[S_{\ell_{1}}],[P_{3}]\\}\cup\\{[R];R\in\Pi\backslash[S_{\ell_{1}}]\cup[P_{3}]\\}$,
where $[S_{\ell_{1}}]=\text{reg}(S_{\ell_{1}},P_{2})\cup\\{P_{1}\\}$,
$[P_{3}]=\\{P_{3},P_{4}\\}$ and $[R]=\\{R\\},\forall
R\in\Pi\backslash[S_{\ell_{1}}]\cup[P_{3}]\\}$. Then $\mathcal{I}$ is a
partition of $\Pi$ and is compatible. By Lemma IV.15, $\text{RG}(D^{**})$ is
feasible.

So for case 2.2, if $\text{RG}(D^{**})$ is not feasible, then
$\Lambda_{j_{3}}\subseteq\text{reg}(S_{\ell_{1}},P_{2})\cup\text{reg}(S_{\ell_{1}},S_{\ell_{3}})$.
Let $\ell_{i}=j_{i}=i,i=1,2,3$. Then the condition (C-IR) holds.

Combining the discussions for all cases above, we can conclude that if
$\text{RG}(D^{**})$ is not feasible, then the condition (C-IR) holds.

###### Lemma C.7

Suppose $\text{RG}(D^{**})$ has three terminal regions and is terminal
separable. If the condition (C-IR) holds, then $\text{RG}(D^{**})$ is not
feasible.

###### proof C.8

We prove this lemma by contradiction. For this purpose, we suppose
$\text{RG}(D^{**})$ is feasible and the condition (C-IR) holds. Then there is
a code $\tilde{C}_{\Pi}=\\{d_{R};R\in\Pi\\}\subseteq\mathbb{F}^{3}$ satisfying
conditions of Lemma IV.7. Since $P_{1}\in\text{reg}^{\circ}(S_{2},S_{3})$,
then by Definition III.7 and condition (2) of Lemma IV.7, we have

$d_{P_{1}}\in\langle\alpha_{2},\alpha_{3}\rangle.$

Moreover, since $\Lambda_{1}=\\{S_{1},P_{1}\\}$, then by conditions (1), (3)
of Lemma IV.7, we have $\bar{\alpha}\in\langle\alpha_{1},d_{P_{1}}\rangle$. So

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

Similarly, since $\Lambda_{2}=\\{P_{1},P_{2}\\}$ and
$P_{2}\in\text{reg}^{\circ}(S_{1},S_{2})$, then

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

By Definition III.7 and condition (2) of Lemma IV.7,
$d_{R}\in\langle\alpha_{1}\rangle$ for all $R\in\text{reg}(S_{1},P_{2})$ and
$d_{R}\in\langle\alpha_{1},\alpha_{3}\rangle$ for all
$R\in\text{reg}(S_{1},S_{3})$. Since
$\Lambda_{3}\subseteq\text{reg}(S_{1},P_{2})\cup\text{reg}(S_{1},S_{3})$, then

$\langle
d_{R};R\in\Lambda_{3}\rangle\subseteq\langle\alpha_{1},\alpha_{3}\rangle.$

By condition (3) of Lemma IV.7, we have $\bar{\alpha}\in\langle
d_{R};R\in\Lambda_{3}\rangle\subseteq\langle\alpha_{1},\alpha_{3}\rangle$, a
contradiction. Thus, we can conclude that if the condition (C-IR) holds, then
$\text{RG}(D^{**})$ is not feasible.

Now, we can prove Theorem IV.21.

######  proof C.9 (Proof of Theorem IV.21)

By enumerating, one of the following three cases hold:

Case 1: $\Omega_{1,2,3}\neq\emptyset$. Then there is a $Q\in
D^{**}\backslash\Pi$ such that $Q\rightarrow T_{i},i=1,2,3$. Similar to what
we did in Remark IV.4, we can first construct a code on the set $\\{R\in
D^{**};R\rightarrow Q\\}$ such that $d_{Q}=\bar{\alpha}$. Then for all $R$
such that $Q\rightarrow R\rightarrow T_{i}$ for some $i\in\\{1,2,3\\}$, let
$d_{R}=\bar{\alpha}$. By this construction, we obtain a solution of
$\text{RG}(D^{**})$. So $\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\\}$. Then there is a $Q\in
D^{**}\backslash\Pi$ such that $Q\rightarrow T_{i_{1}}$ and $Q\rightarrow
T_{i_{2}}$. Let $i_{3}\in\\{1,2,3\\}\backslash\\{i_{1},i_{2}\\}$. We can view
$T_{i_{3}}$ and $Q$ as two terminal regions and, by Lemma C.1, we can
construct a code on the set $\\{R\in D^{**};R\rightarrow
Q~{}\text{or}~{}R\rightarrow T_{i_{3}}\\}$ such that
$d_{Q}=d_{T_{i_{3}}}=\bar{\alpha}$. Moreover, for all $R$ such that
$Q\rightarrow R\rightarrow T_{i_{1}}$ or $Q\rightarrow R\rightarrow
T_{i_{2}}$, let $d_{R}=\bar{\alpha}$. Then we obtain a solution of
$\text{RG}(D^{**})$. So $\text{RG}(D^{**})$ is feasible.

Case 3: $\text{RG}(D^{**})$ is terminal separable. By Lemma C.5 and C.7,
$\text{RG}(D^{**})$ is not feasible if and only if, by proper naming, the
condition (C-IR) holds.

By the above discussion, we proved Theorem IV.21.