The Edge-Removal Problem's Connections to the Zero-Error and δ -Dependence Problems in Network Coding

The edge-removal problem addresses the loss in capacity obtained by the removal of an edge of capacity λ from a given network. In the context of network coding, the edge-removal problem has been solved for certain families of networks (such as instances with co-located sources). However, the problem is open for general instances. This work ties the edge-removal problem to two additional problems in the context of network communication: (a) the ' zero-error' network coding problem, which asks whether the zero-error network coding capacity differs from the capacity when error probability is allowed to tend to zero as the blocklength grows; and (b) the ' δ -dependence' problem, which measures the advantage of message dependence in network coding capacity.