The encoding complexity of network coding with two simple multicast sessions

We consider the encoding complexity of two simple multicast network coding problem (2-SMNC). The network is a directed acyclic graph, where two messages are required to send from two sources to two groups of sinks respectively. We proved that the number of encoding links required to achieve a network coding solution is upper-bounded by max{3; 2N − 2} and the field size required to achieve a linear solution is upper-bounded by equation, where N is the number of sinks. Both bounds are shown to be tight. 1