The Two-Unicast Problem
Sudeep Kamath, Venkat Anantharam, David N. C. Tse, Chih-Chun Wang · IEEE Transactions on Information Theory · 2016
We consider the communication capacity of wireline networks for a two-unicast traffic pattern. The network has two sources and two destinations with each source communicating an independent message to its own destination, subject to the capacity constraints on the directed edges of the network. We propose a simple outer bound for the problem that we call the generalized network sharing (GNS) bound. We show that this bound is the tightest edge-cut bound for two-unicast networks and is tight in several cases, though it is not tight in general. We also show that the problem of computing the GNS bound is NP complete. Finally, we show that despite its seeming simplicity, the two-unicast problem is a very difficult problem: the general network coding problem can be reduced to two-unicast. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing the capacity of general two-unicast networks.