Paperlane

no. 4 · Wednesday 28 October 2026

When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability

Sirui Liu, Zongpeng Li and Baochun Li

math.IT · v2 · 14 pp

Abstract

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édard 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.

comments
14 pages, 3 figures. Revised exposition and proof presentation
fields
Information Theory
pdf ↗ page arXiv:2610.33655 ↗