Network coding can beat routing in undirected networks
Researchers disproved a 2004 conjecture by constructing an undirected network where combining messages achieves a rate strictly above the maximum fractional routing rate.
Edited by Boris Djordjevic · Paperfoot
In a preprint, researchers proved that network coding can beat fractional routing in undirected networks by constructing a finite mathematical network where combining messages achieves a rate strictly above the routing limit. Network coding lets network nodes combine messages rather than merely forward them. In undirected networks, where two directions of a link share its capacity, a 2004 conjecture by Li and Li stated that coding gives no advantage over fractional routing. The authors disproved this conjecture by designing a finite, connected network with unit shared link capacities and at most three connections per node. On this setup, a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The authors also extended the construction to an unbounded family of networks and formalized their proofs in Lean, a software proof assistant.
Why it matters
The mathematical proof settles a twenty-year-old open question in network theory by demonstrating that routing alone cannot achieve the maximum possible information flow in all undirected networks. By verifying the counterexample in the Lean proof assistant, the work confirms that the throughput gap holds rigorously across both individual networks and infinite network families.
Caveats
The result is a theoretical proof on idealized network models rather than an evaluation on physical communication networks. In addition, the paper is a preprint that has not yet undergone peer review.
In this paper
undirected multiple-unicast network coding
- Methods
- binary linear block code (this paper)Lean
- Links
- Code
What it shows
- For every scalar instance, the closure of both the symbol and field-linear rate regions is the unit cube [0,1]^k.
Its symbol and field-linear vector regions have closure [0,1]^{k}.
Proposition IV.2.
- For every scalar instance, exact deterministic fixed-schedule rate vectors over any nontrivial finite abelian group and field-linear rate vectors over any field equal the rational vectors in [0,1)^k.
For every scalar instance, the set of rate vectors of exact deterministic fixed-schedule codes over a nontrivial finite abelian group, and the set of rate vectors of field-linear codes over any field, finite or infinite, both equal the set of rational vectors in [0,1)^{k}.
Proposition IV.3 (Exact finite-block region).
- Every exact deterministic fixed-schedule protocol over a finite alphabet with size greater than one satisfies the leaf bound B_i <= D when the source has degree one.
If s_{i}\neq t_{i} and the source s_{i} has one incident edge, every exact deterministic fixed-schedule protocol over a finite alphabet A, |A|>1, satisfies B_{i}≤ D.
Lemma IV.1 (Leaf bound).
- The finite counterexample and family theorem are formalized in Lean relying solely on standard axioms.
The finite counterexample and the family theorem are formalized in Lean, relying on its standard axioms only.
VII Concluding Remarks
Quoted word for word from the full text on arXiv.
The paper
Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
arXiv, Oct 7, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.09367
arXiv:2610.09367v1 in cs.IT, also math.IT
Comments: 17 pages
Cite as BibTeX
@misc{zhang2026network,
title = {Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks},
author = {Zhang, Xindan and Li, Baochun and Li, Zongpeng},
year = {2026},
eprint = {2610.09367},
archivePrefix = {arXiv},
primaryClass = {cs.IT},
doi = {10.48550/arxiv.2610.09367},
url = {https://arxiv.org/abs/2610.09367}
}
