The Li–Li multiple-unicast conjecture
Let $G = (V, E)$ be a finite connected undirected graph with capacities $c_e \ge 0$, and let $(s_i, t_i)$, $s_i \ne t_i$, be finitely many sessions. Session $i$ has its own independent message, initially known at $s_i$, which must be recovered exactly at $t_i$. Links are noiseless and network coding is causal: each transmitted symbol may be any function of the sender's initial messages and previously received symbols, and both directions of an edge share its capacity. The zero-error throughput region $\mathcal{C}_{\mathrm{NC}}$ is defined by arbitrary finite block protocols and asymptotic packet scaling: at scale $b$, message $i$ has $b r_i$ symbols and edge $e$ carries at most $b c_e$ symbols in total, with integer rounding and closure as $b \to \infty$; a common finite alphabet may be chosen for each protocol, and there is no constraint on completion time. With $\mathcal{P}_i$ the set of simple $s_i$–$t_i$ paths, the fractional routing region is $$\mathcal{C}_{\mathrm{MCF}} = \Bigl\{ r \ge 0 : \exists\, x_{i,P} \ge 0, \ \sum_{P \in \mathcal{P}_i} x_{i,P} \ge r_i \ \text{for all } i, \ \sum_i \sum_{P \in \mathcal{P}_i,\, e \in P} x_{i,P} \le c_e \ \text{for all } e \Bigr\}.$$ Routing is a special case of coding, so $\mathcal{C}_{\mathrm{MCF}} \subseteq \mathcal{C}_{\mathrm{NC}}$.
Li and Li showed that equality for all networks is equivalent to the statement that, in every network, every rate vector $r$ achievable with coding satisfies $\sum_e c_e \ge \sum_i d_i r_i$, where $d_i$ is the number of hops on a shortest $s_i$–$t_i$ path. Cut sufficiency theorems for fractional multicommodity flow, by Hu for two sessions and by Seymour for at most four terminal locations, give equality in those cases. Liu, Que, Li and Li proved it when the sessions use at most five terminal locations, and for networks with at most six coding nodes, a case first settled with computer-aided search by Yin, Li, Liu and Wang. Braverman, Garg and Schvartzman showed that a single network with a gap of $1 + \epsilon$ between the coding and the routing rate would yield networks $G'$ with gap $\log(|G'|)^c$ for some constant $c < 1$.
Problem. Is $\mathcal{C}_{\mathrm{NC}} = \mathcal{C}_{\mathrm{MCF}}$ for every such graph, capacity assignment and collection of sessions? Equivalently, can coding ever increase the throughput of independent unicast sessions over fractional routing? Coding need not be linear, and terminal locations may be shared across sessions.
Source: Li and Li (2004), §3.2, Proposition 3.1 (conjectured), and independently Harvey, Kleinberg and Lehman (2004); see Liu, Que, Li and Li (2026), Conjecture 1. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- CO, OC
- Keywords
- AIM Open Applied Problems, multicommodity flows, network coding
References
@inproceedings{li2004,
author = {Li, Zongpeng and Li, Baochun},
title = {Network coding: the case of multiple unicast sessions},
booktitle = {Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and Computing},
address = {Monticello, IL},
year = {2004},
url = {https://iqua.ece.utoronto.ca/papers/allerton04.pdf},
}
@techreport{harvey2004,
author = {Harvey, Nicholas J. A. and Kleinberg, Robert D. and Lehman, April Rasala},
title = {Comparing network coding with multicommodity flow for the $k$-pairs communication problem},
institution = {MIT Computer Science and Artificial Intelligence Laboratory},
number = {MIT-LCS-TR-964},
address = {Cambridge, MA},
year = {2004},
}
@misc{liu2026beyond,
author = {Liu, Sirui and Que, Li and Li, Zongpeng and Li, Baochun},
title = {On the multiple-unicast conjecture: beyond cut metrics},
year = {2026},
eprint = {2608.06070},
archivePrefix = {arXiv},
}
@article{hu1963,
author = {Hu, T. C.},
title = {Multi-commodity network flows},
journal = {Oper. Res.},
volume = {11},
number = {3},
year = {1963},
pages = {344--360},
doi = {10.1287/opre.11.3.344},
}
@article{seymour1980,
author = {Seymour, P. D.},
title = {Four-terminus flows},
journal = {Networks},
volume = {10},
number = {1},
year = {1980},
pages = {79--86},
doi = {10.1002/net.3230100108},
}
@article{yin2018,
author = {Yin, Xunrui and Li, Zongpeng and Liu, Yaduo and Wang, Xin},
title = {A reduction approach to the multiple-unicast conjecture in network coding},
journal = {IEEE Trans. Inform. Theory},
volume = {64},
number = {6},
year = {2018},
pages = {4530--4539},
doi = {10.1109/TIT.2017.2771738},
}
@inproceedings{braverman2017,
author = {Braverman, Mark and Garg, Sumegha and Schvartzman, Ariel},
title = {Coding in undirected graphs is either very helpful or not helpful at all},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {67},
year = {2017},
pages = {18:1--18:18},
doi = {10.4230/LIPIcs.ITCS.2017.18},
eprint = {1608.06545},
archivePrefix = {arXiv},
}
@misc{aim-li-li-multiple-unicast,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The Li–Li multiple-unicast conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/298-li-li-multiple-unicast.md},
note = {Entry 298 at commit a153f46, 2026-10-13},
}
Resolution claims
Network coding allows intermediate nodes to combine messages, whereas routing only forwards them. The Li-Li conjecture asserts that network coding and fractional routing have the same capacity region in undirected multiple-unicast networks. We give a counterexample to this conjecture and apply it to external-memory integer sorting. Since Aggarwal and Vitter posed the question in 1988, whether integer sorting can beat …
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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: arXiv:2610.10108v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00492, "The Li–Li multiple-unicast conjecture", clopen.solutions.