A Local Perspective on the Edge Removal Problem

The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge e with capacity R_e reduces the achievable rate on each source by no more than R_e. In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a local perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge e. Our central results give sufficient conditions on the function carried by edge e in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e is removed.