A Local Perspective on the Edge Removal Problem

Abstract

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.