WorksComputer Science
Nearly Optimal Sparse Navigable Graphs in General Metrics
Abstract
We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an -point metric and a parameter , a directed graph on is -navigable if, for every pair of distinct points , the source has an outgoing neighbor with . The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give -approximation algorithms and show that an approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general was , where is the minimum number of edges in an -navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in time and achieves an approximation for every . In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.
Introduction
Nearest neighbor search aims to preprocess a dataset so that, given a query point, an exact or approximate nearest neighbor can be found efficiently. Graph-based methods approach this problem by building a graph on the dataset points and answering queries by following edges toward points closer to the query. This approach underlies practical methods such as HNSW [20], NSG [9], and DiskANN [SDK⁺19]. The graph must provide edges that allow a search to make progress, while keeping neighborhoods small enough to inspect efficiently.
Recent work has improved graph construction and search guarantees [DGM⁺24, LT25, GKSW25, AJDG⁺25]. Complementary studies examine the efficiency, accuracy, and scalability of graph-based search in practical settings [ZPL⁺26, AEP25, SSKS21, GKL⁺25, AM26].
A central theoretical abstraction for this approach is navigability [17].
Definition 1.1 (-navigability). Let be an -point metric and let . A directed graph with no self-loops is -navigable if, for every pair of distinct points , some edge satisfies
We call the source, the target, and an intermediate point; may be itself. For , the condition guarantees that a greedy search can always move closer to a target in until it reaches that target. Larger values of require more progress from each step. The analysis of Indyk and Xu [17] implies that, for every , one can choose so that greedy search on an -navigable graph finds a -approximate nearest neighbor (ANN) of any query point in search steps, where is the aspect ratio of , defined as the ratio of the largest pairwise distance to the smallest nonzero pairwise distance. Logarithmic factors in asymptotic bounds are understood to be at least 1.
This motivates the following problem: given and , build an -navigable graph with as few edges as possible. Let denote the minimum number of edges in such a graph. We seek an efficient algorithm whose output size is within a small multiplicative factor of for every input metric.
Previous work. Khanna, Padaki, and Waingarten [18] and, independently, Conway et al. [CDFC⁺26] initiated the study of approximation algorithms for this problem. Both formulate the problem as a Set Cover instance for each source. For a fixed source , each possible outgoing edge corresponds to the set of targets for which satisfies the navigation requirement. Choosing outgoing neighbors for is therefore equivalent to selecting as few such sets as possible to cover . Applying greedy Set Cover to all instances yields an approximation in time. Both works also show that obtaining an approximation is NP-hard in general. Thus the remaining algorithmic question is how quickly we can obtain the logarithmic approximation.
For general , Khanna, Padaki, and Waingarten [18] give an -time algorithm, and Conway et al. [CDFC⁺26] obtain time. Here suppresses factors polylogarithmic in . For , Conway et al. further obtain an -time construction, assuming that the distances from each point to the other points are pairwise distinct. Their work leaves near-quadratic construction for general open. Khanna, Padaki, and Waingarten also use matrix multiplication to obtain a bicriteria guarantee: the output is -navigable, but its size is compared with the optimum under a stronger navigation requirement. These results leave the following question:
Can we obtain an approximation to the sparsest -navigable graph in near-quadratic time for every ?
Main Result
We give an affirmative answer to this question. Even for , our result removes the distinct-distance assumption in the near-quadratic construction of Conway et al. [5]. Our contribution is a simple, unified algorithm to solve the coupled Set Cover instances arising from navigable graph construction in near-quadratic time.
Theorem 1.2. Let be an -point metric space. For every , there is a randomized algorithm that constructs an -navigable graph on . With high probability, the algorithm runs in time and returns a graph with at most edges, where is the minimum number of edges in an -navigable graph on .
The approximation also holds separately for each source’s outdegree, and is optimal up to constants in general. Moreover, even for , any randomized algorithm achieving an approximation with constant success probability requires distance queries [18 Theorem 5]. Thus our running time matches this query lower bound up to polylogarithmic factors.
For any , a more careful choice of parameters and standard refinements of the analysis give a approximation in time with high probability. We present the simpler version for readability and briefly outline this refinement at the end of § 2.
Related Work
Bicriteria approximation. For , let denote the minimum number of edges in a -navigable graph on the same metric. An -bicriteria approximation constructs an -navigable graph and compares its edge count with . Let denote the matrix multiplication exponent.
Khanna, Padaki, and Waingarten [18] introduced this bicriteria formulation. For every and , their algorithm uses matrix multiplication to construct an -navigable graph with edges in time. In the notation above, this is an -bicriteria approximation.
In a follow-up work, Chen and Zhang [6] reduce the running time to for constant . Their algorithm achieves both an -bicriteria 5-approximation and an -bicriteria approximation. They also establish logarithmic approximation hardness for the -bicriteria problem, for every constant , under .
The constant-factor bicriteria guarantee is measured against , whereas Theorem 1.2 gives an approximation relative to . Since for , a constant-factor bound relative to does not in general imply a constant-factor approximation relative to . Our running time is also independent of the aspect ratio . Table 1 summarizes the results.
Table 1. Constructions of sparse -navigable graphs in general metrics. Here is the aspect ratio and is the matrix multiplication exponent. The result of Conway et al. assumes distinct distances from each target. The matrix-multiplication bound of Khanna et al. uses .
Euclidean spaces. For fixed dimension , Arya and Mount [3] and Fu et al. [9] construct 1-navigable graphs on points in under the Euclidean distance, with edges in and time, respectively, assuming distinct distances. For every , Indyk and Xu [17] construct an -navigable graph with edges in time.
High dimension can force dense navigable graphs. For every fixed , Diwan et al. [7] give Euclidean point sets in dimensions requiring edges for 1-navigability, and point sets in dimensions requiring edges. Waizer and Danieli [26] obtain an lower bound in dimensions with pairwise distinct distances. Together with the construction of Conway et al. [CDFC^{+}26], this gives a tight worst-case edge bound under the distinct-distance assumption. With distance ties, an equilateral metric requires all directed edges. Diwan et al. [DGM^{+}24] also give -dimensional instances requiring maximum outdegree for 1-navigability. For every fixed , Al-Jazzazi et al. [AJDG^{+}25] give points in -dimensional Euclidean space, with pairwise distinct distances, for which every -navigable graph requires all directed edges.
Other graph constructions in Euclidean space focus on efficient ANN search rather than -navigability. For , Lu and Tao [19] construct graphs with edges in time with high probability, supporting -ANN queries in time. Har-Peled, Raichel, and Robson [14] obtain graphs with edges supporting -ANN queries in time.
Almost navigability. Avi and Musco [4] relax 1-navigability by requiring that, for at least a fraction of each source’s other targets, some outgoing neighbor is closer to the target than the source. Assuming pairwise distinct distances, for , their randomized algorithm constructs a graph with edges in time with success probability at least , assuming constant-time distance access. Waizer and Danieli [26] show that the worst-case edge count over Euclidean point sets with pairwise distinct distances is for all sufficiently large and all sufficiently small . These results characterize the worst-case edge count for almost navigability. Our algorithm approximates the optimum on each input metric while ensuring -navigability for every ordered pair, without assuming distinct distances.
Technical Overview
For a fixed source , choosing outgoing neighbors can be formulated as a Set Cover problem, following previous work [CDFC^{+}26, KPW26]. For each possible intermediate point , define the set of targets for which the edge satisfies the navigation requirement:
Choosing outgoing neighbors that satisfy the navigation requirement for is equivalent to covering with the corresponding sets . Let denote the minimum number of sets needed, equivalently the minimum feasible outdegree of .
We say that covers when . Let denote the uncovered targets, those not covered by any selected intermediate point. Initially, . Adding to the outgoing neighborhood inserts and updates .
An incidence is a pair with . These incidences define a bipartite incidence graph: each left vertex corresponds to an intermediate point and represents the set , while each right vertex corresponds to a target . The two vertices are adjacent exactly when . The degree of a target is its frequency, the number of sets containing it; the degree of an intermediate point is the set size .
The graph has at most vertices on each side and can contain edges. Constructing it explicitly and running greedy, which repeatedly selects a set covering the most uncovered targets, takes time per source and time overall. Our goal is to preserve the approximation while reducing the total running time to near-quadratic.
Limiting target frequency by random pivots. Suppose that we know a degree estimate satisfying . Since we seek an approximation, we can afford outgoing edges. Let be the set of points obtained from independent uniform samples from ; we call these points pivots. Add the edges for .
We show that after adding the pivot edges, every uncovered target has frequency with high probability. Figure 1 illustrates the argument.

