An Achievable Region for the Double Unicast Problem Based on a Minimum Cut Analysis

We consider the multiple unicast problem under network coding over directed acyclic networks when there are two source-terminal pairs, s₁-t₁ and s₂-t₂. The capacity region for this problem is not known; furthermore, the outer bounds on the region have a large number of inequalities which makes them hard to explicitly evaluate. In this work we consider a related problem. We assume that we only know certain minimum cut values for the network, e.g., mincut(S_i, T_j), where S_i ⊆ {s₁, s₂} and T_j ⊆ {t₁, t₂} for different subsets S_i and T_j. Based on these values, we propose an achievable rate region for this problem using linear network codes. Towards this end, we begin by defining a multicast region where both sources are multicast to both the terminals. Following this we enlarge the region by appropriately encoding the information at the source nodes, such that terminal t_i is only guaranteed to decode information from the intended source s_i, while decoding a linear function of the other source. The rate region depends upon the relationship of the different cut values in the network.