Hardness Results for Approximate Distance Labeling in Sparse Graphs

Abstract

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 2 November 2026

  Efficient Proper Agnostic Learning of Halfspaces

  Anindya De, Elchanan Mossel, Shivam Nadimpalli and 1 other
• arXiv preprint · 3 November 2026

  A Constant-Factor Approximation for Capacitated Facility Location with Outliers

  Rajni Dabas
• arXiv preprint · 2 November 2026

  Submodularity Is Barely Testable

  Diptaksho Palit and Yuichi Yoshida
• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 2 November 2026

  Generalized Flows over Time: Complexity, Structure and Algorithm

  Siyuan Chen, Shengminjie Chen, Suixiang Gao and 3 others

All new papers in Data Structures & Algorithms