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 mathsfd 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 mathsfd(u, t) < mathsfd(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 widetildeOmega(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 Omega(n2) distances. This result shows that in the regime where OPT = widetildeO(n), our widetildeO(n · OPT)-time algorithm is essentially best possible.