On Computing the Partition Bound for Undirected Multi-Source Unicast Network Information Flow

Characterization and computation of the optimal information flow rate of network models are some of the central problems in communication theory. Network coding was introduced in the year 2000 as a scheme to improve the information rate in networks. Subsequently, the capacity of many classes of directed acyclic networks and optimal network codes have been characterized. However, the benefit of network coding in undirected multi-source unicast networks is not clearly understood yet. In particular, whether network coding has any rate advantage over routing in undirected multi-source unicast networks is a well-known open problem. Recently, an upper bound on the information flow in this network model, called the partition bound, is characterized. This paper focuses on computing this bound and presents a procedure to obtain an upper bound on the information flow rate.