Nearly Optimal Sparse Navigable Graphs in General Metrics

Abstract

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $\alpha \ge 1$, a directed graph on $P$ is $\alpha$-navigable if, for every pair of distinct points $s,t\in P$, the source $s$ has an outgoing neighbor $p$ with $d(p,t)<d(s,t)/\alpha$. The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give $O(\log n)$-approximation algorithms and show that an $o(\log n)$ approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general $\alpha \ge 1$ was $\tilde{O}(\min \{n{\mathrm{OPT}}_{\alpha },n^{2.5}\})$, where ${\mathrm{OPT}}_{\alpha }$ is the minimum number of edges in an $\alpha$-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in $\tilde{O}(n^2)$ time and achieves an $O(\log n)$ approximation for every $\alpha \ge 1$. In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.

arXiv comment24 pages, 3 figures