PreprintarXiv licencearXiv
Proof of the Langberg-Médard Multiple Unicast Conjecture
Abstract
Let 𝒩=(V,A,S, R) be a directed network, where D=(V,A) is a digraph, S={s1,s2,…,sk}⊆ V is a set of senders, and R={r1,r2,…,rk}⊆ V is a set of receivers. We prove that if, for each 1≤ j ≤ k, there exist k pairwise arc-disjoint directed paths in D, one from each si to rj, then the underlying undirected network of cal N, with unit capacities, admits a feasible (s1,s2,…,sk)-(r1,r2,…,rk) multiflow of value $1$ for each pair (si,ri), i=1,2,…,k. This establishes the multiple unicast conjecture proposed by Langberg and Médard in 2009.
Related
BibTeX
@misc{cai2026proof,
title = {{Proof of the Langberg-Médard Multiple Unicast Conjecture}},
author = {Kai Cai and Guangyue Han and Mengxi Yang and Wenan Zang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33497},
eprint = {2610.33497},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33497},
}
RIS
TY - UNPB
TI - Proof of the Langberg-Médard Multiple Unicast Conjecture
AU - Kai Cai
AU - Guangyue Han
AU - Mengxi Yang
AU - Wenan Zang
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33497
UR - https://arxiv.org/abs/2610.33497
AB - Let 𝒩=(V,A,S, R) be a directed network, where D=(V,A) is a digraph, S={s_1,s_2,…,s_k}⊆ V is a set of senders, and R={r_1,r_2,…,r_k}⊆ V is a set of receivers. We prove that if, for each 1≤ j ≤ 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,…,s_k)-(r_1,r_2,…,r_k) multiflow of value $1$ for each pair (s_i,r_i), i=1,2,…,k. This establishes the multiple unicast conjecture proposed by Langberg and Médard in 2009.
ER -