Approximate distance labels in sparse graphs need large sizes
Hardness Results for Approximate Distance Labeling in Sparse Graphs
Data Structures and Algorithms
Summary
Graphs are structures made of points connected by lines, and sometimes we want to quickly estimate the distance between two points using labels. This paper shows that for certain kinds of sparse graphs, if you want a very accurate estimate of distances (close to exact), you still need fairly large labels. The authors prove this by building special graphs that make it hard to keep labels small while preserving accurate distances. Their work improves on previous results and also applies to related graph tools like hub labeling and shortcut sets.
What this means in practice
- •For network engineers: Recognize the inherent space costs of storing approximate distance information in large sparse networks, guiding design tradeoffs between accuracy and storage.
- •For database architects: Understand limits on label size for indexing sparse graph-based relational data to optimize approximate distance queries efficiently.
A theory result. No direct application yet.
Authors
Tsvi Kopelowitz, Ariel Korin, Liam Roditty
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.