Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
Abstract
Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes but never settled in general. In this paper, we disprove it by constructing a finite connected simple undirected network with unit shared edge capacities, maximum degree three, and distinct leaf terminals, on which a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The construction turns a short completion-time code into a reversible circuit whose registers all carry independent messages, and a temporal metric on its wires yields the strict routing bound. The underlying integer-coefficient construction works over every finite field and every nontrivial finite abelian group; for deterministic fixed-schedule codes the common-rate supremum is one and the closure of the rate region is the unit cube. Amplifying the gap with a degree-preserving tensor construction and an even subdivision gives, for every 0<β<1, an unbounded family of connected, simple, subcubic, bipartite networks with girth at least nβ on which coding approaches rate one while routing is bounded by Kβ/(log n)c, with one positive exponent c independent of β. The finite counterexample and the family theorem are formalized in Lean.
Related
BibTeX
@misc{zhang2026network,
title = {{Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks}},
author = {Xindan Zhang and Baochun Li and Zongpeng Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09367},
eprint = {2610.09367},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09367},
}
RIS
TY - UNPB
TI - Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
AU - Xindan Zhang
AU - Baochun Li
AU - Zongpeng Li
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09367
UR - https://arxiv.org/abs/2610.09367
AB - Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes but never settled in general. In this paper, we disprove it by constructing a finite connected simple undirected network with unit shared edge capacities, maximum degree three, and distinct leaf terminals, on which a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The construction turns a short completion-time code into a reversible circuit whose registers all carry independent messages, and a temporal metric on its wires yields the strict routing bound. The underlying integer-coefficient construction works over every finite field and every nontrivial finite abelian group; for deterministic fixed-schedule codes the common-rate supremum is one and the closure of the rate region is the unit cube. Amplifying the gap with a degree-preserving tensor construction and an even subdivision gives, for every 0<β<1, an unbounded family of connected, simple, subcubic, bipartite networks with girth at least n^β on which coding approaches rate one while routing is bounded by K_β/(log n)^c, with one positive exponent c independent of β. The finite counterexample and the family theorem are formalized in Lean.
ER -