PaperfootJoin free
arXiv

A math proof resolves a 2009 network flow conjecture

The preprint proves that pairwise arc-disjoint directed paths from all senders to each receiver ensure unit flows between matched pairs in an undirected network.

Paper by Kai Cai, Guangyue Han, Mengxi Yang, Wenan Zang
A network of light blue and dark blue-green routes surrounds a continuous black path, with circular endpoints and a small fan of separate gray branches.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

A preprint proves the multiple unicast conjecture, a mathematical problem about network routing proposed by Langberg and Médard in 2009. The setup considers a directed network with a set of senders and an equal number of receivers. The authors proved that if, for each receiver, there exist pairwise arc-disjoint directed paths from every sender, the underlying undirected network with unit capacities admits a feasible multiflow of value one between each matched sender and receiver pair. Here, arc-disjoint paths are directed routes that share no links. The result shows that this connectivity condition guarantees that all pairs can simultaneously transmit at unit flow in the undirected network.

Why it matters

The proof settles a theoretical question open since 2009, establishing that arc-disjoint path conditions in a directed network guarantee feasible multi-user flows in the underlying undirected graph.

Caveats

The work is a theoretical proof published as a preprint that has not yet been peer-reviewed, and its guarantee applies under the assumption of unit link capacities.

In this paper

multiple unicast problem

What it shows

The inequality bounding the distance from any vertex to receiver r_i by q(v) plus W holds for all vertices and receiver indices.

The inequality d(v,r_{i})≤ q(v)+W holds for all v\in V and 1≤ i≤ k.

Lemma 4.3.

For each position m from 1 to 3, the function F_m matches g_m(i) at receiver r_i and is 1-Lipschitz on V.

For each 1≤ m≤ 3, the function F_{m} satisfies F_{m}(r_{i})=g_{m}(i) for 1≤ i≤ k, and F_{m} is 1 -Lipschitz on V.

Lemma 4.1.

If both X and its complement contain a receiver, then the undirected cut defined by X has size at least k.

If both X and \bar{X} contain a receiver, then |\delta_{G}(X)|≥ k.

Lemma 2.1.

If a receiver lies outside X, then the outgoing directed cut defined by X in D is at least the number of senders in X.

If a receiver lies outside X, then |\delta_{D}^{+}(X)|≥ s(X).

Lemma 2.1.

Quoted word for word from the full text on arXiv.

The paper

Proof of the Langberg-M'edard Multiple Unicast Conjecture

Kai Cai, Guangyue Han, Mengxi Yang, Wenan Zang

arXiv, Oct 24, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.33497

arXiv:2610.33497v1 in cs.IT, also math.CO, math.IT

AbstractPDFHTML

Cite as BibTeX
@misc{cai2026proof,
  title = {Proof of the Langberg-M\'edard Multiple Unicast Conjecture},
  author = {Cai, Kai and Han, Guangyue and Yang, Mengxi and Zang, and Wenan},
  year = {2026},
  eprint = {2610.33497},
  archivePrefix = {arXiv},
  primaryClass = {cs.IT},
  doi = {10.48550/arxiv.2610.33497},
  url = {https://arxiv.org/abs/2610.33497}
}

More in Theory