Generalized Network Sharing Outer Bound and the Two-Unicast Problem

We describe a simple improvement over the Network Sharing outer bound for the multiple unicast problem. We call this the Generalized Network Sharing (GNS) outer bound. We note two properties of this bound with regard to the two-unicast problem: a) it is the tightest bound that can be realized using only edge-cut bounds and b) it is tight in the special case when all edges except those from a so-called minimal GNS set have sufficiently large capacities. Finally, we present an example showing that the GNS outer bound is not tight for the two-unicast problem.