Cut Sets and Information Flow in Networks of Two-way Channels

A network of two way channels (TWCs) is specified by a graph having an edge between vertex u and vertex v if there is a TWC between these vertices. A cut-set bound is derived for such networks when network coding is permitted, and some implications of this bound are discussed. For example, the bound generalizes and improves upon a flow cut-set bound which is standard in network optimization theory. It follows that routing is rate-optimal if routing achieves the standard flow cut-set bound. Other consequences are that linear network coding is optimal for multicasting, and that one can separate channel and network coding for multicasting in networks of TWCs.