Figure 1. (a) Few points closer than the nearest pivot. Here points are ordered from left to right by their distance from for illustration. The nearest pivot has distance from . With high probability, only points satisfy . (b) Uncovered targets have few choices. If remains uncovered after adding edges from to , then . Every intermediate point that covers satisfies . Denote these points by ; all satisfy . Sampled pivots; Points with ; Intermediate points covering ; Source.
Let be the distance from to its nearest pivot:
If remains uncovered, no pivot covers it, so . Every intermediate point covering must therefore satisfy
Thus it suffices to bound the number of points strictly closer to than its nearest pivot.
For a fixed target , hitting one of its nearest points, with ties broken arbitrarily, ensures that fewer than points lie strictly closer to than its nearest pivot. Each draw hits these points with probability at least , so independent draws hit one with high probability. Thus, with high probability, if remains uncovered, its frequency is . A union bound over all targets gives this frequency bound for every uncovered target simultaneously with high probability. The event that hits one of these nearest points for every target does not depend on the source. Hence the frequency bound holds simultaneously for all sources, and sources with the same degree estimate can share .
Sampled greedy coverage. In each iteration, we aim to choose at most additional intermediate points covering at least half of the current uncovered targets . We sample targets from and run greedy on the sampled Set Cover instance to choose these points. We then check their coverage on exactly. If they cover at least half of , we add the corresponding edges and remove the covered targets from . Otherwise, we discard the proposed points and report failure.
At the start of each iteration, draw a uniform sample of targets from without replacement. If is smaller than the prescribed sample size, take . This defines a sampled Set Cover instance with targets and sets for . Its incidence graph retains all left vertices and only the target vertices in .
Run greedy on the sampled instance for at most steps, each time choosing a restricted set covering the most remaining sampled targets. Stop earlier if all sampled targets are covered. An optimal neighborhood of provides at most sets covering . At each step, one of these sets covers at least a fraction of the remaining sampled targets, and greedy covers at least as many. Since , the covered fraction of is therefore at least
We only need this constant coverage, rather than a cover of the entire sample.
We use a standard sampling argument [15, 13]. Fix any collection of at most intermediate points covering less than half of . Hoeffding’s inequality bounds the probability that it covers at least of by . There are at most such collections. Thus sampled targets suffice, by a union bound, to ensure that every collection covering at least of also covers at least half of , with high probability. If , this implication holds deterministically. This guarantee holds simultaneously for all such choices on the same sample . It therefore applies to greedy’s choices, even though they are made after examining . Consequently, the proposed points cover at least half of with high probability.
For each target , we sort by distance to once and reuse this order for all sources. By the frequency bound, each sampled target has degree , so the sampled incidence graph has edges. For each , we scan its distance order until to enumerate its incident edges. We implement greedy using buckets indexed by the number of sampled targets a set still covers, updating the affected sets whenever a sampled target is covered. Each incidence is processed times, so constructing the sampled incidence graph and running greedy take time in total.
Each successful iteration halves , so such iterations use neighbors in total. However, we must still find the targets in covered by the proposed points, both to check their coverage exactly and to update . Since a selected set may cover targets, directly processing up to selected sets can cost time per iteration.
Bounding set sizes with pivots. We obtain a second pivot set of size using a variant of Thorup and Zwick’s center-selection method [25 Theorem 3.1]. Define the nearest-pivot distances and the lists by
The list contains the targets for which is closer than every pivot in . These lists coincide with their clusters. We require
We first explain how these lists eliminate the update bottleneck, then show how to construct and the lists.
After adding the edges for , every target remaining in satisfies . Thus an intermediate point can cover only if
and consequently
For the at most intermediate points proposed by greedy, we scan their lists and check which listed targets belong to and satisfy the navigation inequality. Marking each covered target only once gives the exact coverage in time. If at least half of is covered, we add the proposed edges and remove the marked targets from ; otherwise, we leave unchanged.
Since , , and the lists for do not depend on the source, they can be shared by all sources with the same degree estimate . For each source , we add both and to its neighborhood before the greedy iterations, contributing neighbors in total. Using , , we can filter the current in time, retaining exactly the targets satisfying
The set bounds target frequencies, allowing us to construct the sampled incidence graph and run greedy in time. The lists obtained from support exact validation and updates in time. Together, they give time per iteration. Figure 2 illustrates this combination of pivots, sampled greedy coverage, and exact validation.

