A Bound on Undirected Multiple-Unicast Network Information Flow

One of the important unsolved problems in information theory is the conjecture that the undirected multiple-unicast network information capacity is the same as the routing capacity. This conjecture is verified only for a handful of networks and network classes. Moreover, only two explicit upper bounds on information capacity are known for general undirected networks: the sparsest cut bound and the linear programming bound. In this paper, we present an information-theoretic upper bound, called the
partition bound
, on the capacity of general undirected multiple-unicast networks. We show that a decision version problem of computing the bound is NP-complete. We present two classes of undirected multiple-unicast networks such that the partition bound is achievable by routing. Thus, the conjecture is proved for these classes of networks. Recently, the conjecture was proved for a new class of networks defined by properties relating to cut-set and source-sink paths. We show the existence of a network outside of this new class of networks such that the partition bound is achievable by routing.