Hardness Results for Approximate Distance Labeling in Sparse Graphs

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+ε, where ε>0 is fixed. We prove lower bounds for this (1+ε)-stretch regime through a density/stretch tradeoff. For every constant integer k≥ 1, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with m=O(n1+1/k) edges requires maximum label size at least SumIndex(n)/2Oₖ(√log n) for infinitely many values of n. Thus, under the conjecture that SumIndex(n)=n¹⁻ᵒ⁽¹⁾, the maximum label size must be n¹⁻ᵒ⁽¹⁾. 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.