{"id":"arxiv/2610.33497","url":"https://arxiv.org/abs/2610.33497","tags":["cs.IT","math.CO"],"score":0,"title":"Proof of the Langberg-Médard Multiple Unicast Conjecture","domain":"cs.IT","source":"arxiv","authors":["Kai Cai","Guangyue Han","Mengxi Yang","Wenan Zang"],"reviews":0,"subject":"cs.IT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-24","reactions":{}}