Li-Li Undirected Multiple-Unicast Network Coding Conjecture

Li-Li Undirected Multiple-Unicast Network Coding Conjecture

Definitions and mathematical statement

A multiple-unicast instance is a finite undirected network with edge capacities and designated source--sink pairs carrying independent messages. A rate tuple is achievable by network coding if finite-block, causal local encoders and decoders transmit those messages with zero error at asymptotic rates given by the tuple. Each undirected edge has one shared capacity budget for its two directions.

A routing solution divides each commodity among paths. If $f_{i,P}\ge0$ is the flow of commodity $i$ on path $P$, its constraints are \[ \sum_{i,P:e\in P}f_{i,P}\le c_e, \qquad \sum_Pf_{i,P}\ge R_i. \] The conjecture says that the closed achievable network-coding rate region equals the closed fractional multicommodity-routing region for every instance. The zero-error convention, independent messages, and shared undirected capacities are part of the selected formulation.

Formulation and concept references: [S1].

Short English statement

Can coding ever improve on fractional routing for independent unicast messages in an undirected network with shared edge capacities?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra was developed on 27 September 2026 by deriving communication cut inequalities, solving the tree case, and testing whether those inequalities characterize routing. These are standard partial arguments reconstructed explicitly, not new results. Messages remain independent, the error requirement is zero, and opposite directions share an edge's capacity. The first missing assertion is that a coding-achievable rate tuple satisfies every nonnegative-length metric inequality required by the fractional routing linear program. Cut inequalities alone do not imply this.

The primary source [S1] distinguishes cut sufficiency from its stronger metric approach, and treats specified network classes. Its five-terminal result, for example, does not make every cut-feasible tuple achievable. We do not infer the full conjecture from the subcases in that paper. Our cut calculation below applies to causal interaction, rather than assuming that the network is acyclic or that every edge carries only one commodity.

A cut bound accounting for both directions.

Fix a vertex cut $V=A\sqcup B$. Aggregate all nodes in $A$ into one communicating party and all nodes in $B$ into another; internal communication becomes free. Consider a finite block protocol with independent uniform messages. Let $X$ denote the messages originating in $A$ whose destinations lie in $B$, and $Y$ those originating in $B$ destined for $A$. Give each party all messages originating on its side. This only helps decoding and leaves $X$ independent of the initial data on side $B$, and conversely for $Y$.

Order the cross-cut transmissions in their causal order and write their transcript as $T$. Given $B$'s initial data, every symbol sent by $B$ is a deterministic function of that data and earlier transcript symbols. Consequently the chain rule gives \[ I(X;T\mid\text{initial data in }B) \le \sum_{\text{symbols sent }A\to B}\log_2|\text{symbol alphabet}|. \] Zero-error decoding makes the left side equal to $H(X)$: $X$ is independent of the conditioning data and is recovered from it and the transcript. Reversing the roles gives the corresponding lower bound for $H(Y)$ using only $B\to A$ transmissions. Local random seeds, if present, may be fixed for a finite zero-error protocol, or included among independent initial data; they do not supply the other side's independent messages.

Adding the two bounds and using the shared capacity budget yields, after normalization and passage to asymptotic rates, \begin{equation}\label{wsref-0-61-34-34-37-3a-63-75-74} \sum_{i:\,|\{s_i,t_i\}\cap A|=1}R_i \le \sum_{e\in\delta(A)}c_e. \end{equation} In particular, opposite-direction messages do not each receive the full capacity of the same undirected edge. The argument uses a fixed communication schedule, or one in which any information carried by timing and control is charged to communication, as in the ordinary finite-block capacity model.

An exact solution on trees.

Let the supply graph be a tree. Removing an edge $e$ gives a cut $A_e,B_e$. A commodity's unique source--sink path uses $e$ exactly when its endpoints are separated by that cut. Applying (a447:cut) therefore gives \[ \sum_{i:\,e\in P_i}R_i\le c_e \] for every edge, where $P_i$ is the unique path for commodity $i$. Assigning rate $R_i$ to $P_i$ is already a feasible fractional routing. Thus every coding-achievable tuple is routable on a tree. The reverse inclusion holds because forwarding is a coding protocol.

