OpenAlex ·
Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.09367
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
UniCSI Towards a Universal Wi-Fi CSI Encoder for Ubiquitous Human Sensing
Energy-Aware Receiver-initiated MAC Protocol for Energy Harvesting IoT
Deadline-Aware Multi-Agent Reinforcement Learning for TSN-Based Vehicular Edge Networks
Digital Twin for Pre-Deployment Validation of AI-Driven Safety-Critical Industrial Edge Control Loops
Secure Quantum Handshakes: Quantum Network Verification Via Simon's Algorithm
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.