Figure 2. (a) Intermediate points and targets. Fix a source . Left vertices represent intermediate points , and right vertices represent targets . An edge means , equivalently .
(b) After adding the pivot edges. Add edges from to and remove covered targets, leaving . With high probability, the remaining graph has maximum degree on both sides: bounds target frequencies, and bounds set sizes. This graph is kept implicit.
(c) Sampled greedy coverage. Sample targets uniformly without replacement. Keep all intermediate points and only target vertices in . Construct the sampled graph explicitly and run greedy for at most choices, obtaining (orange). Unsampled targets and their edges are faded.
(d) Exact validation on . Check the same selected points against all targets in by scanning their lists . If at least half of is covered, add to the neighborhood and remove the covered targets; otherwise, leave unchanged.
Selected intermediate points ; Covered targets; Sampled, not covered by ; Unsampled in (c).
Pivots and sampled greedy coverage.
Constructing by adaptive sampling. Call a point satisfied when its current list has size at most . Start with pivots and set , interpreting . While , perform a round: draw points independently and uniformly from , add them to , and remove from every point that is now satisfied. When , add all remaining points of to and finish.
Adding pivots can only shrink the lists, so every point removed from remains satisfied. Each point added to has , so the final insertion satisfies all remaining points. Thus every point is satisfied when the construction finishes. Figure 3 illustrates one round.

