  We consider the communication capacity of wireline networks for a two-unicast
traffic pattern. The network has two sources and two destinations with each
source communicating a message to its own destination, subject to the capacity
constraints on the directed edges of the network. We propose a simple outer
bound for the problem that we call the Generalized Network Sharing (GNS) bound.
We show this bound is the tightest edge-cut bound for two-unicast networks and
is tight in several bottleneck cases, though it is not tight in general. We
also show that the problem of computing the GNS bound is NP-complete. Finally,
we show that despite its seeming simplicity, the two-unicast problem is as hard
as the most general network coding problem. As a consequence, linear coding is
insufficient to achieve capacity for general two-unicast networks, and
non-Shannon inequalities are necessary for characterizing capacity of general
two-unicast networks.
