Outer Bounds and a Functional Study of the Edge Removal Problem

Abstract

In this paper, we investigate the impact of a single edge on the capacity region of a network of error-free, point-to-point links. A family of networks and edges is said to exhibit the "edge removal property" if for any network and edge in the family, removing a δ-capacity edge changes the capacity region by at most δ in each dimension. We derive a sufficient condition on network coding functions to guarantee that the edge removal property holds when the network is operated using functions satisfying the condition. Also, we extend the family of network capacity bounds for which it is known that removing a single edge of capacity δ changes the capacity bound by at most f(δ) in each dimension. Specifically, we show that removing a single δ-capacity edge changes the Generalized Network Sharing outer bound by at most δ in each dimension and the Linear Programming outer bound by at most a constant times δ in each dimension.

Additional details