Figure 3. (a) before the round. Each has . Bars show list sizes; the dashed line marks the satisfaction threshold. Here and all six lists have size .
(b) Sample pivots and update. Draw points independently and uniformly from with replacement. Add the distinct pivots (orange) to , forming . Their lists become empty; other points can also become satisfied.
(c) Retain unsatisfied points. Keep only points with . Faded points are removed from , while sampled pivots remain in . Two points survive in this illustrated round.
Sampled pivots; Newly satisfied; Retained; Removed from
Contraction in expectation
One round of adaptive sampling for .
To bound the number of rounds, fix and before a round’s draws. For each target , the expected number of points in closer to than every new pivot is at most . Summing over all targets, the expected total size of the lists for , after adding the new pivots, is at most . Every point that remains in contributes more than to this sum. So the expected number of unsatisfied points is less than .
This contraction holds for every state before a round. Consequently, all points are satisfied after rounds with high probability. Since each round adds at most pivots, this gives a set of size . A round can be implemented by scanning the distance matrix in time. Thus constructing and its lists takes time with high probability. This preprocessing is performed once for each degree estimate and reused by all sources with that estimate.
Completing the construction. To handle the unknown value of , try degree estimates , capping the last estimate at . At each estimate, add edges to the corresponding pivots and remove the targets they cover from . Repeat the sampled greedy iterations, adding the proposed points as neighbors only if they cover at least half of . If this check fails, move to the next estimate, retaining all previously added neighbors and the current . Stop when becomes empty.
With high probability, every iteration at the first estimate passes the check, so the source finishes at that estimate or earlier. This estimate is less than . Each successful iteration therefore adds neighbors, and there are only successful iterations across all estimates because each halves . The pivot sets also contribute neighbors in total, since their sizes grow geometrically with the degree estimates. Summing over sources gives edges.
There is at most one failed iteration per estimate, so each source performs iterations in total. Each takes time, giving time per source. The shared preprocessing for all degree estimates costs in expectation and with high probability. Thus the total running time is .
Relation to prior techniques. Set sampling and element sampling are established techniques in streaming and sublinear Set Cover [8, 13, 16]. The former covers high-frequency elements using random sets, as in our construction of ; the latter selects sets on a sampled universe to cover much of the original universe, as in our sampled greedy coverage. Conway et al.’s VoteCover [5] achieves a similar effect through a sampling-based simulation of greedy, using voting ideas with earlier precedents in Rajagopalan and Vazirani [22].
Controlling the cost of updating uncovered targets requires additional structure. For , Conway et al. partition unfinished sources into groups of at most vertices and make each group a clique in the output graph. In their setting, the vertex of closest to an external target is a valid intermediate point for every other source in , but need not satisfy the navigation requirement for . Thus, when , each clique leaves at most one uncovered source–target pair per external target, giving such pairs per clique. Across all groups, this leaves uncovered source–target pairs. Their update cost per pair therefore gives total update time. To control this update cost for general , we adapt the center-selection construction of Thorup and Zwick [25 Theorem 3.1]. Together with the sampling techniques above, this yields a near-quadratic construction for every .
Refining the approximation factor. To reduce the leading constant, use pivots at degree estimate , for . The two residual degree bounds then become . Use sampled targets and accept the first greedy prefix leaving at most an fraction of uncovered, updating the exact coverage incrementally. When , this rule accepts a prefix of at most choices with high probability. The smaller pivot sets contribute only neighbors in total. Choosing the constants appropriately gives a approximation while preserving exact -navigability through validation.
These refinements take time with high probability. The factor combines the increase in the residual degree bounds with the increase in sample size needed to control the coverage error to . The known hardness results [KPWV26, CDFC+26] establish the logarithmic dependence, but do not show that the leading coefficient is optimal for this problem.
Preliminaries
Let be an -point metric and . All pairwise distances are given by the matrix . We use for base-2 logarithms and for natural logarithms. Unless stated otherwise, we round up to integers where necessary and omit the ceiling notation.
For a fixed source , an intermediate point is a possible outgoing neighbor of . Define its covered targets by
We say that covers for source precisely when , meaning that the edge satisfies the navigation requirement toward . We allow . For , the intermediate points that cover it form
The frequency of is . The optimum outdegree for is
The constraints and edge costs decompose by source, so .
The analysis uses the following coverage and concentration bounds.
Lemma 3.1 (Greedy maximum coverage [21]). Let be a finite nonempty universe and a finite family of subsets of . Suppose that can be covered by at most sets from . Repeatedly choose a set covering the largest number of currently uncovered elements, stopping after choices or when all elements are covered. The chosen sets cover at least elements.
Proof. Fix at most sets covering . If is the set of currently uncovered elements, one of these sets contains at least elements of . Greedy covers at least as many. If the procedure stops before choices, it therefore covers all of . Otherwise each choice reduces the number of uncovered elements by a factor at most . After choices, at most
elements remain uncovered, proving the bound.
Lemma 3.2 (Hoeffding upper-tail inequality [12]). Let be a finite nonempty set with fixed values for . For an integer , let be uniformly distributed among the -element subsets of . For every ,
Construction and Analysis
We begin with a high-level description of the algorithm. For each source , let denote the targets not covered by its chosen outgoing neighbors. The algorithm tries increasing degree estimates. At degree estimate , the algorithm first adds outgoing edges to the corresponding pivots. Each subsequent iteration runs greedy maximum coverage on a fresh sample of the uncovered targets to propose at most intermediate points. The proposed points are added only if together they cover at least half of the uncovered targets. If this check fails, the algorithm moves to the next estimate, retaining all previously added neighbors and the current .
Setup and Conventions. We assume below; for , the empty graph is optimal. For each source , we try increasing degree estimates for its optimum outdegree . We process stages in increasing order. Stage uses the estimate , where
For any set , define
We interpret minima over empty sets as . Thus is the distance to the nearest pivot, and lists the targets for which is closer than every pivot in . In particular, . For each target , sort and store the points as so that
resolving equal distances by a fixed total order on . Sorting and storing these orders takes time.
Constructing Pivots
Fix an integer degree estimate . We construct two pivot sets , shared by all sources with this estimate. For each source , adding edges from to bounds the number of intermediate points that can cover each target remaining in . Adding edges from to bounds the sizes of the remaining sets . Both constructions treat every point of as a potential intermediate point; when adding outgoing edges from , we exclude itself.
Bounding Target Frequency with . We construct by sampling and verification (Algorithm 1), ensuring that, for every target , at most points lie strictly closer to than its nearest pivot. To explain the role of this property, fix a source and let be its uncovered targets after adding edges from to . The frequency of a target is the number of intermediate points that cover it, namely . For every and , we have
Thus every remaining target has frequency at most . The following lemma establishes the required property of and bounds its size and construction time.
Lemma 4.1. Algorithm 1 constructs a pivot set and its nearest-pivot distances satisfying
The algorithm runs in time with probability at least .
Algorithm 1: Constructing the pivot set
Input: Distance matrix and degree estimate . Output: A pivot set and its nearest-pivot distances .
if then return
while true do
Draw independent uniform points from with replacement
the set of distinct sampled points
for every
if for every then
return
// Discard this failed pass and restart with fresh samples.
Proof. Output properties. If , the algorithm returns and . Then , and no point satisfies for any target . Otherwise, consists of the distinct points among draws, so . The algorithm returns a sampled set only after verifying that, for every target , at most points satisfy . For every target left uncovered by the pivot edges, , so its frequency is at most .
Running time. A pass is one iteration of the while loop in Algorithm 1. Fix a pass and all random choices made before it starts.
For , the bound holds automatically. Otherwise, fix a target . If more than points satisfy , every sampled point must appear after more than points in the stored distance order around . The fraction of occupying such positions is at most . Independence of the draws therefore gives
using . A union bound over all targets gives a failure probability of at most .
Computing takes time, and the check in Line 6 of Algorithm 1 requires one scan of the distance matrix. Hence one pass costs time. With probability at least , the first pass succeeds, giving the same bound on the total time. The same running-time bound holds in expectation.
Bounding Set Sizes with . We construct by adaptive sampling (Algorithm 2), using a variant of Thorup and Zwick’s center-selection method [25 Theorem 3.1]. The construction ensures that for every .
To explain the role of this property, fix a source and let be its uncovered targets after adding edges from to . Every satisfies , so
Thus every remaining set has size at most . The following lemma establishes the required property of and bounds its size and construction time.
Lemma 4.2. Algorithm 2 constructs a pivot set and its nearest-pivot distances such that
The algorithm runs in time with probability at least .
Algorithm 2: Constructing the pivot set
Input: Distance matrix and degree estimate .
Output: A pivot set and its nearest-pivot distances .
while true do
; ; for all
for to do
if then
else
Draw independent uniform points from with replacement
the set of distinct sampled points
foreach do
if then return
// Discard this failed pass and restart with fresh samples.
Proof. We analyze one pass, an iteration of the outer while loop in Algorithm 2. Each pass starts from the same state and uses fresh random samples. Let and denote the sets and after round , respectively; denotes the corresponding nearest-pivot distances. In particular, , , and . For analysis, if becomes empty early, keep these values unchanged through the remaining rounds.
Output properties. The updates maintain . These distances never increase because only grows. Call an intermediate point satisfied after round if . Every point removed from is satisfied and remains so, since its list can only shrink as the nearest-pivot distances decrease. Thus, when becomes empty, every intermediate point is satisfied. Each round adds at most pivots, and a pass contains at most rounds, giving .
Contraction in one round. Condition on the random choices made before round , so that is fixed. If , every point of is added to . Hence for every , and .
Suppose . We bound by counting pairs with and in two ways. Fix a target , and list as in the stored distance order around . For to hold, all draws must come from points strictly farther from than . There are at most such points. Thus, independence of the draws and linearity of expectation give
Every point in has more than targets in its list and therefore contributes more than such pairs. Counting these pairs first by intermediate point and then by target gives
Taking expectations and applying the bound for each target yields
Averaging over the random choices in the preceding rounds gives
Here the expectations are over the random draws within this pass.
Running time. A pass fails only if . By Markov’s inequality,
Each round takes time, including distance updates, filtering, and all other operations. Hence one pass takes time. With probability at least , the first pass succeeds, giving the same bound on the total time. Fresh retries require at most passes in expectation, so the expected running time is also .
Combining the Two Pivot Sets. The following lemma combines the two pivot guarantees and includes the explicit construction of all lists .
Lemma 4.3. For every degree estimate , the combined pivot set , the lists , and the nearest-pivot distances satisfy
These data can be constructed in time with probability at least . All lists are explicitly constructed within this time bound.
Proof. The size bounds on and give
For each intermediate point , the inequality implies . Hence by Lemma 4.2. For each target , the inequality gives
The latter set has size at most by Lemma 4.1, proving the third bound.
By the same lemmas and a union bound, constructing and takes time with probability at least . The same total time bound holds in expectation. Scan all pairs and append to when ; this takes additional time.
For stage , write and for the pivot sets of Lemma 4.3 with , with nearest-pivot distances and lists .
Sampled Greedy Coverage
This subsection presents the procedure in Algorithm 3. At stage , it uses greedy maximum coverage on a sample of the uncovered targets to propose at most intermediate points. It then computes their coverage in and returns the points together with the covered targets if at least half of is covered; otherwise, it returns .
Parameters and Input. At stage , the procedure takes a source and a nonempty set satisfying
This condition states that none of the stage’s pivot edges covers a target in . It draws a uniformly random subset of size
In particular, when .
Incidence Graphs. For a fixed source , the remaining Set Cover instance has targets and sets . We represent it by a bipartite graph.
Definition 4.4 (Incidence graph). For a source and a target set , the incidence graph is the bipartite graph with vertex and edge sets
Here denotes disjoint union: the left vertex class is a copy of representing intermediate points, and the right vertex class is a copy of representing targets. The two copies of the same point are distinct vertices; in particular, joins the left copy of to its right copy.
The neighbors of a target in are , and the neighbors of an intermediate point are . Under (2), Claim 4.6 bounds both degrees by . We access implicitly. For each , scan the stored points in nondecreasing order of distance from , stopping at the first point with . The points preceding it are exactly . To find , scan and retain the targets satisfying .
Restricting the target set from to gives the sampled Set Cover instance, whose sets are .
Definition 4.5 (Sampled incidence graph). For a sample , the sampled incidence graph is the subgraph of obtained by deleting the target vertices in and their incident edges. All left vertices are retained. It represents the Set Cover instance with universe and sets .
Construct explicitly by enumerating for each and adding the edges for . Write for the neighbors of a vertex . Here denotes a left vertex and a right vertex, so
Each sampled target has at most neighbors, so has at most edges.
Greedy and Validation Steps. After constructing , the procedure has two steps. The greedy step (Lines 8–12) starts with and , where contains the sampled targets not yet covered by . While and , choose an intermediate point maximizing , resolving ties arbitrarily. Add to and remove its neighbors from . Every choice has positive gain: a target is covered by the intermediate point . Thus the selected intermediate points are distinct.
The validation step (Lines 13–17) computes the targets in covered by . Initialize . For each , scan and insert into every target satisfying . Return if , and return otherwise.
Algorithm 3:
Input: Source and nonempty satisfying (2) at stage .
Output: with , , and ; or if the chosen points cover fewer than targets of .
if then
else
Draw targets uniformly without replacement from to form
Initialize with vertex set and no edges
foreach do
Enumerate and add to for every
;
while and do
Choose maximizing
foreach do
if then return
return
The following claim shows how the pivot bounds support sampled incidence graph construction and exact validation.
Claim 4.6. For a source and a nonempty set satisfying (2) at stage ,
For each , can be enumerated in time using the stored distance order around .
Proof. If for , then
Thus and . Lemma 4.3 bounds both the set of intermediate points and the list by . To enumerate , scan the stored distance order around until the first point satisfying . This takes at most comparisons.
Lemma 4.7. Algorithm 3 returns either or a pair satisfying
It runs in time.
Proof. The greedy step chooses at most intermediate points. By Claim 4.6, every target in covered by a chosen point lies in . Filtering this list by membership in and the navigation inequality finds exactly . The validation step therefore computes the stated set and returns it only if .
For each sampled target, Claim 4.6 enumerates its neighbors in time. Since , constructing takes time. For the greedy step, maintain only unselected intermediate points in buckets indexed by their current gains . When a sampled target becomes covered, update the gains of its unselected neighbors. Each edge is processed a constant number of times, and the maximum gain only decreases. Greedy therefore takes time as well.
Using Boolean arrays for membership tests, validation takes time. All other operations take time, so the total running time is .
Lemma 4.8. If , the set chosen by the greedy step satisfies
Proof. An optimum set of outgoing neighbors covers every target in , so its neighborhoods in cover . Lemma 3.1 guarantees coverage of at least targets after at most greedy choices. Since , the final greedy set achieves at least this coverage.
Lemma 4.9. If , then returns a pair with probability at least . If , the call succeeds deterministically.
Proof. We use a standard sampling argument [15, 13]. Fix all random choices made before this execution of . With probability at least , every choice of at most intermediate points that covers at least of also covers at least half of . We prove this guarantee for all such sets on the same sample , so it also applies to the set chosen by greedy after observing .
If , Lemma 4.8 guarantees coverage of more than targets, so validation succeeds. Suppose . Before drawing , fix a set with , and let
be the targets it covers. Suppose . If , the fraction of targets covered by in exceeds that in by more than . Applying Lemma 3.2 to the indicators , , with gives
There are at most sets of size at most . A union bound therefore bounds the probability of any such event by
since and .
By Lemma 4.8, the greedy set covers more than sampled targets, and . The guarantee applies to even though it depends on . Hence with probability at least , and the validation step returns .
The Complete Construction
Algorithm 4, ConstructGraph, takes the distance matrix of and . If , it returns . Otherwise, it stores the distance orders and constructs the pivots, nearest-pivot distances, and lists for all stages. These are shared by all sources. It then computes for each and returns the graph with edges for .
Algorithm 4: ConstructGraph
Input: Metric given by its distance matrix and .
Output: An -navigable graph on .
if then return
Set the degree estimates and stages by (1)
Sort and store the distance order around each target using the fixed tie-breaking order
for to do
Apply Lemma 4.3 with degree estimate to construct , , , and all
foreach do
Add to for each
return
For a fixed source , the procedure in Algorithm 5 maintains its chosen outgoing neighbors and its uncovered targets . Initialize and , and process stages in order. At stage , it adds to and removes the targets covered by these pivots using .
While is nonempty, call . If a pair is returned, it adds to , removes from , and continues at the same stage. If is returned, it proceeds to the next stage without changing or . The procedure returns when becomes empty. Lemma 4.10 shows that this happens by stage .
Algorithm 5: Neighbors($s$)
Input: Source $s \in P$.
Output: An outgoing neighborhood $N \subseteq P \setminus \{s\}$ covering every target $t \ne s$.
1 $N \leftarrow \varnothing$; $U \leftarrow P \setminus \{s\}$
2 for $j \leftarrow 0$ to $\ell$ do
3 $N \leftarrow N \cup ((Q_j \cup R_j) \setminus \{s\})$
4 $U \leftarrow \{t \in U : \alpha\mu_{Q_j\cup R_j}(t) \ge d(s,t)\}$
5 while $U \ne \varnothing$ do
6 if $\operatorname{Cover}_j(s,U)$ returns $(S,C)$ then
7 $N \leftarrow N \cup S$; $U \leftarrow U \setminus C$
8 else
9 break
10 if $U = \varnothing$ then break
11 return $N$
Lemma 4.10. Algorithm 5 terminates and returns a set satisfying
Consequently, every graph returned by Algorithm 4 is -navigable.
Proof. We show that Neighbors() maintains
The equality holds initially.
At stage , a target is covered by the pivot edges exactly when . Excluding from the pivot neighbors does not affect this test, since . Previously covered targets remain covered because only grows. Thus adding the pivots and filtering preserves the equality and establishes (2).
By Lemma 4.7, the returned set covers exactly the targets in within the current . The updates and therefore preserve the equality. A return of changes neither set.
Every successful call reduces by at least half, and the first failed call exits its stage. At the last stage, and the construction sets . Adding these pivots makes . The procedure therefore terminates with the claimed coverage. □
Lemma 4.11. For every outcome of the random choices, Neighbors() processes stages and makes calls to .
Proof. The degree estimates double until reaching , giving stages. Each successful call halves the number of uncovered targets, and adding pivots can only decrease it further. Hence at most calls succeed across all stages. Each failed call exits its stage, so there is at most one failure per stage. The total number of calls is . □
The Approximation Guarantee
We prove the approximation guarantee by bounding separately the neighbors contributed by greedy choices and by pivots.
Lemma 4.12. With probability at least , the neighborhoods returned by Neighbors satisfy simultaneously for all .
Proof. Fix all pivot sets constructed by Algorithm 4. All probabilities below are over the fresh samples drawn by . For each source , let be the first stage with . Since and each estimate is at most twice the preceding one, this stage exists and satisfies .
At this stage, the source makes at most calls: each successful call removes at least one target, and a return of exits the stage. For each , condition on the random choices preceding the -th call, if it occurs. Since , Lemma 4.9 bounds its conditional probability of returning by . Averaging over the preceding choices, the probability that this call occurs and returns is therefore at most . A union bound over all sources and possible call indices per source shows that, with probability at least , no call at a source’s first stage with returns . On this event, every source finishes at that stage or earlier.
Fix a source and assume this simultaneous event holds. At every visited stage , each successful call adds at most neighbors. By Lemma 4.11, there are such calls, so the greedy choices contribute neighbors. Since the estimates preceding are distinct powers of two smaller than , we have . The pivots contribute at most
Adding the two contributions proves the claim.
Running Time
Lemma 4.13. Algorithm 4 runs in time with probability at least . The same bound holds in expectation.
Proof. For each source, Lemmas 4.11 and 4.7 bound the time spent in by . Adding pivots and updating take time per stage or call. Processing all sources therefore takes time for every outcome of the random choices.
Sorting the distance orders takes time. There is one pivot construction for each of the stages. By Lemma 4.3 and a union bound over stages, all pivot constructions together take time with probability at least . The same bound holds in expectation by the expected-time bounds proved for the pivot constructions.
Proof of Theorem 1.2. Exact -navigability follows from Lemma 4.10. Summing the outdegree bounds of Lemma 4.12 gives . Lemma 4.13 provides the running-time bounds. The space usage is , since the stored pivot lists have total size and all remaining data fit within this bound. By a union bound, the probability that either the approximation bound or the stated running-time bound fails is at most
Disclosure of AI Use
| Activity | AI used |
| Asking the research question | No |
| Coming up with the approach | Yes |
| Proof development | Yes |
| Writing and exposition | Yes |
| Checking for bugs | Yes |
| Other supporting tasks | Yes |
Table 2 (PDF p. 22).
All AI assistance in this work was provided by GPT-6.1 Sol. The authors formulated the research question and explored the use of the random pivot set together with sampling techniques from streaming Set Cover. Building on these ideas, GPT-6.1 Sol proposed using adaptive sampling to construct and completed the algorithm, analysis, and proofs. The construction of is a variant of the center-selection method of Thorup and Zwick [25 Theorem 3.1].
The authors examined and verified the resulting algorithm and analysis. They prepared the manuscript with AI assistance throughout the writing process, including drafting and revising text, checking for typos, and polishing the exposition. GPT-6.1 Sol also helped check the technical arguments for errors and generated figures.
The authors verified all proofs and results presented in the paper and take full responsibility for its correctness, originality, exposition, and attribution.
Acknowledgment
Hongyi Chen and Tianyi Zhang are supported by the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No. JYB2025XDXM118) and the “111 Center” (No. B26023).
References
- [3]Sunil Arya and David M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 271–280, 1993.DOI
- [5][CDFC+26] Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, and Richard Wen. Efficiently constructing sparse navigable graphs. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1631–1665. Society for Industrial and Applied Mathematics, 2026.arxiv.org/abs/2507.13296
- [8][DIMV14] Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. On streaming and communication complexity of the set cover problem. In Proceedings of the 28th International Symposium on Distributed Computing (DISC), volume 8784 of Lecture Notes in Computer Science, pages 484–498. Springer, 2014.DOI
- [9][FXWC19] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the Navigating Spreading-out Graph. Proceedings of the VLDB Endowment, 12(5):461–474, 2019.arxiv.org/abs/1707.00143
- [12][Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.
- [13][HPIMV16] Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. Towards tight bounds for the streaming set cover problem. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 371–383. Association for Computing Machinery, 2016.
- [14][HPRR26] Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The road to the closest point is paved by good neighbors. In Proceedings of the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 1–11. Society for Industrial and Applied Mathematics, 2026.
- [15][HPS11] Sariel Har-Peled and Micha Sharir. Relative (p, ε)-approximations in geometry. Discrete & Computational Geometry, 45(3):462–496, 2011.DOI
- [16]Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Set cover in sub-linear time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2467–2486. Society for Industrial and Applied Mathematics, 2018.arxiv.org/abs/1902.03534
- [17]Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 66239–66256, 2023.arxiv.org/abs/2310.19126
- [19]Shangqi Lu and Yufei Tao. Proximity graphs for similarity search: Fast construction, lower bounds, and Euclidean separation. Proceedings of the ACM on Management of Data, 3(5):280:1–280:25, 2025.arxiv.org/abs/2509.07732
- [20]Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020.
- [21]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14:265–294, 1978.DOI
- [22]Sridhar Rajagopalan and Vijay V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM Journal on Computing, 28(2):525–540, 1998.DOI
- [25]Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1–10. Association for Computing Machinery, 2001.DOI
- [26]Tomer Waizer and Yoav Danieli. The price of almost navigability, 2026. arXiv:2609.02498.arxiv.org/abs/2609.02498