Communicating the sum of sources in a 3-sources/3-terminals network

We consider the network communication scenario in which a number of sources Si each holding independent information Xi wish to communicate the sum σ Xi to a set of terminals tj. In this work we consider directed acyclic graphs with unit capacity edges and independent sources of unit-entropy. The case in which there are only two sources or only two terminals was considered by the work of Ramamoorthy [ISIT 2008] where it was shown that communication is possible if and only if each source terminal pair Si/tj is connected by at least a single path. In this work we study the communication problem in general, and show that even for the case of three sources and three terminals, a single path connecting source/terminal pairs does not suffice to communicate σ Xi. We then present an efficient encoding scheme which enables the communication of σ Xi for the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths. Our encoding scheme includes a structural decom position of the network at hand which may be found useful for other network coding problems as well.