Source-linked AI summary
Proof of the Langberg-M\'edard Multiple Unicast Conjecture
Kai Cai, Guangyue Han, Mengxi Yang, Wenan Zang
TL;DR
The paper addresses whether strong reachability suffices for unit-rate routing in the multiple unicast setting. It proves that it does for the Langberg–Médard conjecture, using cut bounds and functions defined from receiver distances. The result is a feasible multiflow of value 1 for every pair, while a weaker undirected reachability condition does not suffice.
Problem
The Langberg–Médard conjecture asks whether strong reachability guarantees a feasible multiflow with rate (1, 1, . . . , 1) for all sender–receiver pairs.
Source: §1 · p. 2Method
The proof derives cut inequalities from strong reachability and constructs functions from receiver distances, extending their prescribed receiver values as 1-Lipschitz functions.
Source: §1 · p. 3, §2 · p. 7, §4 · p. 10Results
A strongly reachable network admits a feasible multiflow of value 1 for each sender–receiver pair.
Source: §1 · p. 3Takeaways & Limitations
The Langberg–Médard multiple unicast conjecture holds for every k under strong reachability.
Source: §1 · p. 3Requiring only k undirected edge-disjoint paths to each receiver, one from each sender, is insufficient; a four-vertex path is a counterexample.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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\'edard in 2009.
1 Introduction
The paper proves the Langberg–Médard conjecture: strong reachability guarantees a unit-rate feasible multiflow for every sender–receiver pair in the underlying undirected network. This weaker conjecture differs from the broader network-coding conjecture, for which counterexamples had recently been constructed.
1 Introduction
- The broader Li and Li conjecture asserts that coding and feasible multiflow routing achieve the same rate vectors in undirected networks.Its validity would also answer an open problem in I/O complexity; recent counterexamples were constructed by Braverman and He [3] and Zhang, Li, and Li [20].Source: §1 · p. 2
- Strong reachability means that each receiver has k pairwise arc-disjoint directed paths to it, one from each sender.The underlying undirected network is assumed connected and has unit edge capacities.Source: §1 · p. 2
- The conjecture asks whether strong reachability guarantees a feasible multiflow with rate (1, 1, . . . , 1).Earlier work established lower rates and confirmed the conjecture for k = 3.Source: §1 · p. 2
- For any strongly reachable network N with k sender–receiver pairs, there is a feasible multiflow in N of value 1 for each pair.Source: §1 · p. 3
- Replacing strong reachability with k undirected edge-disjoint paths to each receiver does not suffice; a four-vertex path is a counterexample.The counterexample is G := s1r2r1s2.Source: §1 · p. 3
2 Cut Bounds and Required Functions
This section derives cut bounds from strong reachability and uses them to specify functions whose combined changes can be controlled by edge lengths. A three-coordinate transformation is introduced to meet the required change bound.
2 Cut Bounds and Required Functions
- Strong reachability supplies the outgoing-cut bound: a set excluding some receiver has at least as many outgoing arcs as senders it contains.For the proof, arc-disjoint paths to an excluded receiver yield distinct outgoing arcs for senders inside the set.Source: §2 · p. 4
- An undirected cut separating receivers with function values 0 and λ has size at least k, yielding a bound for functions taking values in [0, λ].The section obtains the corresponding function bounds by summing cut sizes across upper level sets.Source: §2 · pp. 4–5
- The cut bounds apply to nonnegative q vanishing at receivers and to bounded functions attaining 0 and λ at receivers.Upper level sets convert these vertex-function conditions into sums of directed or undirected cut sizes.Source: §2 · pp. 4–5
- The proof requires q and three functions u_m to have total absolute change bounded by the distance between any two vertices.This condition ensures that adding the cut inequalities does not count an edge length more than once.Source: §2 · pp. 5–6
- A transformation of three real values produces q and three u_m coordinates with the required combined change bound.Applying it to three 1-Lipschitz functions yields functions with q equal to zero at each receiver when prescribed receiver triples are permutations of (−h, h, h).Source: §2 · pp. 6–7
3 Prescribed Values at Receivers
This section prescribes receiver values for three functions using adjusted distances among receiver labels. The construction makes those values satisfy the bounds needed to extend the functions over all vertices.
3 Prescribed Values at Receivers
- The perimeter of three receiver labels bounds the distance-based term used to choose the constants and define the auxiliary function q.The section selects a triple with maximum perimeter and postpones q’s definition until the next section.Source: §3 · p. 8
- The three constants λ1, λ2, λ3 are chosen so that λm + λn = ρmn for each pair among the three selected receivers.The section imposes equality in the pairwise constraints required by the function conditions.Source: §3 · p. 8
- Adjusted receiver distances define triples B(i), which are transformed into prescribed triples g(i) with Q(g(i)) = 0.The transformation retains the H and U values of B(i), while adjusting its coordinates to make Q vanish.Source: §3 · pp. 8–9
- At receiver rm, the prescribed U-coordinate is λm and the other two U-coordinates are zero.The prescribed values also satisfy Um(g(i)) ≤ λm and vary by at most ρij across receiver labels.Source: §3 · p. 9
- Each prescribed coordinate gm is 1-Lipschitz across receiver labels, supporting its later extension to all vertices.The section establishes further inequalities among the prescribed coordinates for use in that extension.Source: §3 · pp. 9–10
4 Proof of the Main Result
The proof extends receiver-specific values to all vertices with distance-controlled functions, then combines them into q and three coordinates u1, u2, u3. These functions satisfy the required receiver conditions, a joint Lipschitz bound, and a distance bound for q.
4 Proof of the Main Result
- Each Fm extends receiver values gm(i) to all vertices by minimizing d(v,rj)+gm(j), and is 1-Lipschitz.The construction is motivated by McShane’s extension theorem [13].Source: §4 · p. 10
- The transformed functions q and um satisfy q(ri)=0, um(rm)=λm, um(rn)=0 for n≠m, and 0≤um(v)≤λm.The receiver values follow from F(ri)=g(i); the coordinate bounds are established for every vertex.Source: §4 · pp. 10–11
- The joint change in q and all three um coordinates between vertices is bounded by d(v,w), a stronger form of the required condition.The proof bounds this sum by the largest coordinate change in F, then by d(v,w).Source: §4 · p. 11
- For every vertex v and receiver ri, q(v)≥d(v,ri)−W, equivalently d(v,ri)≤q(v)+W.The proof first establishes the bound for all receiver labels j,h, then minimizes over them and over coordinate pairs.Source: §4 · p. 11
- The proof applies Lemma 2.3 after verifying that the constructed q and u1, u2, u3 meet its conditions.The available passage states this application as the step establishing Theorem 1.3.Source: §4 · pp. 10–11