Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

We initiate the study of approximation algorithms and computational barriers for constructing sparse \(\alpha\)-navigable graphs, an important principle underlying recent advances in graph-based nearest neighbor search. Given an \(n\)-point dataset \(P\) with an associated metric \(d\) and a parameter \(\alpha \ge 1\), the goal is to efficiently build the sparsest graph \(G = (P, E)\) that is \(\alpha\)-navigable: for every distinct \(s, t \in P\), there exists an edge \((s, u) \in E\) with \(d(u, t) \lt \texttt{d}(s, t)/\alpha\). We consider two natural sparsity objectives: minimizing the maximum out-degree and minimizing the total size (or equivalently, the average degree).