  The encoding complexity of network coding for single multicast networks has
been intensively studied from several aspects: e.g., the time complexity, the
required number of encoding links, and the required field size for a linear
code solution. However, these issues as well as the solvability are less
understood for networks with multiple multicast sessions. Recently, Wang and
Shroff showed that the solvability of networks with two unit-rate multicast
sessions (2-URMS) can be decided in polynomial time. In this paper, we prove
that for the 2-URMS networks: $1)$ the solvability can be determined with time
$O(|E|)$; $2)$ a solution can be constructed with time $O(|E|)$; $3)$ an
optimal solution can be obtained in polynomial time; $4)$ the number of
encoding links required to achieve a solution is upper-bounded by
$\max\{3,2N-2\}$; and $5)$ the field size required to achieve a linear solution
is upper-bounded by $\max\{2,\lfloor\sqrt{2N-7/4}+1/2\rfloor\}$, where $|E|$ is
the number of links and $N$ is the number of sinks of the underlying network.
Both bounds are shown to be tight.
