3 Network Coding for s/nt Sum-Networks Wentu Song∗, Chau Yuen∗, Kai Cai†, and Rongquan Feng‡ ∗Singapore University of Technology and Design †Department of Mathematics, University of Hong Kong ‡School of Mathematical Sciences, Peking University, Peking, China Emails: wentu [email protected]; [email protected];[email protected]; [email protected] Abstract—A sum-network isa directed acyclic network where proposedinsectionIII.ThemainresultispresentedinSection each source independently generates one symbol from a given IV. The paper is concluded in Section V. 4 field F and each terminal wants to receive the sum (over F) 1 of the source symbols. For sum-networks with two sources or II. MODELS AND NOTATIONS 0 two terminals, the solvability is characterized by the connection We consider a directed, acyclic, finite graph G = (V,E) 2 condition of each source-terminal pair [3]. A necessary and sufficient condition for the solvability of the 3-source 3-terminal with a set of k sources {s1,··· ,sk} and a set of n terminals n a (3s/3t)sum-networkswasgivenbyShenviandDey[6].However, (sinks){t1,··· ,tn}.EachsourcesigeneratesamessageXi ∈ J the general case of arbitrary sources/sinks is still open. In this F and each terminal tj wants to get the sum Pki=1Xi, where 6 paper, we investigate the sum-network with three sources and Fisafinitefield.Weassumethateachlinkiserror-free,delay- n sinks using a region decomposition method. A sufficient and 1 free and can carry one symbol from the field in each use. We necessary condition is established for a class of 3s/nt sum- networks. As a direct application of this result, a necessary and call such network as a ks/nt sum-network. T] sufficient condition of solvability is obtained for the special case For a link e = (u,v) ∈ E, u is called the tail of e and of 3s/3t sum-networks. v is called the head of e, and are denoted by u = tail(e) I . and v = head(e), respectively. We call e an incoming link s c I. INTRODUCTION of v (an outgoing link of u). For two links e,e′ ∈ E, we [ Network coding allows intermediate nodes of a communi- call e′ an incoming link of e (e an outgoing link of e′) if 1 cation network to combine the incoming information before tail(e) = head(e′). For any e ∈ E, denoted by In(e) the set v forwarding it, and was shown to have significant throughput of incoming links of e. 1 advantages as opposed to the conventional store-and-forward To aid analysis, we assume that each source si has an 4 9 scheme [1], [2]. imaginaryincominglink,calledtheXisourcelink(orasource 3 Mostoftheexistentworksofnetworkcodingfocusonhow linkforshort),andeachterminaltj hasanimaginaryoutgoing . the terminal nodes recover the whole or part of the original link,called a terminallink. Note thatthe sourcelinkshaveno 1 messages. Recently, network coding for communicating the tailandtheterminallinkshavenohead.Asaresult,thesource 0 4 sumofsourcemessagestotheterminalnodeswasinvestigated links have no incoming link. For the sake of convenience, if 1 [3]-[8]. Such a network is called as a sum-network. The e∈E is not a source link, we call e a non-source link. v: problem of communicating sums over networks is in fact a Let Fk be the k-dimensional vector space over the finite i subclass of the problem of distributed function computation, field F. For any subset A ⊆ Fk, let hAi denote the subspace X which has been considered in different contexts [9]-[12]. ofFk spannedbyA. Fori∈{1,··· ,k},we letαi denotethe r It was shown in [3] that for directed acyclic graphs with vector of Fk with the ith component being one and all other a unit capacity edges and independent, unit-entropy sources, components being zero. Meanwhile, we let α¯ = Pki=1αi = if there are two sources or two terminals in the network, (1,1,··· ,1), i.e., the vector with all components being one. then the network is solvable if and only if every source For any linear network coding scheme, the message along is connected to every terminal. For the 3-source 3-terminal any link e is a linear combination Me = Pki=1ciXi of the (3s/3t)sum-networks,anecessaryandsufficientconditionfor source messages and we use the correspondingcoding vector the solvability over any field is given in [6]. However, for de = (c1,··· ,ck) to represent the message, where ci ∈ F. networks with arbitrary number of sources and terminals, no To ensure the computability of network coding, the outgoing necessary and sufficient condition is known. message, as a k-dimensional vector, must be in the span of In this paper, we consider the sum-networks with three all incoming messages. Moreover,to ensure that all terminals sources using the technique of region decomposition [14], receive the sum Pki=1Xi, if e is a terminal link of the sum- [15]. We give a necessary and sufficient condition for the network, then de = Pki=1αi = α¯. Thus, we can define a solvability of a subclass of 3s/nt sum-networks. As a result, linear network code of a ks/nt sum-network as follows: wegiveasimplecharacterizationofsolvabilityforthespecial Definition 2.1 (Linear Network Code): Let G = (V,E) be case of 3s/3t sum-networks. a ks/nt sum-network.A linear code (LC) of G over the field This paper is organizedas follows. In Section II, we intro- F is a collection of vectors C ={de ∈Fk;e∈E} such that ducethenetworkmodelandthenotations.Themethodologyis (1) d =α if e is the X source link (i=1,··· ,k); e i i 1 2 3 s s s 1 5 6 2 7 8 3 S1 S2 S3 S1 S2 S3 4 v v 9 1 2 10 11 R1 R2 R1′ v v 132 13 14154 16v5 R3 R2′ 17 t1 t2 t3 T1 T2 T3 T1 T2 T3 18 19 20 (a) (b) (c) Fig 1. Examples of region graph: (a) is a 3s/3t sum-network G1, where all links are sequentially indexed as 1,2,···,20. Here, the imaginary links 1,2,3 are the X1,X2,X3 source link, and 18,19,20 are the terminal links at terminal t1,t2,t3 respectively. (b) is the region graph RG(D), where S1 = {1,4,5},S2 = {2,6,7},S3 = {3,8,9},R1 = {10,12,13},R2 = {11,14,15,16},R3 = {17},T1 = {18},T2 = {19},T3 = {20} and D = {{1S11,,1S42,,1S53,,1R6,11,7R}2,,TR13=,T{11,8T}2,,TT23}=. ({c1)9i}s,tTh3e=reg{io2n0}graanpdhDR′G=(D{′S),1w,Sh2e,reS3S,1R=′1,R{1′2,,4T,15,}T,2S,2T=3}.{2,6,7},S3 = {3,8,9},R′1 = {10,12,13},R′2 = (2) de ∈hde′;e′ ∈In(e)i if e is a non-source link. We use RG(D) to denote the region graph of G about D, ThecodeC ={de ∈Fk;e∈E}issaidtobealinearsolution i.e., RG(D) = (D,ED). If (R′,R) is an edge of RG(D), we of G if d =α¯ for all terminal link e. call R′ a parent of R. For R ∈ D, we use In(R) to denote e Thevectord iscalledtheglobalencodingvectoroflinke. the set of parents of R in RG(D). Since the source links e ThenetworkGissaid tobesolvableifithasalinearsolution havenoincominglink,thenthesourceregionshavenoparent. over some finite field F. Moreover, since G is acyclic, then clearly, RG(D) is acyclic. ForR,R′ ∈D,apathinRG(D)fromR′toRisasequence III. REGION DECOMPOSITION AND NETWORK CODING of regions {R = R′,R ,··· ,R = R} such that R is a 0 1 p i−1 In this section, we present the region decomposition ap- parentofR ,i=1,··· ,p. Ifthereisa pathfromR′ toR,we i proach,whichwilltakeakeyroleinourdiscussion.Thebasic say R′ is connected to R and denote R′ → R. Else, we say idea of region decomposition is proposed in [14], [15]. R′ is not connected to R and denote R′ 9 R. In particular, A. Region Decomposition and Region Graph we regard R→R for all R∈D. Definition 3.1 (Region and Region Decomposition): Let R B. Network Coding on Region Graph be a non-empty subset of E. R is called a region of G if there is an el ∈ R such that for any e ∈ R and e 6= el, Definition 3.3 (Codes on Region Graph): A linear code R contains an incoming link of e. If E is partitioned into (LC)oftheregiongraphRG(D)overthefieldFisacollection mutually disjoint regions, say R1,R2,··· ,RN, then we call of vectors C˜ ={dR ∈Fk;R∈D} such that D ={R ,R ,··· ,R } a region decomposition of G. 1 2 N (1) d = α , where S is the X source region for each The edge e in Definition 3.1 is called the leader of R and Si i i i l i∈{1,··· ,k}; is denoted as e = lead(R). A region R is called the X l i (2) dR ∈hdR′;R′ ∈In(R)i if R is a non-source region. source region (or a source region for short) if lead(R) is the X source link; R is called a terminal region if R contains a The code C˜ = {dR ∈ Fk;R ∈ D} is said to be a linear i solution of RG(D) if d =α¯ for each terminal region T . terminal link. If R is neither a source region nor a terminal Tj j region,we callRa codingregion.IfRisnotasourceregion, The vector dR is called the global encoding vector of R. we call R a non-source region. TheregiongraphRG(D)issaidtobefeasibleifithasalinear Since the source links have no incoming link, then each solution over some finite field F. source region containsexactly one source link, i.e., its leader. By Definition 3.3, for any linear solution of RG(D), it is But a terminal region may contains more than one terminal always be that dSi =αi and dTj =α¯. So in order to obtain a links. So there are exactly k source region and at most n solution, we only need to specify the global encoding vector terminal regions for any ks/nt sum-network. We will always for each coding region. denote the k source regionsas S ,··· ,S and the n terminal Let D be a region decomposition of G. Clearly, any linear 1 k regions as T ,··· ,T . solution of RG(D) can be extended to a linear solution of G 1 n Definition 3.2 (Region Graph): Let D be a region decom- by letting de = dR for each R ∈ D and each e ∈ R. So if position of G. The region graph of G about D is a directed, RG(D) is feasible, then G is solvable.But conversely,if G is simple graphwith vertexset D and edge set E , where E is solvable, it is not necessary that RG(D) is feasible. D D the set of all ordered pairs (R′,R) such that R′ contains an FortheregiongraphRG(D)inFig.1(b),letd =α and R1 1 incoming link of lead(R). d = d = α +α . Then C˜ = {d ;R ∈ D} is a linear R2 R3 2 3 R ConsidertheexamplenetworkG inFig.1(a).Examplesof solution of RG(D) and we can obtain a linear solution of G 1 1 two region graphsare shown in Fig. 1 (b) and (c). In general, bylettingd =d foreachR∈D andeache∈R.However, e R G may have many region decompositions. the region graph RG(D′) in Fig. 1 (c) is not feasible because for any linear code, by conditions (1), (2) of Definition 3.3, Lemma 3.9: Suppose Θ and Θ are two subsets of D. 1 2 d ∈hα ,α i. So it is impossible that d =α¯. Then reg(Θ )∩reg(Θ )=reg(Θ), where T1 1 3 T1 1 2 In the following,we shall definea specialregiondecompo- Θ=(reg(Θ )∩Θ )∪(reg(Θ )∩Θ ). sition D∗∗ of G, called the basic region decomposition of G, 1 2 2 1 whichis uniqueand hasthepropertythatGis solvableif and Proof: Clearly, Θ⊆reg(Θ ) and Θ⊆reg(Θ ). Then by 1 2 only if the region graph RG(D∗∗) is feasible. Definition 3.7, we have reg(Θ)⊆reg(Θ )∩reg(Θ ). 1 2 Definition 3.4 (Basic Region Decomposition[14]): Let Now, suppose reg(Θ )∩reg(Θ ) 6= reg(Θ). Then there is 1 2 D∗∗ be a region decomposition of G. D∗∗ is called a basic an R such that 0 region decomposition of G if the following conditions hold: R ∈reg(Θ )∩reg(Θ )\reg(Θ). (1) ForanyR∈D∗∗ andanye∈R\{lead(R)},In(e)⊆R; 0 1 2 (2) Eachnon-sourceregionRinD∗∗ hasatleasttwoparents By assumption of Θ, we have R ∈/ Θ ∪Θ . (Otherwise, 0 1 2 in RG(D∗∗). without loss of generality, assume R ∈ Θ . Then R ∈ 0 1 0 Accordingly, the region graph RG(D∗∗) is called a basic (reg(Θ ) ∩ Θ ) ⊆ Θ ⊆ reg(Θ), which contradict to the 2 1 region graph of G. assumption of R ∈/ reg(Θ).) So R ∈reg◦(Θ )∩reg◦(Θ ). 0 0 1 2 Forexample,onecancheckthatforthenetworkG in Fig. Then by Definition 3.7, we have 1 1 (a),the regiongraphRG(D) in Fig. 1 (b)a the basic region In(R )⊆reg(Θ )∩reg(Θ ). graph of G . 0 1 2 1 Thebasic regiondecompositionD∗∗ can bedecidedwithin Since R ∈/ reg(Θ), then by Definition 3.7, there exists an 0 time O(|E|) (See Algorithm 5 in [14]. Note that this Al- R ∈In(R ) such that R ∈/ reg(Θ). Then 1 0 1 gorithm can be generalized to networks with any k sources R ∈reg(Θ )∩reg(Θ )\reg(Θ). directely.). The following two theorems were also derived in 1 1 2 [14] (See Theorem 4.4 and 4.5 of [14] respectively.) and we Similarly, R has a parent R such that 1 2 omit their proof. Theorem 3.5: G has a unique basic region decomposition, R2 ∈reg(Θ1)∩reg(Θ2)\reg(Θ). hence has a unique basic region graph. By repeating this process, we can find a series of infinite Theorem 3.6: G is solvable if and only if RG(D∗∗) is regions R , R , R , ··· such that R is a parent of R feasible, where D∗∗ is the basic region decomposition of G. 0 1 2 i i−1 and C. Super Region R ∈reg(Θ )∩reg(Θ )\reg(Θ), i=1,2,··· . i 1 2 In this subsection, we always assume that D is a region This contradicts to the fact that RG(D) is a finite graph. So decomposition of G such that each non-source region has at reg(Θ )∩reg(Θ )=reg(Θ). least two parents in RG(D). 1 2 Definition 3.7 (Super Region [15]): Let D be a region de- IV. A SUFFICIENT AND NECESSARY CONDITION FORA compositionofGand∅6=Θ⊆D.Thesuperregiongenerated SUBCLASS OF3-SOURCESUM-NETWORKS by Θ, denoted by reg(Θ), is defined recursively as follows: Throughoutthissection,wealwaysassumethatGisa3s/nt (1) If R∈Θ, then R∈reg(Θ); sum-network and D∗∗ is the basic region decomposition of (2) If R∈D and In(R)⊆reg(Θ), then R∈reg(Θ). G. By Theorem 3.6, G is solvable if and only if RG(D∗∗) is We define reg◦(Θ) = reg(Θ) \ Θ. Moreover, if Θ = feasible. So we only need to consider coding on RG(D∗∗). {R1,··· ,Rk}, then we denote reg(Θ)=reg(R1,··· ,Rk). SinceGisa3s/ntsum-network,thenRG(D∗∗)hasexactly Since RG(D) is acyclic, then reg(Θ) is well defined. three source regions and at most n terminal regions. Without lossofgenerality,weassumeRG(D∗∗)hasexactlynterminal S1 S2 S3 regions. Let S (i ∈ {1,2,3}) denote the X source region i i and T ,j =1,··· ,n, denote the n terminal regions. For any j R1 R2 R3 i∈{1,2,3}, by Lemma 3.9, we have R4 R5 reg(Si,Sj1)∩reg(Si,Sj2)={Si} (1) where {j ,j }={1,2,3}\{i}.Thus T1 T2 T3 1 2 reg◦(S ,S )∩reg◦(S ,S )=∅. (2) i j1 i j2 Fig2. Anexampleofregiongraph. i.e., reg◦(S ,S ), reg◦(S ,S ) and reg◦(S ,S ) are mutually 1 2 1 3 2 3 ConsidertheregiongraphinFig.2.We havereg(S ,S )= disjoint. Denote {1,··· ,n}=[n] for any positive integer n. 1 2 {S ,S ,R ,R }. and reg(S ,R )={S ,S ,R }. Definition 4.1: We define some subsets of D∗∗ as follows: 1 2 1 4 2 3 2 3 3 Remark 3.8: From Definition 3.3 and 3.7, it is easy to see (1) Π,reg(S ,S )∪reg(S ,S )∪reg(S ,S ); 1 2 1 3 2 3 thatifC˜ ={dR ∈Fk;R∈D}isalinearcodeofRG(D)and (2) For any I ⊆ [n], ΩI is the set of all R ∈ D∗∗\Π such ∅6=Θ⊆D, then dR ∈hdR′;R′ ∈Θi for all R∈reg(Θ). that R→Tj,∀j ∈I, and R9Tj′,∀j′ ∈[n]\I; (3) Λ isthesetofallQ∈ΠsuchthatQhasachildR∈Ω . Lemma 4.5: If RG(D∗∗) is terminal-separable,then for all I I We also denote ΩI = Ωi1,···,ip and ΛI = Λi1,···,ip if the j ∈[n] and {i1,i2}⊆{1,2,3},we have Tj ∈Ωj ⊆reg◦(Λj) subset I ={i1,··· ,ip}. and Λj *reg(Si1,Si2). In particular, we have |Λj|≥2. Fromtheabovedefinition,thefollowingremarkisobvious. Proof: Since Tj → Tj and RG(D∗∗) is terminal- separable, then Tj 9Tj′,∀j′ ∈[n]\{j}. So Tj ∈Ωj. Remark 4.2: If I,I′ ⊆[n] and I 6=I′, then ΩI ∩ΩI′ =∅. We now prove Ωj ⊆ reg(Λj) by contradiction. For this Since RG(D∗∗) is acyclic, regions in D∗∗ can be sequen- purpose, suppose there is an R ∈ Ωj such that R ∈/ reg(Λj). tially indexed as D∗∗ = {R1,R2,R3,··· ,RN} such that ThenbyDefinition3.7,Rhasaparent,sayP1,suchthatP1 ∈/ Ri = Si,i = 1,2,3, RN−n+j = Tj,j = 1,2,··· ,n, and reg(Λj). Clearly, P1 ∈/ Π. (Otherwise, by the definition of ℓ < ℓ′ if Rℓ is a parent of Rℓ′. For all I ⊆ [n], we can Λj, P1 ∈Λj ⊆ reg(Λj), which contradicts to the assumption determine ΩI by a the following simple labelling algorithm. that P1 ∈/ reg(Λj).) Since RG(D∗∗) is terminal-separableand P1 → R → Tj, then P1 9 Tj′,∀j′ 6= j. So P1 ∈ Ωj. Similarly, P has a parent P such that P ∈/ reg(Λ ) and Algorithm 1: Labelling Algorithm (RG(D∗∗)): 1 2 2 j P ∈ Ω . By repeating this process, we can obtain a series 2 j j ← from 1 to n of infinite regions, P ,P ,··· such that P ∈/ reg(Λ ) and 1 2 i j Label RN−n+j with j; Pi ∈ Ωj, which contradicts to the fact that RG(D∗∗) is a ℓ← from N to 1; finite graph. So Ω ⊆reg(Λ ). j j if Rℓ has a child Rℓ′ such that Rℓ′ is labelled with j for Note that Ωj ⊆ D∗∗ \Π and Λj ⊆ Π. So Ωj ∩Λj = ∅. some j ∈[n] then Thus, we have T ∈Ω ⊆reg◦(Λ ). j j j Label Rℓ with j; Moreover,if Λj ⊆reg(Si1,Si2), then byDefinition 3.7, we have T ∈ Ω ⊆ reg◦(Λ ) ⊆ reg(S ,S ), which contradicts j j j i1 i2 Note that for each R ∈ D∗∗ and j ∈ [n], if R has a to Assumption 1. So Λj *reg(Si1,Si2). Finally, if |Λ | = 1, say Λ = {Q}, then by the definition child R′ such that R′ → T , then R → T . So R → T j j j j j of Π and Λ , we have Q∈reg(S ,S ) for some {i ,i }⊆ if and only if R is labelled with j by Algorithm 1. Let j i1 i2 1 2 {1,2,3}. Thus, Λ ={Q}⊆reg(S ,S ), which contradicts I = {j ∈ [n];R is labelled with j}. Then for each I ⊆ [n], j i1 i2 RR∈Ω if and only if I =I. Thus, by Algorithm 1, we can to the proved result that Λj *reg(Si1,Si2). So |Λj|≥2. I R Lemma 4.6: SupposeRG(D∗∗)isterminal-separable.Then easily determine Ω for all I ⊆ [n]. Clearly, the run time of I RG(D∗∗) is feasible if and only if there is a collection of Algorithm 1 is O(|D∗∗|). Consider the region graph in Fig. 2. We have Ω = {T } vectors C˜Π = {dR;R ∈ Π} ⊆ F3 satisfying the following i i three conditions: fori∈{1,2,3},Ω ={R } andΩ =Ω =Ω =∅. 2,3 5 1,2 1,3 1,2,3 Thus, we have Λ1 = {R1,R3}, Λ2 = {R4}, Λ3 = {R3}, (1) dSi =αi,i=1,2,3; Λ2,3 ={R2,R3} and Λ1,2 =Λ1,3 =Λ1,2,3 =∅. (2) dR ∈hdR′;R′ ∈In(R)i,∀R∈Π\{S1,S2,S3}; IfC˜ ={dR ∈Fk;R∈D}isalinearsolutionofRG(D∗∗), (3) α¯ ∈hdR;R∈Λji,∀j ∈[n]. {i,j} ⊆ {1,2,3} and R ∈ reg(S ,S ), then by Remark 3.8, Proof: Suppose RG(D∗∗) is feasible and C˜ ={d ;R∈ i j R α¯ 6=d ∈hα ,α i.SoT ∈/ reg(S ,S )forallterminalregion D∗∗} is a linear solution of RG(D∗∗). By Lemma 4.5, R i j ℓ i j Tℓ, which implies that Tℓ ∈D∗∗\Π,∀ℓ∈[n]. For this reason, Tj ∈ Ωj ⊆ reg◦(Λj) and Λj * reg(Si1,Si2), ∀j ∈ [n] and in this section, we assume: {i ,i }⊆{1,2,3}.ByRemark3.8,α¯ =d ∈hd ;R∈Λ i. 1 2 Tj R j Assumption 1: T ∈/ Π for all j ∈[n]. Let C˜ ={d ;R∈Π}. Then C˜ satisfies conditions(1)-(3). j Π R Π Definition 4.3: The region graph RG(D∗∗) is said to be Conversely, suppose there is a collection C˜ = {d ;R ∈ Π R terminal-separableif ΩI =∅ forall I ⊆[n] such that|I|>1. Π} ⊆ F3 satisfying conditions (1)-(3). We can construct a For example, the region graph in Fig. 3 is terminal- linear solution of RG(D∗∗) as follows: separable. However, the region graph in Fig. 2 is not because Since RG(D∗∗) is terminal-separable, for each j ∈[n] and Ω2,3 ={R5}6=∅. Q ∈ Λj, by the Definition of Λj and Ωj, we can find a path We shall give a necessary and sufficient condition of feasi- {R ,··· ,R } ⊆ Ω such that R = T and Q is a parent of 1 ℓ j ℓ j bility for terminal-separableregion graph, by which it is easy R . Let Γ be the union of all such paths. Then Γ ⊆ Ω . 1 j j j tocheckwhetheraterminal-separableregiongraphisfeasible. Sinceα¯ ∈hd ;R∈Λ i, thenwe canconstructa codeC˜ = R j Γj Remark 4.4: Terminal-separable region graphs is of inter- {dR;R∈Γj} such that dTj =α¯ and dR ∈hdR′;R′ ∈In(R)i esting because, if a region graph RG(D) is not terminal- forallR∈Γ .ByRemark4.2,Ω ,j =1,··· ,n,aremutually j j separable, then we can view it as a region graph with fewer disjoint. So Γ ,j = 1,··· ,n, are mutually disjoint and C˜ = j terminal regions. For example, for the region graph in Fig. C˜ ∪C˜ ∪···∪C˜ is a linear solution of RG(D∗∗). Thus, Π Γ1 Γn 2, we can view T and R as two terminal regions and RG(D∗∗) is feasible. 1 5 construct a linear solution of RG(D). Then the sum of sources can be transmitted from R to T and T . In fact, A. Partitioning of Π 5 2 3 letdR1 =dR2 =α1,dR3 =α2+α3 anddR5 =α1+α2+α3. TogiveasimplecharacterizationoffeasibilityofRG(D∗∗), Then {dR;R∈D} is a linear solution of RG(D). we need to make some discussion on partitioning Π. Let I = {∆ ,··· ,∆ } be a partition of Π. For the sake Definition 4.10: Let I = {[S ],[S ],[S ],··· ,[R ]} be a 1 K 1 2 3 K of convenience, we shall call each ∆ an equivalent class of partitionof Π. I is said to be compatibleif the followingtwo i I. If R ∈ ∆ , we denote ∆ = [R]. Thus, for each ∆ , we conditions hold: i i i can choose an Ri ∈∆i and denote I ={[R1],··· ,[RK]}. (1) No pair of equivalent classes of I are connected; Let I = {[S1],[S2],[S3],··· ,[RK]} be an arbitrary parti- (2) Λj * [Si1]i1 ∪[Si2]i2 ∪(∪Kℓ=4[Rℓ]i1,i2) for all j ∈ [n] tion of Π.1 For each equivalentclass [R]∈I and each subset and {i ,i }⊆{1,2,3}. 1 2 {i,j}⊆{1,2,3}, we denote Clearly,in Example4.8, the partitionI of Πis compatible. Suppose I is a partition of Π and {[R′],[R′′]} ⊆ I. By [R] =[R]∩reg(S ,S ). (3) i,j i j combining[R′]and[R′′] intooneequivalentclass[R′]∪[R′′], For each i∈{1,2,3}, we denote we obtain a partition I′ =I∪{[R′]∪[R′′]}\{[R′],[R′′]} of Π. We callI′ a contractionofI bycombining[R′] and[R′′]. [S ] =[S ] ∪[S ] (4) i i i i,j1 i i,j2 B. Main Result where {j ,j } = {1,2,3}\{i}. Then we can divide each 1 2 equivalent class as follows: Let I = {[R];R ∈ Π}, where [R] = {R},∀R ∈ Π. Then 0 Definition 4.7: For i ∈ {1,2,3}, [Si] is divided into two I0 is a partition of Π. We call I0 the trivial partition of Π. subclasses [Si]i and [Si]j1,j2, where {j1,j2}={1,2,3}\{i}; Definition 4.11: Let I0,I1,··· ,IL = Ic be a sequence For i ∈ {4,··· ,K}, [Ri] is divided into three subclasses of partitions of Π such that Iℓ is a contraction of Iℓ−1 by [Ri]1,2,[Ri]1,3 and [Ri]2,3. combining two connected equivalent classes in Iℓ−1 and, for any {i,j} ⊆ {1,2,3}, [S ] 6= [S ] in I , where i j ℓ−1 S1 S2 S3 ℓ=1,··· ,L. Ic is called a character partition of Π if one of the following conditions hold: R2 R3 (1) [Si]=[Sj] for some {i,j}⊆{1,2,3}; R4 R1 R7 R5 R6 (2E)xNamoppleair4.o1f2:eqCuoivnasliednetrcltahseserseginioIncgarraepchoninneFctiegd..4 (a). We have Π = {S ,S ,S ,R ,R ,R ,R } and Λ = 1 2 3 1 2 3 4 2 T1 T2 T3 T4 T5 {S2,R1}⊆([S2]2∪[R1]1,3).By(1)ofDefinition4.9,[S2]and [R ] are connected. So I = {{S },{S ,R },{S },{R }, 1 1 1 2 1 3 2 Fig 3. An example of terminal-separable region graph: By Definition {R },{R }} is obtained from I by combining [S ] and 3.7, we can check that reg(S1,S2) = {S1,S2,R1,R4}, reg(S1,S3) = 3 4 0 2 [R ], where I is the trivial partition of Π. Similarly, let {S1,S3,R2,R7}andreg(S2,S3)={S2,S3,R3,R5,R6}. ByDefinition 1 0 4.1,wehaveΩj ={Tj},j=1,···,6andΩI =∅,∀I ⊆{1,···,6}such I2 = {{S1},{S2,R1,R2},{S3},{R3},{R4}} and I3 = that|I|≥2.Sothis regiongraphisterminal-separable. {{S },{S ,R ,R ,R },{S },{R }}. Then I ,j = 2,3, is 1 2 1 2 3 3 4 j obtained from I by combining two connected equivalent For any equivalent class [R] ∈I, we use [[R]] to denote a j−1 classes. Note that in I , reg([S ] ) = reg(R ,R ) = subclassof[R].Notethatasubclass[[R]]of[R]ispossiblyan 3 2 2,3 2 3 {R ,R ,R } and reg([R ] ) = reg(R ) = {R }. So emptyset.ByEquations(1)−(4),eachequivalentclassisadis- 2 3 4 4 2,3 4 4 by (2) of Definition 4.9, [S ] and [R ] are connected and jointunionofitsallsubclasses.Thus,{[S ] ,[S ] }∪{[S ] , 2 4 1 1 1 2,3 2 2 I = {{S }, {S ,R ,R ,R ,R },{S }} is obtained from [S ] }∪{[S ] ,[S ] }∪(∪K {[R ] ,[R ] ,[R ] }) is 4 1 2 1 2 3 4 3 2 1,3 3 3 3 1,2 i=4 i 1,2 i 1,3 i 2,3 I by combining two connected equivalent classes. In I , still a partition of Π. 3 4 again by (1) of Definition 4.9, [S ] and [S ] are connected Example 4.8: Consider the region graph in Fig. 3. By 2 1 and I ={{S ,S ,R ,R ,R , R }, {S }} is obtained from Definition3.7, reg(S ,S )={S ,S ,R ,R }, reg(S ,S )= 5 1 2 1 2 3 4 3 1 2 1 2 1 4 1 3 I by combining two connected equivalent classes. Thus, {S ,S ,R ,R }andreg(S ,S )={S ,S ,R ,R ,R }.Let 4 1 3 2 7 2 3 2 3 3 5 6 I ,I ,··· ,I satisfy the conditions of Definition 4.11. So [S ] = {S ,R ,R ,R ,R ,R }, [S ] = {S }, [S ] = {S }, 0 1 5 1 1 1 3 4 5 7 2 2 3 3 I =I is a character partition of Π. Since [S ]=[S ], then [R ] = {R ,R } and I = {[S ],[S ],[S ],[R ]}. Then I c 5 1 2 2 2 6 1 2 3 2 I is not compatible. is a partition of Π and [S ] = {S ,R ,R ,R }, [S ] = c 1 1 1 1 4 7 1 2,3 Similarly, for the region graph in Fig. 4 (b), we can find {R ,R }, [S ] = {S }, [S ] = ∅, [S ] = {S }, 3 5 2 2 2 2 1,3 3 3 3 that I = {{S ,P ,P ,P ,P },{S },{S }} is a character [S ] = ∅, [R ] = ∅, [R ] = {R }, [R ] = {[R ]} c 1 1 2 3 4 2 3 3 1,2 2 1,2 2 1,3 2 2 2,3 6 partition of Π. Since Λ ⊆[S ] , then I is not compatible. are all subclasses of I and they also form a partition of Π. 2 1 1 c Lemma 4.13: LetI be a partition of Π. If I is compatible, Definition 4.9: Let I = {[S ],[S ],[S ],··· ,[R ]} be a 1 2 3 K then RG(D∗∗) is feasible. partition of Π. Two equivalent classes [R′] and [R′′] are said Proof: The proof is given in Appendix A. to be connected if one of the following conditions hold: (1) There is a j ∈ [n] such that Λ ⊆ [[R′]]∪[[R′′]], where Lemma 4.14: Suppose C˜Π = {dR;R ∈ Π} ⊆ F3 satisfies j theconditionsofLemma4.6andI isa characterpartitionof [[R′]] (resp. [[R′′]]) is a subclass of [R′] (resp. [R′′]); c Π. For any [R] ∈ I and {i ,i } ⊆ {1,2,3}, if Q ∈ [R] (2) There is an {i ,i }⊆{1,2,3} such that reg([R′] )∩ c 1 2 i1,i2 reg([R′′] )6=1 ∅2. i1,i2 and dQ 6=0, then dQ′ ∈hdQi,∀Q′ ∈[R]i1,i2. i1,i2 Proof: The proof is given in Appendix B. Theorem 4.15: Let RG(D∗∗) be terminal-separable and I 1WhenweusethenotationI={[S1],[S2],[S3],···,[RK]},wealways c assumethat[S1],[S2],[S3],···,[RK]aremutuallydifferent. beacharacterpartitionofΠ.ThenRG(D∗∗)isfeasibleifand S1 S2 S3 S1 S2 S3 are two S-connectedequivalentclasses, whichcan be donein time O(|S|) = O(n) by Definition 4.9. Thus, it is {|Π|,n}- R1 R2 R3 P2 P4 P1 polynomial time complexity to determine whether RG(D∗∗) is feasible. R4 P3 Consider the region graph in Fig. 3. We can check that the partitionI inExample4.8isacharacterpartitionofΠ.SinceI T1 T2 T3 T4 T1 T2 T3 is compatible,so the regiongraphisfeasible. LetF=GF(p) for a sufficiently large prime p. Let d = d =d = α , (a) (b) R1 R4 R7 1 d = 2α +3α , d = d = α +α , d = α +3α . R2 1 3 R3 R5 2 3 R6 1 2 Fig4. Examplesofregiongraph. Then {d ;R∈Π} is a linear solution of the graph. R Similar to the information flow decomposition technique only if I is compatible. Moreover, it is {|Π|,n}-polynomial c usedin[13],wecanreduceanycompatiblepartitionofΠinto time complexity to determine feasibility of RG(D∗∗). a minimal compatible partition I , i.e., I is a compatible m m Proof: If I is compatible, then by Lemma 4.13, c partition of Π but any contraction of I is not compatible. RG(D∗∗)isfeasible.Conversely,supposeRG(D∗∗)isfeasible m Thenwe canconstructan optimallinearsolutionofRG(D∗∗) and C˜Π = {dR;R ∈ Π} ⊆ F3 satisfies the conditions of on I using the method in the proof of Lemma 4.13. m Lemma 4.6. We shall prove that I is compatible. c ForthetworegiongraphsinFig.4,wehaveseenthatthere For any {i ,i } ⊆ {1,2,3}, if [S ] = [S ], then 1 2 i1 i2 is a character partition of Π that is not compatible. So by S ∈ [S ] . By Definition 3.3 and Lemma 4.14, i1 i2 i1,i2 Theorem 4.15, these two region graphs are not feasible. d = α ∈ hd i = hα i, a contradiction. So Si1 i1 Si2 i2 In[6],anecessaryandsufficientconditionforsolvabilityof [S ] 6= [S ]. Thus, by proper naming, we can assume i1 i2 a 3s/3t sum-network was given based on a set of connection I = {[S ],[S ],[S ],[R ],··· ,[R ]}. Moreover, by Defini- c 1 2 3 4 K conditions. By our method, we can give another sufficient tion 4.11, no pair of equivalent classes of I are connected. c andnecessaryconditionforsolvabilityof3s/3tsum-networks For any j ∈ [n] and {i ,i } ⊆ {1,2,3}, suppose Λ ⊆ 1 2 j which is different from [6]: [S ] ∪[S ] ∪(∪K [R ] ). Then by Lemma 4.14 and i1 i1 i2 i2 ℓ=4 ℓ i1,i2 Theorem 4.16: Suppose RG(D∗∗) has three terminal re- Equation (4), we have gions.ThenRG(D∗∗)isnotfeasibleifandonlyifitisterminal d ∈hd i=hα i,∀Q∈[S ] (5) separable and the following condition (C-IR) hold: Q Si1 i1 i1 i1 (C-IR) By proper naming, there is a P ∈reg◦(S ,S ) and a and 1 2 3 P ∈ reg◦(S ,S ) such that Λ = {S ,P }, Λ = {P ,P } 2 1 2 1 1 1 2 1 2 d ∈hd i=hα i,∀Q∈[S ] . (6) and Λ ⊆reg(S ,P )∪reg(S ,S ). Q Si2 i2 i1 i2 3 1 2 1 3 Proof: The proof is given in Appendix C. Note that C˜ satisfies condition (2) of Lemma 4.6. By Equa- Π Fig. 4 (b) is an illustration of infeasible region graph of tion (5), (6) and Definition 3.7, we can easily see that d ∈ R 3s/3t sum-network. hα ,α i for all R∈[S ] ∪[S ] ∪(∪K [R ] ). Then i1 i2 i1 i1 i2 i2 ℓ=4 ℓ i1,i2 dR ∈hαi1,αi2i for all R∈Λj and α¯ ∈/ hdR;R∈Λji, which V. CONCLUSIONS AND DISCUSSIONS contradicts to the assumption that C˜ satisfies condition (3) Π We investigated the network coding problem of a special of Lemma4.6. Thus,Λj *[Si1]i1∪[Si2]i2∪(∪Kλ=4[Rλ]i1,i2). subclass of 3s/nt sum-networks termed as terminal-separable By Definition 4.10, I is compatible. c networks using a network region decomposition method. We By Definition 4.11, the following algorithm output a char- give a necessary and sufficient condition for solvability of acter partition of Π. terminal separable networks as well as a simple charac- terization of solvability of 3s/3t sum-networks. The region Algorithm 2: Partitioning algorithm (Π,S): decomposition method is shown to be an efficient tool for L=0; analyzing the structure of a network and helps to investigate Whilethere are R′,R′′ ∈IL which are S−connected do the networkcodingproblemof a communicationnetwork.By Let IL+1 be a contraction of IL by combining R′ and R′′; moreintensiveanalysis,wecanalsogiveacharacterizationof If [Si]=[Sj] for some {i,j}⊆{1,2,3} then solvability of 3s/4t sum-networks, which is our future work. Ic =IL; return Ic; REFERENCES stop; [1] R.Ahlswede,N.Cai,S.-Y.R.Li,andR.W.Yeung,“Networkinformation else flow,”IEEETrans.Inf.Theory,vol.46,no.4,pp.1204-1216,Jul.2000. L=L+1; [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. Ic =IL; [3] A.Ramamoorthy, “Communicating thesumofsources overanetwork,” return Ic; inProcISIT,Toronto,Canada, July06-11,pp.1646-1650,2008. [4] B.K.Rai,B.K.Dey,andA.Karandikar,“Someresultsoncommunicating thesumofsourcesoveranetwork,” inProcNetCod 2009. Clearly, there are at most |Π| roundsin Algorithm2 before [5] M.LangbergandA.Ramamoorthy,“Communicatingthesumofsources output Ic. In each round, we need to determine wether there ina3-sources/3-terminals network,” inProcISIT,Seoul,Korea,2009. [6] S. Shenvi and B. K. Dey, “A necessary and sufficient condition for Since F is sufficiently large, then there exists a β(K) ∈ F3 solvability ofa3s/3tsumnetwork,”inProcISIT,Texas,U.S.A,2010. such that [7] B.K.RaiandB.K.Dey,“OnNetworkCodingforSum-Networks,”IEEE Trans.Inf.Theory,vol.58,no.1,pp.50-63,Jan.2012. β(K) ∈/ hα¯,γi,∀γ ∈Ψ . (7) K−1 [8] B.K.RaiandN.Das,“Sum-Networks:Min-Cut=2DoesNotGuarantee Solvability,” IEEE Communications Letters, vol. 17, no. 11, pp. 2144- For each {i ,i }⊆{1,2,3}, let 1 2 2147,Nov.2013. [9] A.GiridharandP.R.Kumar,“Computingandcommunicatingfunctions 06=β(K) ∈hβ(K),α¯i∩hα ,α i (8) over sensor networks,” IEEE J. Select. Areas Commun., vol. 23, no. 4, i1,i2 i1 i2 [10]ppY..7K5a5n-7o6ri4a,a2n0d05D. . Manjunath, “On distributed computation in noisy where 0 is the zero vector of F3. Let BK = {β1(K,2), randomplanarnetworks,” inProc.ISIT,Nice,France, 2008. β(K),β(K)}. We shall prove that the collection {B , ···, 1,3 2,3 1 [11] R. Appuswamy, M. Franceschetti, N. Karamchandani, and K. Zeger, B , B } satisfies conditions (1)−(4). Networkcodingforcomputing:cut-setbounds,IEEETrans.Inf.Theory, K−1 K vol.57,no.2,pp.1015-1030, Feb.2011. By Equation (8), we have βi(1K,i)2 ∈ hαi1,αi2i,∀{i1,i2} ⊆ [12] S. Kannan and P. Viswanath, Multi-session function computation and {1,2,3}. So {B , ···, B , B } satisfies condition (1). 1 K−1 K multicasting in undirected graphs, IEEE J. Select. Areas Commun., vol. By assumption, {B , ···, B } satisfies condition (2), 31,no.4,pp.702-713,2013. 1 K−1 then for any ℓ ∈ {1,··· ,K −1} and {γ,γ′} ⊆ B , the pair [13] C. Fragouli and E. Soljanin,“Information flow decomposition for net- ℓ workcoding,”IEEETrans.Inf.Theory,vol.52,no.3,pp.829-848,Mar. {γ,γ′}isinΦ .Moreover,since{B ,···,B }satisfies K−1 1 K−1 2006. condition (1), then {γ,γ′} ⊆ B ⊆ hα ,α i ∪ hα ,α i ∪ [14] W. Song, K. Cai, R. Feng and C. Yuen, “The Complexity ofNetwork ℓ 1 2 1 3 hα ,α i. So {γ,γ′} ⊆ {hγ,γ′i , hγ,γ′i , hγ,γ′i }. CodingWithTwoUnit-RateMulticastSessions,”IEEETrans.Inf.Theory, 2 3 1,2 1,3 2,3 vol.59,no.9,pp.5692-5707, Sept.2013. Thus, we have ∪Kℓ=−11Bℓ ⊆ ΨK−1. By Equation (7), for any [15] W.Song,R.Feng,K.CaiandJ.Zhang,“NetworkCodingfor2-unicast γ ∈∪K−1B , withRate(1,2)”inProc.ISIT,Boston,2012. ℓ=1 ℓ γ ∈/ hβ(K),α¯i. (9) APPENDIX A In particular, we have α ∈/ hβ(K),α¯i,j = 1,2,3. So by j PROOF OF LEMMA4.13 Equation (8), β(K), β(K) and β(K) are mutually linearly 1,2 1,3 2,3 independent and α¯ ∈hγ,γ′i,∀{γ,γ′}⊆B . Thus, {B , ···, Here, we prove Lemma 4.13. First, we prove two lemmas. K 1 B , B } satisfies condition (2). Lemma A.1: LetB ={α ,α +α },B ={α ,α +α }, K−1 K 1 1 2 3 2 2 1 3 Now,weprovethat∪K B satisfiescondition(3).Suppose B = {α ,α + α } and K ≥ 3 is an integer. If F ℓ=1 ℓ is3sufficien3tly 1large, 2then there are K − 3 subsets B = {γ,γ′,γ′′} ⊆ ∪Kℓ=1Bℓ such that {γ,γ′,γ′′} * hαi1,αi2i for {β1(4,2),β1(4,3),β2(4,3)}, ···, BK = {β1(K,2),β1(K,3),β2(K,3)} ⊆ F3 4such faonrya{niy1,ℓi2∈}{⊆1,{··1·,2,K,3}}.aWnde h{aγv,eγ′t,hγe′′f}ol=6low{iβn1(gℓ,2)t,hβre1(eℓ,3)c,aβse2(ℓ,s3):} that {B ,B ,B ,··· ,B } satisfies the following conditions: 1 2 3 K Case 1: {γ,γ′,γ′′} ⊆ ∪K−1B . By the induction assump- (1) Foranyℓ∈{4,··· ,K}and{i1,i2}⊆{1,2,3},βi(1ℓ,)i2 ∈ tion, γ,γ′ and γ′′ are lineaℓr=ly1indℓependent. hαi1,αi2i; Case 2: {γ,γ′} ⊆ ∪Kℓ=−11Bℓ and γ′′ ∈ BK. We have the (2) For any ℓ∈{1,··· ,K} and {γ,γ′}⊆Bℓ, α¯ ∈hγ,γ′i; following two subcases: (3) If {γ,γ′,γ′′} ⊆ ∪Kℓ=1Bℓ such that {γ,γ′,γ′′} * Case 2.1: {γ,γ′} ⊆ hαℓ1,αℓ2i for some {ℓ1,ℓ2} ⊆ hαi1,αi2i,∀{i1,i2} ⊆ {1,2,3}, and {γ,γ′,γ′′} 6= {1,2,3}. By assumption of {γ,γ′,γ′′}, we have γ′′ ∈/ {β(ℓ),β(ℓ),β(ℓ)},∀ℓ ∈ {4,··· ,K}, then γ,γ′ and γ′′ hα ,α i. So γ,γ′ and γ′′ are linearly independent. 1,2 1,3 2,3 ℓ1 ℓ2 are linearly independent; Case 2.2: {γ,γ′} * hαℓ1,αℓ2i,∀{ℓ1,ℓ2} ⊆ {1,2,3}. Then (4) For any pair {γ,γ′} ⊆ ∪Kℓ=1Bℓ, γ and γ′ are linearly the pair {γ,γ′} is in the set ΦK−1. So we have γ′′ ∈/ independent. hγ,γ′i. (Otherwise, γ′′ ∈ {hγ,γ′i ,hγ,γ′i ,hγ,γ′i } ⊆ 1,2 1,3 2,3 Ψ andbyEquation(8),β(K) ∈hα¯,γ′′i,whichcontradicts Proof: We can prove this lemma by induction. K−1 to Equation(7).) Thus, γ,γ′ and γ′′ are linearly independent. Clearly, when K = 3, the collection {B ,B ,B } satisfies 1 2 3 Case 3: γ ∈ ∪K−1B and {γ′,γ′′} ⊆ B . By Equations conditions (1)−(4). ℓ=1 ℓ K (8) and (9), γ ∈/ hβ(K),α¯i = hγ′,γ′′i. So γ,γ′ and γ′′ are Now suppose K > 3 and there is a collection {B , 1 linearly independent. ···, B } which satisfies conditions (1)−(4). We want to K−1 Thus, {B ,··· ,B ,B } satisfies conditions (3). construct a subset BK = {β1(K,2),β1(K,3),β2(K,3)} ⊆ F3 such Clearly, i1f {B ,·K··−,1B K ,B } satisfies conditions (3), that the collection {B ,··· ,B ,B } satisfies conditions 1 K−1 K 1 K−1 K then for any {γ,γ′} ⊆ ∪K B , we can find a γ′′ ∈ ∪K B (1)−(4). The subset B can be constructed as follows: ℓ=1 ℓ ℓ=1 ℓ K such that γ,γ′ and γ′′ are linearly independent. So γ and thaLte{tγΦ,γK′−}1*bheαtih1e,αsie2ti,o∀f{ail1l,ip2a}ir⊆s {{γ1,,γ2′,}3}⊆. T∪hKℓe=−n11hBγℓ,γs′uic∩h γco′nadreitiloinnesa(r4ly).independentand{B1,··· ,BK−1,BK}satisfies hαi1,αi2i is an 1-dimensionalsubspace of F3. Let hγ,γ′ii1,i2 Byinduction,forallK ≥3,wecanalwaysfindacollection be a fixed non-zero vector in hγ,γ′i∩hα ,α i. Let i1 i2 {B1, ···, BK−1, BK} which satisfies conditions (1)−(4). WegiveanexampleofLemmaA.1inthebelow.Tosimplify ΨK−1 = [ {hγ,γ′i1,2,hγ,γ′i1,3,hγ,γ′i2,3}. our discussion, we assume that F = GF(p), where p is a {γ,γ′}∈ΦK−1 sufficiently large prime. Example A.2: According to Lemma A.1, B = {α ,α + By the construction of C˜ , we have d = α ,j = 1 1 2 Π Sj j α },B = {α ,α +α },B = {α ,α +α }. Then Φ = 1,2,3. Moreover, since I is compatible, then for each 3 2 2 1 3 3 3 1 2 3 {{α ,α +α },{α ,α +α },{α ,α +α },{α +α ,α + [R ] ∈ I and {i ,i } ⊆ {1,2,3}, we have [R ] = 1 2 3 2 1 3 3 1 2 2 3 1 ℓ 1 2 ℓ i1,i2 α },{α + α ,α + α },{α + α ,α + α }} and Ψ = reg([R ] ). (Otherwise, by Definition 3.7, there is an 3 2 3 1 2 1 3 1 2 3 ℓ i1,i2 {α ,α +α }∪{α ,α +α }∪{α ,α +α }∪{α +α ,α + R ∈ reg([R ] )\[R ] . By condition (2) of Definition 1 2 3 2 1 3 3 1 2 2 3 1 ℓ i1,i2 ℓ i1,i2 α ,α −α }∪{α +α ,α +α ,α −α }∪{α +α ,α + 4.9, [R ] and [R] are connected, which contradicts to the 3 1 2 2 3 1 2 1 3 1 3 1 ℓ α ,α −α }.We cancheckthatα +3α ∈/ hα¯,γi,∀γ ∈Ψ . assumptionthatI iscompatible.)Now,let∆ =[R ] ,i= 2 2 3 1 2 3 i i i1,i2 Let β(4) =α +3α and B ={α +3α ,2α +3α ,2α − 1,··· ,K, where [R ]=[S ],i =1,2,3. By the construction, 1 2 4 1 2 1 3 2 i i α }. Then the collection {B ,B ,B ,B } satisfies conditions C˜ = {d ;R ∈ reg(S ,S )} satisfies the conditions of 3 1 2 3 4 i1,i2 R i1 i2 (1)−(4) of Lemma A.1. LemmaA.3.SodR ∈hdR′;R′ ∈In(R)i,∀R∈reg◦(Si1,Si2). Similarly,wecanconstructasubsetB ={2α +3α ,α + Finally, we provethat C˜ satisfies condition (3) of Lemma 5 1 2 1 Π 3α ,α −2α } such that the collection {B ,B ,B ,B ,B } 4.6. For each Λ ,j ∈[n], we have the following two cases: 3 2 3 1 2 3 4 5 j satisfies conditions (1)−(4) of Lemma A.1. Case 1: There is an [R ] ∈ I such that Λ intersects with ℓ j Lemma A.3: Let {i ,i } ⊆ {1,2,3} and {∆ ,··· ,∆ } at least two subclasses of [R ]. Suppose Q ∈ Λ ∩[[R ]] 1 2 1 K ℓ 1 j ℓ 1 be a partition of reg(S ,S ) such that reg(∆ ) = ∆ ,i = and Q ∈ Λ ∩ [[R ]] , where [[R ]] and [[R ]] are two i1 i2 i i 2 j ℓ 2 ℓ 1 ℓ 2 1,··· ,K. Let C˜ = {d ;R ∈ reg(S ,S )} ⊆ hα ,α i different subclasses of [R ]. Then by the construction of C˜ , i1,i2 R i1 i2 i1 i2 ℓ Π be such that: {d ,d }⊆B and α¯ ∈hd ,d i. Q1 Q2 ℓ Q1 Q2 (1) If {R,R′}⊆∆i for some i∈[K], then dR =dR′; Case 2: For each [Rℓ] ∈ I, Θj intersects with at (2) If {R,R′} * ∆i for any i ∈ [K], then dR and dR′ are most one subclass of [Rℓ]. Since I is compatible, then we linearly independent. can always find a subset {Q1,Q2,Q3} ⊆ Λj such that 3T.h7e,nIPndr(RoRo)∈f:⊆hSdurRep′gp;(oRSsi′e1∈,RSIin2∈()R.rWe)ig,e◦(∀hSRaiv1e,∈Sthri2ee)g.◦fo(TSllhoie1wn,iSnbigy2)t.Dweoficnaitsieosn: a{onQfd1C˜,{ΠQd,Q2{,1Qd,Qd3Q1},2d,isQdQ2a,n3d}QI6=3−}in{*dβe1(pℓ,h2)eα,niβd11(,eℓ,αn3),ti2βsi2(e,ℓ,t3∀).}{B,i∀1y,ℓit2h∈}e {c⊆4o,n{·s·1tr·,u2,cK,ti3o}}n., Case 1: In(R) ⊆ ∆i for some i ∈ {1,··· ,K}. Then by So dQ1,dQ2 and dQ3 are linearly independent. Thus, α¯ ∈ Definition 3.7, R∈reg(∆i). Since by the assumption of this hdQ1,dQ2,dQ3i=F3. lemma, reg(∆i) = ∆i, then R ∈ ∆i and, by condition (1), By the above discussion, C˜Π satisfies the conditions of dR =dR′ for all R′ ∈In(R). Thus, dR ∈hdR′;R′ ∈In(R)i. Lemma 4.6. So RG(D∗∗) is feasible. Case 2:In(R)*∆i foranyi∈{1,··· ,K}.By Definition Here, we make an example to illustrate the construction of 3.4, each non-source region has at least two parents. Since C˜Π in the proof of Lemma 4.13. {∆ ,··· ,∆ }isapartitionofreg(S ,S ),thenthereexists 1 K i1 i2 APPENDIX B a subset {i ,i } ⊆ {1,··· ,K} such that In(R)∩∆ 6= ∅ 1 2 i1 PROOF OFLEMMA 4.14 and In(R) ∩ ∆ 6= ∅. Assume R′ ∈ In(R) ∩ ∆ and i2 1 i1 Here, we prove Lemma 4.14. Rlin2′ea∈rlyIn(iRnd)e∩pe∆ndie2n.tTahnedn bdyRc∈ondhditRio′1n,d(R2)′2,id=R′1 haαn1d,αdR2i′2. aSroe satSisufipepsotsheeC˜coΠnd=itio{ndsRo;fRL∈emΠm}a 4⊆.6.FN3oitse athactolRleGct(iDon∗∗t)haist dR ∈hdR′;R′ ∈In(R)i. acyclic and d = α 6= 0,i = 1,2,3. If there is an R ∈ Π Definition A.4: Let I = {[S ],[S ],[S ],··· ,[R ]} be a Si i 1 2 3 K such that d = 0, then we can always find an R ∈ Π such partition of Π. A subset {Q,Q′,Q′′} ⊆ Π is called an I- R 0 independent set if the following three conditions hold: that dR0 = 0 and dR′ 6= 0,∀R′ ∈ In(R0). We redefine dR0 (1) |{Q,Q′,Q′′}∩[[R]]|≤1foranyequivalentclass[R]∈I rbeysullettetdincgoddeR0C˜==d{Rd′ f;oRr ∈a Πfix}edstiRll′sa∈tisfiIne(sRth0e).cTonhdenitiothnes Π R and any subclass [[R]] of [R]; of Lemma 4.6 and d 6= 0. We can perform this operation (2) {Q,Q′,Q′′}*[R] for any equivalent class R∈I; R0 continuouslyuntild 6=0forallR∈Πandtheresultedcode (3) {Q,Q′,Q′′}*[Si]i∪[Sj]j ∪(∪Kℓ=4[Rℓ]i,j) for any pair C˜ ={d ;R∈Π}RstillsatisfiestheconditionsofLemma4.6. Π R {i,j}⊆{1,2,3}. So we canassume, withoutloss ofgenerality,that d 6=0 for R Now we can prove Lemma 4.13 all R∈Π. Proof of Lemma 4.13: Since I is compatible, by Defi- ToproveLemma4.14,thekeyistoprovethatallequivalent nition 4.10, we can assume I = {[S1],[S2],[S3],··· ,[RK]}. class [R]∈Ic satisfies the following property: Let B , ···, B be as in Lemma A.1. We construct a code C˜Π =1{dR;R∈KΠ}⊆F3 as follows: T•oPprroopveerttyhi(sa,):wFeofirrasntypproavire{tQhe,Qfo′l}lo⊆wi[nRg],twdQo′l∈emhmdQas,.α¯i. • For j ∈{1,2,3} and R∈[Sj]j, let dR =αj; Lemma B.1: LetI bea partitionofΠand[R]∈I satisfies • For j ∈ {1,2,3} and R ∈ [Sj]i1,i2, let dR = αi1 +αi2, Property (a). Then for any {i1,i2} ⊆ {1,2,3} and any pair • [wFRohjre]rij1e,i{2∈i,1l,e{it24}d,R·=··={,1Kβ,i(21}j,,),i32{.}i\1{,ji}2}; ⊆ {1,2,3} and R ∈ [{[QR,]]QPo′rf}o[o⊆Rf:][aRSni]ndi1c,aein2,yC˜dpΠQa′irs∈a{tQihsdfi,QQesi′.}cM⊆ono[dr[eRitoi]vo],enrsd,Qf(o′1r∈)ahnadnyQdsiu.(b2c)laossf We shall prove that C˜Π = {dR;R ∈ Π} ⊆ F3 satisfies the Lemma 4.6, then by Definition 3.7, we have dW ∈ conditions of Lemma 4.6. hα ,α i,∀W ∈ reg(S ,S ). By assumption and Equation i1 i2 i1 i2 (3), {Q,Q′} ⊆ [R]i1,i2 ⊆ reg(Si1,Si2). So dQ,dQ′ ∈ ℓ = 1,··· ,L. So by Lemma B.3, all equivalent classes in hα ,α i. Meanwhile, since [R] ∈ I satisfies Property (a), I satisfy Property (a). In particular, all equivalent classes in i1 i2 ℓ then dQ′ ∈ hdQ,α¯i. So dQ′ ∈ hαi1,αi2i∩hdQ,α¯i = hdQi Ic =IL satisfiesproperty(a).ThentheconclusionofLemma and the first claim is true. 4.14 is obtained by Lemma B.1. We now prove the second claim. If [R] 6= [S ],∀i ∈ i APPENDIX C {1,2,3}, then by Definition 4.7, [[R]] = [R] for some {i1,i2} ⊆ {1,2,3} and by the proven result, di1Q,′i2∈ hdQi. If PROOF OFTHEOREM4.16 [R] = [S ] for some i ∈ {1,2,3}, then by Definition 4.7, we Here, we prove Theorem 4.16. First, we prove some lem- i have the following two cases: mas. Case 1: [[R]]=[S ] =[S ] ∪[S ] , where {j ,j }= Lemma C.1: If RG(D∗∗) has two terminal regions, then i i i i,j1 i i,j2 1 2 {1,2,3}\{i}.By the provenresult, we have α =d ∈hd i RG(D∗∗) is feasible. i Si Q and dQ′ ∈hdSii. So dQ′ ∈hdQi. Proof: Suppose RG(D∗∗) has two terminal regions T1 Case 2: [[R]] = [Si]j1,j2, where {j1,j2} = {1,2,3}\{i}. and T2. We have the following two cases: By the proven result, we have dQ′ ∈hdQi. Case 1: Ω1,2 6= ∅. Then there is a Q ∈ D∗∗\Π such that In both cases, we have dQ′ ∈hdQi. So the second claim is Q →Ti,i = 1,2. Similar to what we did in Remark 4.4, we true. can first constructa code on the set {R∈D∗∗;R→Q} such Lemma B.2: Suppose I ={[S1],[S2],[S3],··· ,[RK]} is a that dQ = α¯. Then for all R such that Q → R → Ti for partition of Π in which all equivalentclasses satisfy Property some i∈{1,2}, let dR =α¯. By this construction, we obtain (a). Suppose {[R],[R′]} ⊆ I and there is a Λ such that a solution of RG(D∗∗). So RG(D∗∗) is feasible. j Λj ⊆[[R′]]∪[[R′′]],where[[R′]](resp.[[R′′]])isasubclassof Case 2: Ω1,2 = ∅. Then RG(D∗∗) is terminal separable. [R′](resp.[R′′]).Thenα¯ ∈hdP′,dP′′iforanyP′ ∈Λj∩[[R′]] From Lemma 4.5, we have Λj * reg(Si1,Si2),∀{i1,i2} ⊆ and P′′ ∈Λj ∩[[R′′]]. {1,2,3}, and |Λj| ≥ 2,j = 1,2. By enumerating, we have Proof: Since C˜ satisfies condition (3) of Lemma 4.6 the following three subcases: Π and Λ ⊆[[R′]]∪[[R′′]], then α¯ ∈hd ;R∈Λ i=hd ;R∈ Case 2.1: |Λ | > 2 and |Λ | > 2. Let I = {[R];R ∈ Π}, j R j R 1 2 0 (Λ ∩[[R′]])∪(Λ ∩[[R′′]])i. By LemmaB.1, hd ;R∈(Λ ∩ where [R]={R} for all R ∈Π. Clearly, I is a partition of j j R j 0 [[R′]])∪(Λj ∩[[R′′]])i=hdP′,dP′′i. So α¯ ∈hdP′,dP′′i. Π and is compatible. By Lemma 4.13, RG(D∗∗) is feasible. Lemma B.3: Suppose I = {[S ],[S ],[S ],··· ,[R ]} is Case2.2:|Λ |>2and|Λ |=2.LetI ={Λ }∪{[R];R∈ 1 2 3 K 1 2 2 a partition of Π and I′ is a contraction of I by combining Π\Λ }, where [R] = {R} for all R ∈ Π\Λ . Clearly, I is a 2 2 two connected equivalent classes [R′] and [R′′] in I. If all partition of Π and is compatible. By Lemma 4.13, RG(D∗∗) equivalentclassesinI satisfy Property(a),thenallequivalent is feasible. classes in I′ satisfy Property (a). Case 2.3: |Λ | = |Λ | = 2 and Λ ∩Λ = ∅. Let I = 1 2 1 2 Proof: Suppose [R] ∈ I′. If [R] 6= [R′] ∪ [R′′], then {Λ ,Λ }∪{[R];R ∈ Π\(Λ ∪Λ )}, where [R] = {R} for 1 2 1 2 [R]∈I,andbyassumption,[R]satisfiesproperty(a).Nowwe all R ∈ Π\(Λ ∪Λ ). Clearly, I is a partition of Π and is 1 2 suppose[R]=[R′]∪[R′′].Since,[R′]and[R′′]areconnected, compatible. By Lemma 4.13, RG(D∗∗) is feasible. by Definition 4.9, we have the following two cases: Case 2.4: |Λ | = |Λ | = 2 and Λ ∩Λ 6= ∅. If Λ = Λ , 1 2 1 2 1 2 Case 1: There is a Λ ⊆[[R′]]∪[[R′′]], where [[R′]] (resp. then it is easy to construct a code C˜ satisfies the conditions j Π [[R′′]])is asubclassof[R′](resp.[R′′]). By LemmaB.2,α¯ ∈ of Lemma4.6. So RG(D∗∗) is feasible. Thus,we can assume hdP′,dP′′i,whereP′ ∈Λj∩[[R′]]andP′′ ∈Λj∩[[R′′]].Then Λ1 6= Λ2. Then by proper naming, we can assume Λ1 = dP′′ ∈ hdP′,α¯i and dP′ ∈ hdP′′,α¯i. Since, by assumption, {Q1,Q2} and Λ2 = {Q1,Q3}. By Lemma 4.5, {Q1,Q2} * [R′] and [R′′] satisfy property (a), then hdQ,α¯i=hdP′,α¯i= reg(Si1,Si2) and {Q1,Q3} * reg(Si1,Si2) for all {i1,i2} ⊆ hdP′′,α¯i and dQ′ ∈hdQ,α¯i,∀{Q,Q′}⊆[R]=[R′]∪[R′′]. {1,2,3}. Then one of the following two cases hold: Case 2: There is a subset {i ,i } ⊆ {1,2,3} such that Case 2.4.1: {Q ,Q } ⊆ reg(S ,S ) for some {i ,i } ⊆ 1 2 2 3 i1 i2 1 2 reg([R′] )∩reg([R′′] )6=∅.PickaQ ∈reg([R′] )∩ {1,2,3}.LetI ={[Q ]}∪{[R];R∈Π\[Q ]},where[Q ]= i1,i2 i1,i2 0 i1,i2 1 1 1 reg([R′′] ). Since, by assumption, [R′] and [R′′] satisfy {Q } ∪ reg(Q ,Q ) and [R] = {R} for all R ∈ Π\[Q ]. i1,i2 1 2 3 1 property (a), then hdQ,α¯i = hdQ0,α¯i = hdQ′,α¯i and Clearly, I is a partition of Π and is compatible. By Lemma dQ′ ∈hdQ,α¯i,∀{Q,Q′}⊆[R]=[R′]∪[R′′]. 4.13, RG(D∗∗) is feasible. Inbothcases,[R]=[R′]∪[R′′] satisfiesproperty(a).Thus, Case 2.4.2: {Q2,Q3} * reg(Si1,Si2) for all {i1,i2} ⊆ all equivalent classes in I′ satisfy Property (a). {1,2,3}.LetI ={[Q ]}∪{[R];R∈Π\[Q ]},where[Q ]= 1 1 1 Now we can prove Lemma 4.14. {Q ,Q ,Q }and[R]={R}forallR∈Π\[Q ].Clearly,I is 1 2 3 1 Proof of Lemma 4.14: Since each equivalent class [R] apartitionofΠandiscompatible.ByLemma4.13,RG(D∗∗) in I contains exactly one region R, so [R] naturally satisfies is feasible. 0 property (a) and [S ]6=[S ] for all {i,j}⊆{1,2,3}. By the above discussions, we proved that RG(D∗∗) is i j By Definition 4.11, I = I , where I ,I ,··· ,I = I feasible. c L 0 1 L c is a sequence of partitions of Π such that I is a contraction Lemma C.2: Suppose RG(D∗∗) has three terminal regions ℓ of I by combining two connected equivalent classes in and is terminalseparable. ThenRG(D∗∗) is feasible if one of ℓ−1 I and, for any {i,j} ⊆ {1,2,3}, [S ] 6= [S ] in I , the following conditions hold: ℓ−1 i j ℓ−1 (1) |Λ |≥3 and |Λ |≥3 for some {j ,j }⊆{1,2,3}; Case 1.1.1: Λ ∩(reg◦(S ,S )∪reg◦(S ,S ))6=∅. By j1 j2 1 2 j3 ℓ1 ℓ2 ℓ2 ℓ3 (2) For any {j ,j } ⊆ {1,2,3}, if |Λ | = |Λ | = 2, then (4) of Lemma C.2, RG(D∗∗) is feasible. 1 2 j1 j2 Λ ∩Λ =∅; Case1.1.2:Λ ∩(reg◦(S ,S )∪reg◦(S ,S ))=∅.Then j1 j2 j3 ℓ1 ℓ2 ℓ2 ℓ3 (3) S ∈/ Λ for all i,j ∈{1,2,3}; Λ ⊆reg(S ,S )∪{S }. Moreover, since by Lemma 4.5, i j j3 ℓ1 ℓ3 ℓ2 (4) There is a subset {ℓ′,ℓ′′} ⊆ {1,2,3} such that Λj ∩ Λj3 * reg(Si1,Si2),∀{i1,i2} ⊆ {1,2,3}, then either Λj3 = reg◦(Sℓ′,Sℓ′′)6=∅ for all j ∈{1,2,3}. {S1,S2,S3} or {Q,Sℓ2}⊆Λj3 for some Q∈reg◦(Sℓ1,Sℓ3). Proof: 1) Suppose condition (1) holds. Let j3 ∈ Let I = {[Sℓ1],[Sℓ2],[Sℓ3],[P2]}, where [Sℓ1] = {Sℓ1}, {1,2,3}\{j1,j2}. From Lemma 4.5, we have Λj3 * [Sℓ2] = {Sℓ2} ∪ reg◦(Sℓ1,Sℓ3), [Sℓ3] = {Sℓ3} and [P2] = reg(Si1,Si2),∀{i1,i2} ⊆ {1,2,3}, and |Λj3| ≥ 2. Then we reg◦(Sℓ1,Sℓ2)∪reg◦(Sℓ2,Sℓ3). Clearly, I is a partition of Π have the following two cases: and is compatible. By Lemma 4.13, RG(D∗∗) is feasible. Case 1: |Λj3| > 2. Let I0 = {[R];R ∈ Π}, where [R] = Case 1.2: P0 ∈ reg◦(Sℓ1,Sℓ3). This case can be further {R} for all R ∈ Π. Clearly, I is a partition of Π and is divided into the following subcases: 0 compatible. By Lemma 4.13, RG(D∗∗) is feasible. Case 1.2.1: |Λj3| = 3 or Λj3 ⊆ {P0,P1,P2}. Let I = Case 2: |Λj3| = 2. Let I = {Λj3}∪{[R];R ∈ Π\Λj3}, {[P2]}∪{[R];R ∈ Π\[P0]}, where [P2] = {P0,P1,P2} and where [R]={R} for all R∈Π\Λj3. Clearly, I is a partition [R] = {R},∀R ∈ Π\[P2]. Clearly, I is a partition of Π and ofΠandiscompatible.ByLemma4.13,RG(D∗∗)isfeasible. is compatible. By Lemma 4.13, RG(D∗∗) is feasible. 2) Suppose condition (2) holds. Let A ⊆ {1,2,3} be such Case 1.2.2: |Λj3|=2 and Λj3∩{P0,P1,P2}=∅. Assume that |Λj| = 2,∀j ∈ A, and |Λj| > 2,∀j ∈ {1,2,3}\A. Let Λj3 = {P3,P4}. Let I = {[P2],[P3]}∪{[R];R∈ Π\([P2]∪ I = {Λj;j ∈ A}∪{[R];R ∈ Π\(∪j∈AΛj)}, where [R] = [P3])},where[P2]={P0,P1,P2},[P3]={P3,P4}and[R]= {R} for all R ∈ Π\(∪j∈AΛj). Clearly, I is a partition of Π {R},∀R∈Π\([P2]∪[P3]). Clearly, I is a partition of Π and and is compatible. By Lemma 4.13, RG(D∗∗) is feasible. is compatible. By Lemma 4.13, RG(D∗∗) is feasible. 3) Suppose condition (3) holds. Let I = {[S1],[S2],[S3], Case 1.2.3: |Λj3| = 2 and Λj3 ∩{P0,P1,P2} = {P2}. By [R]}, where [S ] = {S } for i ∈ {1,2,3} and [R] = (4) of Lemma C.2, RG(D∗∗) is feasible. i i Π\{S1,S2,S3}. Clearly, I is a partition of Π and is com- Case 1.2.4: |Λj3| = 2 and Λj3 ∩{P0,P1,P2} = {P1} (or patible. By Lemma 4.13, RG(D∗∗) is feasible. {P0}). By proper naming, we can assume Λj3 = {P1,P3}, 4) Without loss of generality, assume ℓ = 1,ℓ′ = 2 and where P3 ∈/ {P0,P1,P2}. If P3 6=Sℓ,∀ℓ∈ {1,2,3}, then by ℓ′′ =3.LetI ={[S1],[S2],[S3]},where[S1]=reg(S1,S2)∪ (3) of Lemma C.2, RG(D∗∗) is feasible. So we assume P3 = reg(S1,S3) ∪ reg◦(S2,S3), [S2] = {S2} and [S3] = {S3}. Sℓ for some ℓ ∈ {1,2,3}. Since P1 ∈ reg◦(Sℓ2,Sℓ3) and, Clearly, I is a partition of Π and is compatible. By Lemma by Lemma 4.5, Λj3 = {P1,P3} * reg(Si1,Si2),∀{i1,i2} ⊆ 4.13, RG(D∗∗) is feasible. {1,2,3}, then P3 = Sℓ1. Let j3 = 1,j1 = 2,j2 = 3 and Lemma C.3: Suppose RG(D∗∗) has three terminal regions ℓi =i (i=1,2,3). Then the condition (C-IR) holds. andisterminalseparable.IfRG(D∗∗)isnotfeasible,thenthe Case2:Thereisanℓ1 ∈{1,2,3}suchthatSℓ1 ∈Λj1∪Λj2. condition (C-IR) holds. Let {ℓ2,ℓ3}={1,2,3}\{ℓ1}. We can further divide this case Proof: If Λ = Λ for some {j ,j } ⊆ {1,2,3}, then into the following subcases: j1 j2 1 2 by lemma C.1, we can construct a code C˜Π satisfies the Case 2.1: Sℓ1 ∈Λj1 ∩Λj2. By proper naming, we assume conditions of Lemma 4.6. So RG(D∗∗) is feasible. Thus, we Λ ={S ,P } and Λ ={S ,P }. (13) assumeΛ ,Λ andΛ aremutuallydifferent.SinceRG(D∗∗) j1 ℓ1 1 j2 ℓ1 2 1 2 3 is not feasible, then by (1), (2) of Lemma C.2, there is a Since, by Lemma 4.5, Λj1, Λj2 * reg(Si1,Si2),∀{i1,i2} ⊆ {j ,j }⊆{1,2,3} such that {1,2,3}, then we have 1 2 |Λj1|=|Λj2|=2 and |Λj1 ∩Λj2|=1. (10) P1,P2 ∈reg◦(Sℓ2,Sℓ3). (14) Let j3 ∈ {1,2,3}\{j1,j2}. By enumerating, we can divide If Λj3 ∩ reg◦(Sℓ2,Sℓ3) 6= ∅, then by (4) of Lemma C.2, our discussion into the following cases: RG(D∗∗) is feasible. So we assume Λ ∩reg◦(S ,S )=∅. j3 ℓ2 ℓ3 Case 1: Λ ∪ Λ ⊆ reg◦(S ,S ) ∪ reg◦(S ,S ) ∪ Then j1 j2 1 2 1 3 reg◦(S ,S ). By (10), we can assume 2 3 Λ ⊆reg(S ,S )∪reg(S ,S ). (15) j3 ℓ1 ℓ2 ℓ1 ℓ3 Λ ={P ,P } and Λ ={P ,P }. (11) j1 1 2 j2 0 2 We have the following two subcases: By Lemma 4.5, Λj1 * reg(Si1,Si2),∀{i1,i2} ⊆ {1,2,3}. Case 2.1.1: Λj3 ∩ (reg◦(Sℓ1,Sℓ2) ∪ reg◦(Sℓ1,Sℓ3)) 6= ∅. Then by proper naming, we can assume Withoutloss of generality,assume Q ∈Λ ∩reg◦(S ,S ). 1 j3 ℓ1 ℓ2 P ∈reg◦(S ,S ) and P ∈reg◦(S ,S ). (12) Since, by Lemma 4.5, Λj3 * reg(Si1,Si2),∀{i1,i2} ⊆ 2 ℓ1 ℓ2 1 ℓ2 ℓ3 {1,2,3}, then there is a Q ∈ reg(S ,S )\{S } such that 2 ℓ1 ℓ3 ℓ1 where{ℓ ,ℓ ,ℓ } isa fixedpermutationof{1,2,3}.Also, by Q ∈ Λ . Let I = {[S ],[S ]} ∪ {[R];R ∈ Π\([S ] ∪ 1 2 3 2 j3 ℓ1 ℓ3 ℓ1 Lemma 4.5, Λj2 * reg(Si1,Si2),∀{i1,i2} ⊆ {1,2,3}. Then [Sℓ3])}, where [Sℓ1] = {Sℓ1}∪reg(P1,P2), [Sℓ3] = {Q1}∪ for P , we have the following subcases: reg(S ,S )\{S } and [R] = {R},∀R ∈ Π\([S ]∪[S ]). 0 ℓ1 ℓ3 ℓ1 ℓ1 ℓ3 Case 1.1: P ∈ reg◦(S ,S ). We can further divide this Clearly, I is a partition of Π and is compatible. By Lemma 0 ℓ2 ℓ3 case into the following two subcases: 4.13, RG(D∗∗) is feasible.