The Two-Unicast Problem
From MaRDI portal
Publication:5375551
DOI10.1109/TIT.2016.2628797zbMATH Open1395.94010arXiv1506.01105OpenAlexW2963881246MaRDI QIDQ5375551
Chih-Chun Wang, David N. C. Tse, V. Anantharam, Sudeep Kamath
Publication date: 14 September 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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 a 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 this bound is the tightest edge-cut bound for two-unicast networks and is tight in several bottleneck 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 as hard as the most general network coding problem. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing capacity of general two-unicast networks.
Full work available at URL: https://arxiv.org/abs/1506.01105
Related Items (1)
This page was built for publication: The Two-Unicast Problem
