CS Paper Radar

Hardness Results for Approximate Distance Labeling in Sparse Graphs

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

cs.DS ·submitted 2026-11-02 09:21 UTC · v1
top venuetheory

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.

Comment
To appear in SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate

cs.DS ·2026-10-01 ·Yaowei Long
top venue similarity 0.73
Abstract · 80 pages, to appear in FOCS 2026

We present new algorithms for the vertex-failure distance oracles and labeling schemes problems in undirected weighted graphs. A vertex-failure distance oracle is a data structure that, given two vertices $x$ and $y$ and a failed vertex set $F$ of size at most $f$, returns an approximation to the distance between $x$ and $y$ in $G \setminus F$. In the labeling-scheme setting, the data structure needs to be stored distributively as labels on the vertices, and each query $(x,y,F)$ must be answered by accessing only the labels of the vertices in $F \cup \{x,y\}$. For any $f\geq 1$ and $k \ge 1$, we obtain a vertex-failure distance oracle with $O(k^{6})$ approximation, space $\tilde{O}(f^{2}n^{1+1/k})$, query time $\tilde{O}(f^{5}n^{1/k})$, and polynomial preprocessing time. In particular, this is the first time-efficient oracle for multiple vertex failures with space close to linear, as well as the first constant-approximation oracle with polynomial space when tolerating $Ω(\log n)$ vertex failures. The previous results, due to [Duan-Gu-Ren, SODA'21], gave two alternatives: for any constant $c \ge 1$ and $ε>0$, one oracle has $\mathrm{poly}(\log n,f)$ approximation, space $n^{2+1/c}\mathrm{poly}(\log n,f)$, and query time $\mathrm{poly}(\log n,f^{c})$, while the other has $(1+ε)$ approximation, space $n^{2+1/c}(\log n/ε)^{O(f)}$, and query time $\mathrm{poly}(\log n,f^{c},1/ε)$. We also obtain a vertex-failure distance labeling scheme with $O(k^{6})$ approximation and label size $f^{3}n^{1/k}\log^{O(k)} n$. This is the first nontrivial distance labeling scheme for vertex failures. Our techniques build on recent tools related to length-constrained vertex expanders and also introduce a new expander-based shortcut sparsification. The latter also leads to a deterministic vertex-failure connectivity labeling scheme of size $\tilde{O}(f^{2})$.

0.32

On Multi-label radio Labelings of Graphs

cs.DM math.CO ·2026-10-19 ·Olivier Togni
theory similarity 0.72
Abstract · 14 pages

We propose and study a multi-labeling generalization of the $k$-radio labeling problem of graphs: given a graph $G$ and integers $k$ and $m$, assign to each vertex of $G$ a set of $m$ integer labels such that distinct labels assigned to a vertex differ by at least $k+1$, and the labels of any two distinct vertices $x$ and $y$ pairwise differ by at least $k+1-d(x,y)$, with $d(x,y)$ being the distance between vertices $x$ and $y$. We prove general bounds on the minimum span of such a labeling and more refined results for the case $k=1$. For paths and cycles, we derive sharp bounds on the minimum span when $k$ is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.

0.16

A Tight Space Lower Bound for Pivot-Based Distance Oracles

cs.DS ·2026-10-21 ·Avi Kadria, Liam Roditty
theory similarity 0.71
Abstract

An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch $k=2\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$. This trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $Ω(m)$ space. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u \to p_v \to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. We prove that every \emph{pivot-based} $1$-hop ADO with \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for graphs with constant degree. This matches the best known ADOs with $\tilde{O}(1)$ query time, at every known stretch, up to polylogarithmic factors. We also extend our lower bound to pivot-based ADOs with any constant number $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets and improved lower bounds for general $β$-hop hopsets.

0.24

Õptimal Facial Distance Labeling in Planar Graph

cs.DS ·2026-11-08 ·Noy Rotbart, Oren Weimann
theoryhot direction similarity 0.70
Abstract

We show how to assign labels of size $\tilde O(n^{1/3})$ to the vertices of a face $F$ in an $n$-vertex unweighted undirected planar graph $G$ s.t one can deduce the distance between any two vertices of $F$ given their labels alone. This matches (up to log factors) the $Ω(n^{1/3})$ lower bound of Gavoille, Peleg, Pérennes, Raz from 2004. Prior to our work, the smallest labels were of size $O(n^{1/2})$.

0.28

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

cs.DS ·2026-09-08 ·Yaowei Long, Seth Pettie, Thatchaphol Saranurak
similarity 0.70
Abstract · 11 pages

For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

0.36

Nearly Optimal Sparse Navigable Graphs in General Metrics

cs.DS ·2026-10-29 ·Hongyi Chen, Tianyi Zhang
similarity 0.69
Abstract · 24 pages, 3 figures

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge1$, a directed graph on $P$ is $α$-navigable if, for every pair of distinct points $s,t\in P$, the source $s$ has an outgoing neighbor $p$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give $O(\log n)$-approximation algorithms and show that an $o(\log n)$ approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general $α\ge1$ was $\widetilde O(\min\{n\operatorname{OPT}_α,n^{2.5}\})$, where $\operatorname{OPT}_α$ is the minimum number of edges in an $α$-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in $\widetilde O(n^2)$ time and achieves an $O(\log n)$ approximation for every $α\ge1$. In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.

0.20

On graphically local versions of metric embeddings

cs.CG math.CO ·2026-08-16 ·Vishesh Jain, Duan Tu
theory similarity 0.68
Abstract

We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a small distortion, only a subset of the pairwise distances specified by a bounded degree graph $G$. We provide a general reduction showing that, in many cases, this is no easier than embedding the points while approximately preserving all pairwise distances. As an illustration of our general reduction, we show that there exists a Euclidean metric space $X$ on $n$ points along with a graph $G = (X,E)$ of maximum degree $3$ such that any embedding of $X$ into $\ell_2^m$ which only preserves distances specified by $E$ up to a relative error of $(1+\varepsilon)$ must satisfy $m = Ω(\varepsilon^{-2}\log n)$. Our lower bound matches the upper bound on the dimension coming from the Johnson-Lindenstrauss lemma for approximately preserving all pairwise distances; previously, such a lower bound was known only for the class of noncontracting embeddings [Schechtman-Shraibman, Discrete & Computational Geometry, 2009]. Moreover, the condition that the maximum degree of the graph is $3$ is best possible: for graphs $G$ of maximum degree $2$ (or more generally, treewidth at most $2$), any metric space embeds $G$-isometrically into any two-dimensional normed space.

0.04

$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds

cs.DS cs.DM ·2026-09-30 ·Shiri Chechik, Gur Lifshitz
top venue similarity 0.68
Abstract · A preliminary version appeared in SODA 2026

For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all distances $d\le k$. Specifically, we construct a spanner $H\subseteq G$ with $O(n^{1+1/k}+(k+d\log d)n)$ edges, ensuring that any pair at original distance at most $d$ satisfies $\mathrm{dist}_H(u,v)\le 2k+O(d\log d)$. Equivalently, the multiplicative stretch for pairs at distance $d$ is $2k/d+O(\log d)$. In particular, setting $d=k/\log k$ yields an $(O(\log k),O(k))$-spanner with $O(n^{1+1/k}+kn)$ edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed $\varepsilon>0$ and sufficiently large $k$, an $(O(k^\varepsilon),O_\varepsilon(k))$-spanner with $O_{\varepsilon,k}(n^{1+1/k})$ edges. Our result improves the multiplicative stretch from $O(k^\varepsilon)$ to $O(\log k)$ while keeping the additive term linear in $k$, bringing us closer to the goal of $(O(1),O(k))$-spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch $O_\varepsilon(k/d)$ for distances $d\le k^{1-\varepsilon}$, for every fixed $\varepsilon>0$, and an explicit bound of $7k/d$ for $d\le\sqrt{k}/2$. We achieve $2k/d+O(\log d)$, which is $(2+o(1))k/d$ whenever $d=o(k/\log k)$. Our second result is an improved construction of $k$-hybrid spanners, which guarantee stretch $2k-1$ for adjacent pairs and $k$ for non-adjacent pairs. Parter's original construction uses $O(k^2 n^{1+1/k})$ edges; we achieve the same guarantees with $O(n^{1+1/k}+kn)$ edges, removing the $k^2$ factor from the $n^{1+1/k}$ term. For every fixed $k$, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.

0.49