Portal de Periódicos da CAPES

The Two-Unicast Problem

2016; Institute of Electrical and Electronics Engineers; Volume: 64; Issue: 5 Linguagem: Inglês

10.1109/tit.2016.2628797

1557-9654

Sudeep Kamath, Venkatachalam Anantharam, David Tse, Chih-Chun Wang,

Full-Duplex Wireless Communications

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.