Proof of the Langberg-Médard Multiple Unicast Conjecture
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33497
curl -X POST /api/v1/records/arxiv/2610.33497/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33497/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'