CS Paper Radar

When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability

Sirui Liu, Zongpeng Li, Baochun Li

cs.IT ·submitted 2026-10-24 13:11 UTC · v2
theory

Abstract

In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings. In multiple unicast, where each source sends a message only to its prescribed destination, a central question is under what conditions fractional routing suffices to attain the transmission rates supported by network coding. We prove that, for any given collection of multiple-unicast demands in an undirected network, if the maximum flow between every pair of distinct destinations is at least the total demand rate, then the following are equivalent in feasibility: multiple-unicast coding, multiple-unicast fractional routing, and simultaneous fractional routing of all source rates to any fixed destination. Verifying this pairwise maximum-flow condition and, when it holds, deciding feasibility of the given multiple-unicast demands require at most as many maximum-flow computations as there are destinations. As a direct corollary, we prove the Langberg--Médard conjecture: if a directed network supports coded multicast of independent source messages at a common rate to every destination, then removing arc directions without changing capacities permits simultaneous fractional routing at that rate for all prescribed source--destination pairs.

Comment
14 pages, 3 figures. Revised exposition and proof presentation

Closest papers

Nearest neighbours by meaning across the whole index.

Cut Conditions, Integrality, and Obstructions for Directed Multiflows

cs.DM math.CO ·2026-11-09 ·Srinwanti Debgupta, Martin Skutella, Philipp Warode
theory similarity 0.69
Abstract

In contrast to the max-flow/min-cut theorem for single-commodity flows, the cut condition is necessary but not sufficient for the existence of directed multiflows, even with only two commodities. Poremba and Shepherd (IPCO 2023) conjecture that the cut condition is sufficient for all capacities and demands on a directed two-commodity topology if and only if it contains neither of two specific topologies as a relevant minor. We prove this conjecture. As a consequence, the fractional and integral flow-cut gaps of every directed two-commodity topology coincide and are either 1 or 2. We then investigate stronger necessary conditions for multiflow feasibility and their implications for integrality. We introduce a hierarchy of five conditions, ranging from the classical cut condition through conditions based on blocking edge sets and binary edge lengths to the linear programming dual characterization of fractional feasibility. The corresponding classes of sufficient topologies are strictly nested. We extend the Nagamochi-Ibaraki theorem: whenever one of the first four conditions is sufficient on a topology, integral capacities and demands satisfying that condition admit an integral multiflow, computable in polynomial time. Finally, we prove that recognizing topologies on which any of these four conditions is sufficient is coNP-complete, even for two commodities.

0.17

Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks

cs.IT ·2026-10-07 ·Xindan Zhang, Baochun Li, Zongpeng Li
theoryhighly cited similarity 0.68
Abstract · 17 pages

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.

0.65

Routing Optimality for Demand Graphs of Matching Number at Most Two

cs.IT ·2026-10-13 ·Xiaohong Cai, Yulin Chen
theory similarity 0.63
Abstract · This paper has been submitted to ITW 2027

We prove that network coding and fractional routing have the same capacity region in undirected networks whose demand graph has matching number at most two, that is, when no three demand edges have pairwise disjoint endpoints. The metric-packing reduction of Liu et al. reduces this problem to a distance-weighted communication inequality on the fixed graph $Γ_{3,3}$. We first prove two entropy inequalities for sessions between designated terminal pairs on $Γ_{3,3}$. We then extend this result to sessions with arbitrary endpoints to obtain the distance-weighted communication bound required by the reduction. The proof combines conditional entropy inequalities with two graph contractions and an information inequality for deterministic interaction. Combining this inequality with the existing reduction establishes routing optimality for this class of demand graphs.

0.33

Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting

cs.DS cs.CCcs.IT ·2026-10-14 ·Baochun Li, Zongpeng Li, Sirui Liu
code/data similarity 0.63
Abstract · 43 pages, 4 figures, 1 table. Lean 4 formalization and verification code: https://github.com/rtyu-1/coded-sorting-lean

In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, we give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is \[ O\!\left(\frac{N}{B}\left[1+ \frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon} \right]\right), \] where $\varepsilon=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $Θ\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.

0.57

Proof of the Langberg-Médard Multiple Unicast Conjecture

cs.IT math.CO ·2026-10-24 ·Kai Cai, Guangyue Han, Mengxi Yang, Wenan Zang
theory similarity 0.62
Abstract

Let $\mathcal{N}=(V,A,S, R)$ be a directed network, where $D=(V,A)$ is a digraph, $S=\{s_1,s_2,\ldots,s_k\}\subseteq V$ is a set of senders, and $R=\{r_1,r_2,\ldots,r_k\}\subseteq V$ is a set of receivers. We prove that if, for each $1\le j \le 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,\ldots,s_k)$-$(r_1,r_2,\ldots,r_k)$ multiflow of value $1$ for each pair $(s_i,r_i)$, $i=1,2,\ldots,k$. This establishes the multiple unicast conjecture proposed by Langberg and Médard in 2009.

0.33

The Multiple Unicast Conjecture is False

cs.IT cs.CCcs.DMcs.DS ·2026-10-07 ·Mark Braverman, Zhongtian He
theoryhighly cited similarity 0.62
Abstract

The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.

0.39

Linear Network Coding for Sum All-Reduce over Ring Networks

cs.IT ·2026-11-16 ·Yi Chen, Zhuoqi Tu, Shenghao Yang
publishedtheory similarity 0.59
Abstract

Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with $N\geq 3$ nodes and unit-capacity links, where each node holds a vector containing $K$ symbols, we prove that the number of time units $T$ required by any feasible linear code satisfies $T\ge\max\bigl\{K+N-2,\ \lceil\frac{2(N-1)}{N}K\rceil\bigr\}$, giving a rate $K/T$ of at most $N/(2(N-1))$. The bound is tight over every field. When $K\ge N$, an interleaved reduce--multicast code achieves the bound; when $K<N$ and $K$ divides $N$, a reduce--partial-multicast code does. When $K<N$ and $K$ does not divide $N$, no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.

0.40

A Family of Well-Behaved Multiflow Instances

cs.DS cs.DM ·2026-11-02 ·Joseph Poremba, F. Bruce Shepherd
published similarity 0.57
Abstract · To appear in SOSA 2027. 10 pages, 2 figures

We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances. We also show the family has an additive $6 d_{\max}$ error for converting a fractional flow into an unsplittable one.

0.35