Paperlane

no. 3 · Tuesday 27 October 2026

Proof of the Langberg-Médard Multiple Unicast Conjecture

Kai Cai, Guangyue Han, Mengxi Yang and Wenan Zang

math.IT

Abstract

Let $\mathcal{N}=(V,A,S, R)$ be a directed network, where $D=(V,A)$ is a digraph, $S=\{s_1,s_2,\ldots,s_k\}\subseteq V$ is a set of senders, and $R=\{r_1,r_2,\ldots,r_k\}\subseteq V$ is a set of receivers. We prove that if, for each $1\le j \le k$, there exist $k$ pairwise arc-disjoint directed paths in $D$, one from each $s_i$ to $r_j$, then the underlying undirected network of ${\cal N}$, with unit capacities, admits a feasible $(s_1,s_2,\ldots,s_k)$-$(r_1,r_2,\ldots,r_k)$ multiflow of value $1$ for each pair $(s_i,r_i)$, $i=1,2,\ldots,k$. This establishes the multiple unicast conjecture proposed by Langberg and Médard in 2009.

fields
Information Theory, Combinatorics
pdf ↗ page arXiv:2610.33497 ↗