2025/07/18 by Khanna, Sanjeev, Padaki, Ashwin, Waingarten, Erik
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.14060
We initiate the study of approximation algorithms and computational barriers for constructing sparse α-navigable graphs [IX23, DGM+24], a core primitive underlying recent advances in graph-based nearest neighbor search. Given an n-point dataset P with an associated metric d and a parameter α≥ 1, the goal is to efficiently build the sparsest graph G=(P, E) that is α-navigable: for every distinct s, t ∈ P, there exists an edge (s, u) ∈ E with d(u, t) < d(s, t)/α. We consider two natural sparsity objectives: minimizing the maximum out-degree and minimizing the total size. We first show a strong negative result: the slow-preprocessing version of DiskANN (analyzed in [IX23] for low-doubling metrics) can yield solutions whose sparsity is \widetildeΩ(n) times larger than optimal, even on Euclidean instances. We then show a tight approximation-preserving equivalence between the Sparsest Navigable Graph problem and the classic Set Cover problem, obtaining an O(n3)-time (ln n + 1)-approximation algorithm, as well as establishing NP-hardness of achieving an o(ln n)-approximation. Building on this equivalence, we develop faster O(ln n)-approximation algorithms. The first runs in \widetildeO(n ⋅ OPT) time and is thus much faster when the optimal solution is sparse. The second, based on fast matrix multiplication, is a bicriteria algorithm that computes an O(ln n)-approximation to the sparsest 2α-navigable graph, running in \widetildeO(nω) time. Finally, we complement our upper bounds with a query complexity lower bound, showing that any o(n)-approximation requires examining Ω(n2) distances. This result shows that in the regime where OPT = \widetildeO(n), our \widetildeO(n ⋅ OPT)-time algorithm is essentially best possible.