2020/05/20 by Langberg, Michael, Effros, Michelle
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2005.10315
The edge-removal problem asks whether the removal of a λ-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than λ. In this short manuscript, we prove that for undirected networks, removing a λ-capacity edge decreases the rate by O(λ). Through previously known reductive arguments, here newly applied to undirected networks, our result implies that the zero-error capacity region of an undirected network equals its vanishing-error capacity region. Whether it is possible to prove similar results for directed networks remains an open question.