# Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

arXiv: https://arxiv.org/abs/2507.14060 · HTML: https://mlsanity.com/paper/2507.14060/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2025.

## Built on by (most cited first, 2 of 2)

- [Graph-Based Nearest-Neighbor Search without the Spread](https://mlsanity.com/paper/2602.06633/) (2026)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)

## Abstract (arXiv)

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.