Edge removal in undirected networks
Michael L. Langberg, Michelle Effros · 2021
The edge-removal problem asks whether the removal of a$\lambda$-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than$\lambda$. We prove that for undirected networks, removing a$\lambda$capacity edge decreases the rate by$O(\lambda$. 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.