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 max{2,⌊(√2N-7/4)+1/2⌋}, where N is the number of sinks. Both bounds are shown to be tight.