Rational feasible rates can be realized by time-sharing packets along the paths and pipelining over sufficiently long blocks. Startup delays occupy a bounded number of rounds relative to the block length. Real rate tuples follow by downward rational approximation and closure. If the network is disconnected, any positive-rate commodity crossing components is impossible by the zero-capacity cut; otherwise this argument applies separately to tree components. A source coinciding with its sink needs no transmission and can be omitted.

This proof obtains an entire rate region, not just equality of two maximum common throughputs. Its success comes from having one decisive cut for each edge, with no path-choice tradeoffs.

What positive combinations of cuts establish.

For a cut $A$, let $\delta_A(u,v)$ be one when the vertices lie on different sides and zero otherwise. Multiplying (a447:cut) by nonnegative coefficients and adding proves \[ \sum_iR_i d_1(s_i,t_i)\le \sum_{uv\in E}c_{uv}d_1(u,v), \qquad d_1=\sum_A\lambda_A\delta_A,\quad\lambda_A\ge0. \tag{447.1} \] Such metrics are precisely finite cut-cone, or finite $L^1$, metrics. The displayed implication itself only needs the given cut decomposition.

The routing dual asks for more. Assign arbitrary nonnegative lengths $\ell_e$ to supply edges and let $d_\ell$ be shortest-path distance. Every routing must satisfy \begin{equation}\label{wsref-0-61-34-34-37-3a-6d-65-74-72-69-63} \sum_iR_i d_\ell(s_i,t_i)\le\sum_e c_e\ell_e, \end{equation} because every unit of commodity $i$ uses a path of length at least its shortest-path distance. Conversely these inequalities for all $\ell\ge0$ characterize feasible fractional routing by finite-dimensional linear-programming duality, using the finite collection of simple paths. This is also the throughput/cost equivalence explained in [S1].

An exact cut decomposition matching terminal distances and costing no more than $\ell_e$ on each edge would make $447.1$ imply (a447:metric). The general existence of such a decomposition is false. This refutes that particular route, not the coding conjecture: stronger information inequalities could still prove the missing metric bounds.

A five-vertex countertest to cut sufficiency.

Take the supply graph $K_{2,3}$, with hubs $a,b$, leaves $u,v,w$, and unit capacity on each of its six edges. Request unit rate for each of the three leaf pairs and for the pair $(a,b)$. Every demand pair has supply distance two, so unit edge lengths give \[ \sum_iR_i d(s_i,t_i)=8>6=\sum_ec_e. \] The tuple cannot be fractionally routed.

Nevertheless all cuts satisfy (a447:cut). If a cut has one hub on each side, its capacity is three. If $r$ leaves lie with the first hub, its crossing demand is \[ r(3-r)+1\le3,\qquad 0\le r\le3. \] If both hubs are on the same side and $r$ leaves are on the other, capacity is $2r$ and crossing demand is $r(3-r)\le2r$. Complements cover the remaining descriptions. These calculations include the empty cut.

Thus cut feasibility plus independent messages cannot be treated as a routing construction. No coding protocol attaining this tuple has been supplied. Indeed the five-terminal conclusion reported in [S1] rules out a coding gain in this class; the tuple is useful here precisely because cut conditions by themselves miss the obstruction.

Why an XOR picture is insufficient.

If a bottleneck transmits $X\oplus Y$, neither independent bit is recovered without suitable side information. Establishing that side information consumes edges and must satisfy the same capacity accounting. In an undirected example, routes may also use edges in directions excluded by a directed drawing. Therefore a local reduction from two transmitted symbols to one is not a comparison with the optimum fractional routing of the complete undirected instance. The preceding cut proof allows interaction and side information but still forces the total communication across a tree edge to carry every separated message.

Verification and outcome.

The accompanying finite check enumerates every cut of the five-vertex instance and verifies both the cut inequalities and the length obstruction exactly. The tree proof checks arbitrary capacities and simultaneous, differently oriented commodities. Neither test searches the space of all nonlinear causal codes.

UNRESOLVED. Equality of the closed regions is proved here for trees. Positive combinations of cuts and their precise limitation are established. The first remaining gap is proving (a447:metric) for every coding-achievable tuple and every nonnegative length assignment, using genuinely stronger information about coding than the cut conditions alone.

Sources

• S1 Sirui Liu, Li Que, Zongpeng Li and Baochun Li, On the Multiple-Unicast Conjecture: Beyond Cut Metrics, arXiv:2608.06070v1 $2026$. https://arxiv.org/html/2608.06070v1. Formulation source.