Source-linked AI summary
When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability
Sirui Liu, Zongpeng Li, Baochun Li
TL;DR
The paper asks when fractional routing can attain network-coding rates in multiple unicast, where each source sends only to its prescribed destination. It proves that a pairwise maximum-flow condition makes coding, prescribed-demand routing, and routing to one fixed destination equivalent in feasibility. This equivalence also proves the Langberg–Médard conjecture for the stated directed-to-undirected setting.
Problem
The central question is when fractional routing suffices to attain transmission rates supported by network coding for multiple-unicast demands.
Source: §I · p. 1Method
The paper proves a feasibility equivalence under a condition requiring maximum flow between every pair of distinct destinations to meet or exceed total demand.
Source: §I · pp. 1–2Results
Under that condition, multiple-unicast coding, prescribed-demand fractional routing, and simultaneous routing of all source rates to one fixed destination are equivalent in feasibility.
Source: §I · pp. 1–2Takeaways & Limitations
The equivalence proves that coded multiple multicast in a directed network yields same-rate fractional routing of prescribed pairs in the underlying undirected network.
Source: B. The Langberg–Médard Conjecture · p. 5
Abstract
from arXiv · showhide
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\'{e}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.
I. INTRODUCTION
The paper identifies when fractional routing matches network coding in undirected multiple-unicast networks: a pairwise maximum-flow condition on destinations makes both equivalent to routing all source rates to one fixed destination. This equivalence also yields the Langberg–Médard conjecture and a reduction strategy for proving routing feasibility.
B. The Langberg–Médard Conjecture
- The Langberg–Médard conjecture asks whether coded multiple multicast in a directed network guarantees same-rate routing of prescribed pairs after directions are removed; earlier general guarantees included 1/3 and 8/9.The paper proves the conjecture as a consequence of its feasibility equivalence.Source: §I · p. 1, B. The Langberg–Médard Conjecture · p. 3
I. INTRODUCTION
- When every pair of distinct destinations has maximum flow at least the total demand rate, multiple-unicast coding, prescribed-demand fractional routing, and single-sink routing are equivalent in feasibility.The fixed single-sink destination may be chosen in advance; at most |T| maximum-flow computations suffice to check the condition and decide feasibility when it holds.Source: §I · pp. 1–2
A. The Multiple-Unicast Conjecture
- Counterexamples by Zhang, Li, and Li [3] and Braverman and He [4] show that coding can outperform fractional routing in general undirected multiple-unicast networks.The paper's pairwise destination-flow condition identifies a scope in which their feasibility is equivalent.Source: §I · p. 1, A. The Multiple-Unicast Conjecture · p. 2
C. Network Reduction
- The proof reduces general networks by eliminating internal nodes and source-to-source edges using Király's result, then splitting off sources with Mader's theorem while preserving destination connectivities.The reduction controls cost and preserves single-sink routability and the pairwise destination maximum-flow condition.Source: C. Network Reduction · p. 3
III. NOTATION AND PRELIMINARIES
The preliminaries define the undirected network and fractional-routing model, then characterize routing feasibility through a comparison of capacity cost and rate-weighted shortest-path cost.
A. Network Model
- The underlying undirected multigraph replaces each directed arc with an edge of equal capacity, shared between its two directions; opposite arcs become parallel edges.The network model allows finite nonnegative capacities and directed cycles in the original multigraph.Source: A. Network Model · p. 3
B. Fractional Routing
- Fractional routing assigns nonnegative path flows that deliver each demand rate while keeping total traffic on every edge, across both directions, within its capacity.A source may split its traffic among multiple paths; zero-rate demands may be discarded before distances are formed.Source: B. Fractional Routing · p. 3
- Routing is feasible exactly when, for every nonnegative edge-length assignment, network capacity cost is at least the demands' rate-weighted shortest-path cost.The characterization follows from linear programming duality for multicommodity flow.Source: B. Fractional Routing · p. 3
- A pseudometric is symmetric, nonnegative, zero on identical points, and satisfies the triangle inequality, though distinct points may have distance zero.For capacities x_uv priced by distances d(u,v), x · d is their total cost.Source: B. Fractional Routing · p. 4
C. Network Coding
The paper defines the coding tasks and relates multiple-multicast feasibility to destination-wise flows. Its main theorem equates multiple-unicast coding, prescribed fractional routing, and routing all sources to one fixed destination under the theorem’s pairwise maximum-flow condition.
C. Network Coding
- Multiple-multicast coding can be checked separately for each destination through a feasible flow simultaneously sending all source rates there.The augmented single-source multicast flow has total rate kρ; removing its super-source arcs gives the destination-wise flows.Source: C. Network Coding · p. 4
- With unit arc capacities and common rate one, multiple-multicast coding is equivalent to strong reachability: each destination has k arc-disjoint paths from the sources.Source: C. Network Coding · pp. 4–5
IV. MAIN RESULTS
- The paper’s main results include both the coding-routing feasibility equivalence and the resulting resolution of the Langberg–Médard conjecture.Source: §IV · p. 5
A. Coding and Routing Feasibility
- Under the pairwise maximum-flow condition, multiple-unicast coding, prescribed fractional routing, and routing all source rates to one fixed destination are equivalent in feasibility.The fixed destination may be chosen arbitrarily from T.Source: A. Coding and Routing Feasibility · p. 5
- At most |T| maximum-flow computations suffice to check the condition and, when it holds, decide coding or fractional-routing feasibility.Source: A. Coding and Routing Feasibility · p. 5
B. The Langberg–Médard Conjecture
The paper derives the Langberg–Médard conclusion from a routing theorem for undirected networks. Its proof reduces general networks to a source-adjacent-to-destinations setting and establishes a routing-cost inequality there.
B. The Langberg–Médard Conjecture
- If every destination separately admits directed fractional flows carrying all prescribed source rates to it, replacing arcs by same-capacity undirected edges permits simultaneous fractional routing of the prescribed demands.Source: B. The Langberg–Médard Conjecture · p. 5
- For equal source rates, the theorem and the multiple-multicast flow characterization yield the Langberg–Médard conjecture.The corollary also covers strongly reachable unit-capacity networks at unit rate for paired demands.Source: B. The Langberg–Médard Conjecture · p. 5
C. Proof Overview
- The proof’s core is to establish the fractional-routing dual inequality from single-sink routability and the pairwise maximum-flow condition.Source: C. Proof Overview · p. 5
- Király’s cut-covering theorem reduces general networks for fixed rational shortest-path pseudometrics, while Mader splitting-off supports the simplified proof; rational approximation completes the argument.Source: C. Proof Overview · pp. 5–6
V. MULTIPLE-UNICAST ROUTING WHEN SOURCES ARE ADJACENT ONLY TO DESTINATIONS
- For a fixed destination cut, each source can be placed independently on the side giving its smaller cut contribution.The two contributions are A_i(J) and r_i − A_i(J).Source: Figure 1 · p. 6, §V · p. 6
- When sources are adjacent only to destinations, the cut condition implies simultaneous routing of the A_iu rates from destination nodes u to their prescribed destinations t_i.Source: §V · p. 6
- Splitting off source edges preserves destination connectivity, allowing auxiliary-edge costs to cancel and yielding the cost inequality for the original destination network.Source: §V · p. 6
A. Source Elimination Preserving Connectivity
The proof eliminates sources by splitting paired incident edges, producing an auxiliary network on destinations while preserving the required connectivity. Pairing weights record the splits and support the capacity and cut conditions used in later arguments.
A. Source Elimination Preserving Connectivity
- Scaling rational capacities by 2N turns them into unit edges, after which each source’s incident edges can be completely split into pairs.A pair s_i u, s_i v becomes an edge uv when u and v differ, and is deleted when they coincide.Source: A. Source Elimination Preserving… · pp. 6–7
- The pairing weights H_i record how often each unordered destination pair is formed and count each endpoint occurrence, including twice for a diagonal pair.Their sums encode the source’s total incident capacity and its capacity to each destination.Source: A. Source Elimination Preserving… · pp. 6–7
- Mader’s splitting-off theorem permits complete source elimination while preserving pairwise local edge connectivity among the remaining vertices.Even degrees persist after each split, so the multigraph has no incident bridge and the theorem’s hypotheses continue to hold.Source: A. Source Elimination Preserving… · p. 7
- After splitting, the destination network has edge capacities combining original destination edges with split pairs, and every distinct destination pair retains minimum-cut capacity at least R.Diagonal pairing weights affect endpoint counts but contribute neither edges nor cut capacity.Source: A. Source Elimination Preserving… · p. 7
B. From Connectivity to a Routing-Cost Lower Bound
A destination network whose nontrivial cuts have capacity at least R yields a lower bound on its cost under any pseudometric. The proof uses disjoint metric balls and cut counting to bound the sum of pairwise distances for every destination triple.
B. From Connectivity to a Routing-Cost Lower Bound
- Each source-splitting pair and its target form a destination triple whose pairwise distance sum matches the target-distance and auxiliary-edge costs.This identity connects source elimination to the three-point metric bound.Source: B. From Connectivity to a Routing-Cost… · p. 7
- Three disjoint open balls are chosen so each pair of radii sums to the distance between their centers, making each positive-radius ball define a nontrivial cut.Integrating the cut capacities across the radii bounds K · d below by R times the triple’s perimeter.Source: B. From Connectivity to a Routing-Cost… · p. 7
- The three-point quantity π_d(a,b,c) is the sum of the three pairwise distances, and maximizing it gives M(d).The resulting integral bound is K · d ≥ λM(d).Source: B. From Connectivity to a Routing-Cost… · pp. 7, 9
- For any pseudometric d, a destination network with every nontrivial cut of capacity at least λ has cost K · d at least λ times the maximum three-point perimeter.The perimeter is the sum of the three pairwise distances, maximized over triples that may repeat destinations.Source: B. From Connectivity to a Routing-Cost… · p. 7
- Expanding the sets J_p,z turns edge crossings into intervals of length |f_p(x) − f_p(y)|, so capacity-weighted cut counts yield the metric-cost integral.As z decreases, the ball radius α_p − z grows; the sets for distinct centers are disjoint.Source: B. From Connectivity to a Routing-Cost… · p. 8, Figure 3 · p. 8
C. Routing Feasibility by Cost Cancellation
The proof compares the target-demand distance cost plus auxiliary-edge cost with a lower bound from the destination network, then cancels the shared auxiliary cost. The resulting inequality gives fractional routing, with rational capacities extended to real capacities by approximation.
C. Routing Feasibility by Cost Cancellation
- Adding auxiliary-edge cost to both sides of the source-pair distance identity makes that cost cancel against the destination-network lower bound.The comparison proves the required routing-cost inequality for rational capacities.Source: C. Routing Feasibility by Cost… · p. 9
- Approximating real capacities by rational sequences and taking their limit extends the routing-cost inequality to real capacities.The proof also treats R = 0 separately; for R > 0, the destination network is connected.Source: C. Routing Feasibility by Cost… · p. 9
- The resulting inequality implies that demands u → t_i of rates A_iu admit simultaneous fractional routing in the destination network (T, B).This follows by applying Lemma 1 to the cost inequality.Source: C. Routing Feasibility by Cost… · p. 9
VI. ELIMINATING INTERNAL NODES AND EDGES BETWEEN SOURCES
The proof removes internal nodes and source-to-source edges by finding a minimum-cost capacity assignment that still satisfies the cut lower bounds. Király’s parsimony theorem supplies an optimal assignment tight at nodes with the relevant subadditivity property.
VI. ELIMINATING INTERNAL NODES AND EDGES BETWEEN SOURCES
- The proof assigns capacities on the complete graph while preserving cut lower bounds and keeping total distance-weighted cost no greater than the original network’s.The chosen capacities vanish on edges incident to internal nodes and between sources, while each source retains incident capacity r_i.Source: §VI · p. 9
A. The Parsimonious Cut-Covering Theorem
- Király’s parsimony theorem guarantees a minimum-cost cut-covering solution tight at every node subadditive for the cut requirement h.For internal nodes h({v}) = 0, while for sources h({s_i}) = r_i.Source: A. The Parsimonious Cut-Covering Theorem · pp. 9–10
- The cut-covering theorem applies to skew-supermodular bounds and rational pseudometric costs, with the rational formulation obtained by scaling to integers.The integer-case guarantee is rescaled to give an optimal rational solution satisfying the singleton equalities.Source: A. The Parsimonious Cut-Covering Theorem · p. 10
B. Constructing and Verifying the Cut Function
The pairwise destination-flow condition and single-sink routability can each be expressed as cut-capacity lower bounds; together they define a cut function with the properties needed for the proof.
B. Constructing and Verifying the Cut Function
- Every cut separating the destination set must have capacity at least the total demand rate R.This is equivalent to the condition that maximum flow between every pair of distinct destinations is at least R.Source: B. Constructing and Verifying the Cut… · p. 10
- Single-sink routability to fixed destination t0 is equivalent to cut bounds using the source rate w(U) for sets excluding t0 and R − w(U) for sets containing t0.The proof obtains these bounds by adding a super-source and applying max-flow min-cut.Source: B. Constructing and Verifying the Cut… · p. 10
- Combining the two conditions yields cut bounds c(δ_G U) ≥ F(U), where F is skew-supermodular and every node is subadditive for F.These properties are the stated prerequisites used in the subsequent capacity transformation.Source: B. Constructing and Verifying the Cut… · p. 10
C. Capacity Transformation Without Cost Increase
Under the combined cut bounds, a rational pseudometric admits a capacity transformation that does not increase total capacity cost, reducing the analysis to source–destination and destination–destination connections.
C. Capacity Transformation Without Cost Increase
- When c(δ_G U) ≥ F(U) for every U, the capacity transformation supplies a nonnegative rational matrix A for any rational pseudometric d.The resulting capacities satisfy the stated source-rate row sums and cut constraints.Source: C. Capacity Transformation Without… · p. 11
- The constructed capacity solution has positive capacity only between sources and destinations or between distinct destinations, with each source’s incident capacity summing to its rate.Internal nodes and edges between sources are eliminated because their capacities are zero.Source: C. Capacity Transformation Without… · p. 11
- The transformation preserves the relevant cost bound while producing capacities that satisfy the destination-set cut constraints.The proof uses the restriction of d to T when evaluating destination-to-destination costs.Source: C. Capacity Transformation Without… · p. 11
D. Completing the Proof of Theorem 1
Theorem 1 follows by proving the three feasibility implications: routing is coding, coding implies single-sink routability under the pairwise flow condition, and single-sink routability plus that condition implies prescribed-demand routing.
D. Completing the Proof of Theorem 1
- Fractional routing implies coding because forwarding messages along fractional routes is a coding solution.The proof extends this implication to real path-flow rates by limits of finite-block routing schemes.Source: D. Completing the Proof of Theorem 1 · p. 12
- Coding implies single-sink routability: cut-set bounds handle sets containing no destinations, while the pairwise flow condition handles sets containing a destination.For the latter sets, the cut separates that destination from t0 and has capacity at least R, hence at least the source rate within the set.Source: D. Completing the Proof of Theorem 1 · p. 12
- Single-sink routability and the pairwise flow condition imply prescribed-demand routing by applying the capacity transformation and the routing-cost theorem.The proof first treats rational rates and lengths, then extends to real values by approximation and continuity of shortest-path distances.Source: D. Completing the Proof of Theorem 1 · p. 12
VII. THE LANGBERG–MÉDARD CONJECTURE
The paper derives the Langberg–Médard result by showing that the directed multicast hypothesis supplies the conditions for Theorem 1 on the underlying undirected network. Its conclusion also identifies a destination-connectivity boundary for coding–routing feasibility equivalence.
VII. THE LANGBERG–MÉDARD CONJECTURE
- The directed multicast flows imply single-sink routability and a pairwise destination max-flow of at least R in the underlying undirected network, so Theorem 1 gives simultaneous fractional routing.For a destination-separating cut, outgoing and incoming directed capacities bound traffic from sources on each side; the arc sets are disjoint.Source: §VII · p. 12
- Coded multiple-multicast at common rate ρ yields simultaneous fractional routing at rate ρ for every prescribed source–destination pair after arc directions are removed.The proof applies Theorem 2 to the destination set and equal source rates.Source: §VII · p. 12
VIII. CONCLUSION
- Under the pairwise destination-flow condition, coding and fractional routing have the same feasible rate vectors, and feasibility checks require at most as many max-flow computations as destinations.The equivalence also includes simultaneous routing of all source rates to any one fixed destination.Source: §VIII · p. 13
- The proof’s reduction to an auxiliary destination-only network may apply to other multicommodity-flow and network information-flow problems.The paper identifies the exact coding–routing gap under weaker destination connectivity as future research.Source: §VIII · p. 13
APPENDIX A STATEMENTS OF THE RESULTS USED
The appendix states two existing results used in the proofs: Mader’s splitting-off theorem and Király’s parsimonious cut-covering theorem.
A. Mader’s Splitting-Off Theorem
- Mader’s theorem preserves local edge connectivity among all pairs other than an even-degree vertex with no incident bridge while its incident edges are paired and split off.After deleting the resulting isolated vertex, λH′(u, v) = λH(u, v) for distinct u, v other than x.Source: A. Mader’s Splitting-Off Theorem · p. 13
- Lemma 2 applies the result after multiplying rational capacities by 2N and replacing them with parallel unit edges; every vertex then has even degree, so every cut has even size and there is no bridge.Source: A. Mader’s Splitting-Off Theorem · p. 13
B. Király’s Parsimonious Cut-Covering Theorem
- Király’s theorem uses two skew-supermodular functions and a symmetric, zero-at-empty cut bound h(U) = max{p1(U), p2(U), 0}, with a nonnegative integer-valued pseudometric d.When the feasible set is nonempty, an optimal solution can satisfy the stated condition simultaneously at every vertex subadditive for h.Source: B. Király’s Parsimonious Cut-Covering… · p. 13
- Lemma 4 extends Király’s integer-data result to rational cut bounds and rational pseudometrics by clearing denominators and rescaling capacities.The stated theorem combines Claim 1.1 and Theorem 2.1 of Király.Source: B. Király’s Parsimonious Cut-Covering… · p. 13