A Proof of the Langberg-Médard Conjecture

Overview & Synopsis

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, the precise capability boundary between coding and fractional routing has long remained unresolved. In this context, the Langberg-Médard conjecture asserts that if all sources in a directed network transmit independent messages at a common rate and every destination can recover all source messages by network coding, then replacing every arc by an undirected edge of equal capacity yields a network in which fractional routing can simultaneously deliver each source's message to its prescribed destination at the same common rate. We prove the Langberg-Médard conjecture for any number of source-destination pairs and arbitrary network topology. More generally, for an undirected network with a given source set and a disjoint set of allowed destinations, we establish a necessary and sufficient cut-capacity condition for simultaneous unit-rate fractional routing under every assignment of an allowed destination to each source. Networks satisfying the hypothesis of the Langberg-Médard conjecture necessarily satisfy this cut condition, so the conjecture follows as a direct corollary.