On the Generalized Network Sharing bound and edge-cut bounds for network coding

We consider sum-rate edge-cut bounds on network coding rates for the multiple unicast problem. We first show that the Generalized Network Sharing (GNS) bound is equivalent to a functional dependence bound in the literature. After defining a notion of profile of an edge-cut, we show that the only profiles for which, every edge-cut with the said profile leads to a fundamental bound on network coding rates, are the so-called GNS profiles and further, we quantify with a tight constant factor, the amount by which network coding can potentially beat edge-cuts associated with other profiles. Finally, we show that the problem of computing the GNS bound is NP-complete, even for two-unicast networks.