We study the network coding problem of sum-networks with 3 sources and n terminals (3s/nt sum-network), for an arbitrary positive integer n, and derive a sufficient and necessary condition for the solvability of a family of so-called terminal-separab
le sum-network. Both the condition of terminal-separable and the solvability of a terminal-separable sum-network can be decided in polynomial time. Consequently, we give another necessary and sufficient condition, which yields a faster (O(|E|) time) algorithm than that of Shenvi and Dey ([18], (O(|E|^3) time), to determine the solvability of the 3s/3t sum-network. To obtain the results, we further develop the region decomposition method in [22], [23] and generalize the decentralized coding method in [21]. Our methods provide new efficient tools for multiple source multiple sink network coding problems.
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.
