Beyond the Butterfly ¿ A Graph-Theoretic Characterization of the Feasibility of Network Coding with Two Simple Unicast Sessions
Chih-Chun Wang, Ness B. Shroff · 2007
The problem of network coding with two simple unicast sessions is considered for general directed acyclic graphs. An explicit graph-theoretic characterization is provided for the feasibility of whether two symbols at different sources can be simultaneously transmitted to the designated sinks via network coding. The existence of a routing scheme is equivalent to finding edge-disjoint paths. Similarly, in this paper it is proven that the existence of a network coding scheme is equivalent to finding paths with controlled edge overlaps, and the characterization includes the well-studied butterfly graph as a special case. Various generalizations and implications are discussed based on the constructive nature of the flow-based conditions. For example, it is shown that a linear network coding scheme using only six paths is as effective as any non-linear network coding scheme.