Edge-Cut Bounds on Network Coding Rates

A bound on network coding rates is developed that generalizes an edge-cut bound on routing rates. The bound involves progressively removing edges from the network graph and checking whether certain strengthened $d$-separation conditions are satisfied. The bound improves on the cut-set bound, and its efficacy is demonstrated by showing that routing is rate-optimal for some commonly cited examples in the networking literature.