Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

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 (or equivalently, the average degree).

Our starting point is a strong negative result: the slow-preprocessing version of DiskANN (analyzed in [IX23] for low-doubling metrics) can yield solutions whose sparsity is Ω(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(n 3 )-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 O(n • OPT) time and is therefore 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 O(n ω ) time. Finally, we complement our upper bounds with a query complexity lower bound, showing that any o(n)-approximation requires examining Ω(n 2 ) distances. This result shows that in the regime where OPT = O(n), our O(n • OPT)-time algorithm is essentially best possible.

Collectively, these results significantly advance our understanding of the computational complexity of computing sparse navigable graphs.