CS Paper Radar

Routing Optimality for Demand Graphs of Matching Number at Most Two

Xiaohong Cai, Yulin Chen

cs.IT ·submitted 2026-10-13 08:05 UTC · v1
theory

Abstract

We prove that network coding and fractional routing have the same capacity region in undirected networks whose demand graph has matching number at most two, that is, when no three demand edges have pairwise disjoint endpoints. The metric-packing reduction of Liu et al. reduces this problem to a distance-weighted communication inequality on the fixed graph $Γ_{3,3}$. We first prove two entropy inequalities for sessions between designated terminal pairs on $Γ_{3,3}$. We then extend this result to sessions with arbitrary endpoints to obtain the distance-weighted communication bound required by the reduction. The proof combines conditional entropy inequalities with two graph contractions and an information inequality for deterministic interaction. Combining this inequality with the existing reduction establishes routing optimality for this class of demand graphs.

Comment
This paper has been submitted to ITW 2027

Closest papers

Nearest neighbours by meaning across the whole index.

When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability

cs.IT ·2026-10-24 ·Sirui Liu, Zongpeng Li, Baochun Li
theory similarity 0.63
Abstract · 14 pages, 3 figures. Revised exposition and proof presentation

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é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.

0.25

Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks

cs.IT ·2026-10-07 ·Xindan Zhang, Baochun Li, Zongpeng Li
theoryhighly cited similarity 0.60
Abstract · 17 pages

Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes but never settled in general. In this paper, we disprove it by constructing a finite connected simple undirected network with unit shared edge capacities, maximum degree three, and distinct leaf terminals, on which a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The construction turns a short completion-time code into a reversible circuit whose registers all carry independent messages, and a temporal metric on its wires yields the strict routing bound. The underlying integer-coefficient construction works over every finite field and every nontrivial finite abelian group; for deterministic fixed-schedule codes the common-rate supremum is one and the closure of the rate region is the unit cube. Amplifying the gap with a degree-preserving tensor construction and an even subdivision gives, for every $0<β<1$, an unbounded family of connected, simple, subcubic, bipartite networks with girth at least $n^β$ on which coding approaches rate one while routing is bounded by $K_β/(\log n)^c$, with one positive exponent $c$ independent of $β$. The finite counterexample and the family theorem are formalized in Lean.

0.64

Logarithmic Embeddings into Probabilistic Spanning Trees for Distances and Capacities

cs.DS ·2026-11-03 ·Mohammad Hajiaghayi
theory similarity 0.60
Abstract

We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$. This settles the logarithmic stretch conjecture of Alon, Karp, Peleg, and West, whose spanning-tree game appeared at the 1991 DIMACS Workshop on On-Line Algorithms and in SIAM Journal on Computing in 1995. A weighted form of the theorem also yields a distribution over spanning trees with capacities exactly equal to their fundamental graph cuts. Every tree dominates every graph cut, every cut is approximated within $O(\log n)$ in expectation, and the same capacity distribution defines an $O(\log n)$-competitive fractional oblivious routing. The distance and capacity distributions may differ. Diamond graphs give matching logarithmic lower bounds for stretch, congestion, and cut distortion. For rational input, both distributions are constructed deterministically in polynomial time and use at most $m$ trees, where $m$ is the number of graph edges. We prove an $Ω(m/ρ)$ support lower bound for congestion $ρ$; in particular, $(1-o(1))m$ trees can be necessary for near-unit congestion, even when the optimum tends to one. Thus linear dependence on $m$ is unavoidable in this regime. The weighted theorem combines a protected-geodesic petal decomposition with a pathwise entropy bound for locally selected centers. A local averaging inequality derandomizes the radii, and an adaptive rational packing procedure constructs the distributions.

0.54

A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

cs.DS cs.DMmath.CO ·2026-09-15 ·Michel X. Goemans, Yuchong Pan
theory similarity 0.58
Abstract

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

0.23

On Han- and Shearer-Type Information Inequalities: Equality Conditions and Combinatorial Applications

cs.IT ·2026-10-13 ·Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara, Vinod M. Prabhakaran
similarity 0.58
Abstract · 17 pages, 2 figures

Madiman and Tetali established strong and weak fractional inequalities that subsume classical entropy subset inequalities such as Han's inequality and Shearer's lemma. In this work, we derive a decomposition of the gap in the strong fractional inequality and use it to establish the necessary and sufficient conditions for equality in the strong form of Han's inequality. As a consequence, we characterize the equality conditions for a strong Loomis-Whitnet-type projection inequality of Balister and Bollobas (2012). Finally, we apply the weak fractional inequality to an extremal graph theory problem, recovering and extending results of Sason (2022) and Boucheron et al. (2013), whose approaches rely on Han's inequality.

0.37

Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting

cs.DS cs.CCcs.IT ·2026-10-14 ·Baochun Li, Zongpeng Li, Sirui Liu
code/data similarity 0.57
Abstract · 43 pages, 4 figures, 1 table. Lean 4 formalization and verification code: https://github.com/rtyu-1/coded-sorting-lean

In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, we give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is \[ O\!\left(\frac{N}{B}\left[1+ \frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon} \right]\right), \] where $\varepsilon=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $Θ\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.

0.57

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.57
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.57
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16