arXiv · Oct 24, 2026
When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability
By Liu S, Li Z, Li B
In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings. In multiple unicast, where each source sends a message only to its prescribed destination, a central question is under what conditions fractional routing suffices to attain the transmission rates supported by network coding. We prove that, for any given collection of multiple-unicast demands in an undirected network, if the maximum flow between every pair of distinct destinations is at least the total demand rate, then the following are equivalent in feasibility: multiple-unicast coding, multiple-unicast fractional routing, and simultaneous fractional routing of all source rates to any fixed destination. Verifying this pairwise maximum-flow condition and, when it holds, deciding feasibility of the given multiple-unicast demands require at most as many maximum-flow computations as there are destinations. As a direct corollary, we prove the Langberg–M'edard conjecture: if a directed network supports coded multicast of independent source messages at a common rate to every destination, then removing arc directions without changing capacities permits simultaneous fractional routing at that rate for all prescribed source–destination pairs.