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₂. Current characterizations of the multiple unicast capacity region in this setting have a large number of inequalities, which makes them hard to explicitly evaluate. In this work we consider a slightly different problem. We assume that we only know certain minimum cut values for the network, e.g., mincut(S_i, T_j), where S_i ⊆ {si, 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 based on linear codes. Towards this end, we begin by defining a base 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 takes different forms depending upon the relationship of the different cut values in the network.