betaFeedback

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 nn-point metric (P,d)(P,d) and a parameter α≥1α\ge1, a directed graph on PP is αα-navigable if, for every pair of distinct points s,t∈Ps,t\in P, the source ss has an outgoing neighbor pp with d(p,t)<d(s,t)/αd(p,t)<d(s,t)/α. 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)O(\log n)-approximation algorithms and show that an o(log⁡n)o(\log n) approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general α≥1α\ge1 was O~(min⁡{nOPT⁡α,n2.5})\widetilde O(\min\{n\operatorname{OPT}_α,n^{2.5}\}), where OPT⁡α\operatorname{OPT}_α is the minimum number of edges in an αα-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in O~(n2)\widetilde O(n^2) time and achieves an O(log⁡n)O(\log n) approximation for every α≥1α\ge1. 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 (α\alpha-navigability). Let (P,d)(P,d) be an nn-point metric and let α≥1\alpha\ge1. A directed graph (P,E)(P,E) with no self-loops is α\alpha-navigable if, for every pair of distinct points s,t∈Ps,t \in P, some edge (s,p)∈E(s,p) \in E satisfies

αd(p,t)<d(s,t).\alpha d(p,t) < d(s,t).

We call ss the source, tt the target, and pp an intermediate point; pp may be tt itself. For α=1\alpha= 1, the condition guarantees that a greedy search can always move closer to a target in PP until it reaches that target. Larger values of α\alpha require more progress from each step. The analysis of Indyk and Xu [17] implies that, for every 0<ε≤10 < \varepsilon\le1, one can choose α=O(1/ε)\alpha= O(1/\varepsilon) so that greedy search on an α\alpha-navigable graph finds a (1+ε)(1+\varepsilon)-approximate nearest neighbor (ANN) of any query point in O(log⁡(Δ/ε))O(\log(\Delta/\varepsilon)) search steps, where Δ\Delta is the aspect ratio of (P,d)(P,d), 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 (P,d)(P,d) and α≥1\alpha\ge1, build an α\alpha-navigable graph with as few edges as possible. Let OPTα\mathrm{OPT}_{\alpha} 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 OPTα\mathrm{OPT}_{\alpha} 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 ss, each possible outgoing edge (s,p)(s,p) corresponds to the set of targets t∈P∖{s}t \in P \setminus\{s\} for which (s,p)(s,p) satisfies the navigation requirement. Choosing outgoing neighbors for ss is therefore equivalent to selecting as few such sets as possible to cover P∖{s}P \setminus\{s\}. Applying greedy Set Cover to all nn instances yields an O(log⁡n)O(\log n) approximation in O(n3)O(n^3) time. Both works also show that obtaining an O(log⁡n)O(\log n) approximation is NP-hard in general. Thus the remaining algorithmic question is how quickly we can obtain the logarithmic approximation.

For general α≥1\alpha\ge1, Khanna, Padaki, and Waingarten [18] give an O~(n OPTα)\widetilde{O}(n\ \mathrm{OPT}_{\alpha})-time algorithm, and Conway et al. [CDFC⁺26] obtain O~(min⁡{n OPTα,n2.5})\widetilde{O}(\min\{n\ \mathrm{OPT}_{\alpha}, n^{2.5}\}) time. Here O~\widetilde{O} suppresses factors polylogarithmic in nn. For α=1\alpha= 1, Conway et al. further obtain an O~(n2)\widetilde{O}(n^2)-time construction, assuming that the distances from each point to the other points are pairwise distinct. Their work leaves near-quadratic construction for general α\alpha open. Khanna, Padaki, and Waingarten also use matrix multiplication to obtain a bicriteria guarantee: the output is α\alpha-navigable, but its size is compared with the optimum under a stronger navigation requirement. These results leave the following question:

Can we obtain an O(log⁡n)O(\log n) approximation to the sparsest α\alpha-navigable graph in near-quadratic time for every α≥1\alpha\ge1?

Main Result

We give an affirmative answer to this question. Even for α=1\alpha= 1, 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 (P,d)(P,d) be an nn-point metric space. For every α≥1\alpha\ge1, there is a randomized algorithm that constructs an α\alpha-navigable graph on (P,d)(P,d). With high probability, the algorithm runs in O(n2log⁡2n)O(n^2 \log^2 n) time and returns a graph with at most O(log⁡n)OPT⁡αO(\log n)\operatorname{OPT}_{\alpha} edges, where OPT⁡α\operatorname{OPT}_{\alpha} is the minimum number of edges in an α\alpha-navigable graph on (P,d)(P,d).

The O(log⁡n)O(\log n) approximation also holds separately for each source’s outdegree, and is optimal up to constants in general. Moreover, even for α=1\alpha= 1, any randomized algorithm achieving an o(n)o(n) approximation with constant success probability requires Ω(n2)\Omega(n^2) distance queries [18 Theorem 5]. Thus our running time matches this query lower bound up to polylogarithmic factors.

For any 0<ε≤10 < \varepsilon\le1, a more careful choice of parameters and standard refinements of the analysis give a (1+ε)(ln⁡n+1)(1+\varepsilon)(\ln n + 1) approximation in Oε(n2log⁡2n)O_{\varepsilon}(n^2 \log^2 n) 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 β≥α\beta\ge\alpha, let OPT⁡β\operatorname{OPT}_{\beta} denote the minimum number of edges in a β\beta-navigable graph on the same metric. An (α,β)(\alpha,\beta)-bicriteria approximation constructs an α\alpha-navigable graph and compares its edge count with OPT⁡β\operatorname{OPT}_{\beta}. Let ω\omega denote the matrix multiplication exponent.

Khanna, Padaki, and Waingarten [18] introduced this bicriteria formulation. For every α≥1\alpha\ge1 and 0<ε<10 < \varepsilon< 1, their algorithm uses matrix multiplication to construct an α\alpha-navigable graph with O(log⁡n)OPT⁡2(1+ε)αO(\log n)\operatorname{OPT}_{2(1+\varepsilon)\alpha} edges in O~(nωlog⁡Δ/ε)\widetilde{O}(n^{\omega}\log\Delta/\varepsilon) time. In the notation above, this is an (α,2(1+ε)α)(\alpha,2(1+\varepsilon)\alpha)-bicriteria O(log⁡n)O(\log n) approximation.

In a follow-up work, Chen and Zhang [6] reduce the running time to O~(n2log⁡Δ)\widetilde{O}(n^2\log\Delta) for constant α≥1\alpha\ge1. Their algorithm achieves both an (α,2α+O(1))(\alpha,2\alpha+O(1))-bicriteria 5-approximation and an (α,α+O(1))(\alpha,\alpha+O(1))-bicriteria O(log⁡n)O(\log n) approximation. They also establish logarithmic approximation hardness for the (α,2α−η)(\alpha,2\alpha-\eta)-bicriteria problem, for every constant η∈(0,1)\eta\in(0,1), under P≠NP\mathrm{P} \ne\mathrm{NP}.

The constant-factor bicriteria guarantee is measured against OPT⁡2α+O(1)\operatorname{OPT}_{2\alpha+O(1)}, whereas Theorem 1.2 gives an O(log⁡n)O(\log n) approximation relative to OPT⁡α\operatorname{OPT}_{\alpha}. Since OPT⁡β≥OPT⁡α\operatorname{OPT}_{\beta} \ge\operatorname{OPT}_{\alpha} for β>α\beta> \alpha, a constant-factor bound relative to OPT⁡β\operatorname{OPT}_{\beta} does not in general imply a constant-factor approximation relative to OPT⁡α\operatorname{OPT}_{\alpha}. Our running time is also independent of the aspect ratio Δ\Delta. Table 1 summarizes the results.

ReferenceEdge boundRunning time
Khanna et al. [18]O(log⁡n) OPTαO(\log n)\ \mathrm{OPT}_{\alpha}O~(n OPTα)\widetilde{O}(n\ \mathrm{OPT}_{\alpha})
Khanna et al. [18]O(log⁡n) OPT2(1+ε)αO(\log n)\ \mathrm{OPT}_{2(1+\varepsilon)\alpha}O~(nωlog⁡Δ/ε)\widetilde{O}(n^{\omega}\log\Delta/\varepsilon)
Conway et al. [CDFC^{+}26]O(log⁡n) OPTαO(\log n)\ \mathrm{OPT}_{\alpha}O~(min⁡{n OPTα,n2.5})\widetilde{O}(\min\{n\ \mathrm{OPT}_{\alpha},n^{2.5}\})
Conway et al. [CDFC^{+}26]$ (α=1\alpha=1) | O(log⁡n) OPT1O(\log n)\ \mathrm{OPT}_{1} | O~(n2)\widetilde{O}(n^{2})
Chen–Zhang [6]5 OPT2α+O(1)5\ \mathrm{OPT}_{2\alpha+O(1)}O~(n2log⁡Δ)\widetilde{O}(n^{2}\log\Delta)
Chen–Zhang [6]O(log⁡n) OPTα+O(1)O(\log n)\ \mathrm{OPT}_{\alpha+O(1)}O~(n2log⁡Δ)\widetilde{O}(n^{2}\log\Delta)
This paperO(log⁡n) OPTαO(\log n)\ \mathrm{OPT}_{\alpha}O~(n2)\widetilde{O}(n^{2})

Table 1. Constructions of sparse α\alpha-navigable graphs in general metrics. Here Δ\Delta is the aspect ratio and ω\omega is the matrix multiplication exponent. The α=1\alpha=1 result of Conway et al. assumes distinct distances from each target. The matrix-multiplication bound of Khanna et al. uses 0<ε<10<\varepsilon<1.

Euclidean spaces. For fixed dimension dd, Arya and Mount [3] and Fu et al. [9] construct 1-navigable graphs on nn points in Rd\mathbb{R}^d under the Euclidean distance, with n2O(d)n2^{O(d)} edges in O(n2)O(n^2) and O(n2log⁡n)O(n^2\log n) time, respectively, assuming distinct distances. For every α≥1\alpha\ge1, Indyk and Xu [17] construct an α\alpha-navigable graph with O(n(2α)O(d)log⁡Δ)O(n(2\alpha)^{O(d)}\log\Delta) edges in O(n3)O(n^3) time.

High dimension can force dense navigable graphs. For every fixed γ>0\gamma> 0, Diwan et al. [7] give Euclidean point sets in Oγ(log⁡n)O_{\gamma}(\log n) dimensions requiring Ω(n3/2−γ)\Omega(n^{3/2-\gamma}) edges for 1-navigability, and point sets in O(log⁡3n)O(\log^3 n) dimensions requiring Ω(n3/2/log⁡n)\Omega(n^{3/2}/\log n) edges. Waizer and Danieli [26] obtain an Ω(n3/2)\Omega(n^{3/2}) lower bound in O(nlog⁡n)O(\sqrt{n}\log n) dimensions with pairwise distinct distances. Together with the O(n3/2)O(n^{3/2}) 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 n(n−1)n(n-1) directed edges. Diwan et al. [DGM^{+}24] also give O(log⁡n)O(\log n)-dimensional instances requiring maximum outdegree Ω(n)\Omega(n) for 1-navigability. For every fixed α>1\alpha>1, Al-Jazzazi et al. [AJDG^{+}25] give nn points in O(log⁡n)O(\log n)-dimensional Euclidean space, with pairwise distinct distances, for which every α\alpha-navigable graph requires all n(n−1)n(n-1) directed edges.

Other graph constructions in Euclidean space focus on efficient ANN search rather than α\alpha-navigability. For ε∈(0,1)\varepsilon\in(0,1), Lu and Tao [19] construct graphs with O(nε−O(d))O(n\varepsilon^{-O(d)}) edges in npolylog⁡(nΔ)n\operatorname{polylog}(n\Delta) time with high probability, supporting (1+ε)(1+\varepsilon)-ANN queries in polylog⁡(nΔ)\operatorname{polylog}(n\Delta) time. Har-Peled, Raichel, and Robson [14] obtain graphs with O(nε−d)O(n\varepsilon^{-d}) edges supporting (1+ε)(1+\varepsilon)-ANN queries in O(ε−dlog⁡Δ)O(\varepsilon^{-d}\log\Delta) time.

Almost navigability. Avi and Musco [4] relax 1-navigability by requiring that, for at least a (1−τ)(1-\tau) fraction of each source’s other targets, some outgoing neighbor is closer to the target than the source. Assuming pairwise distinct distances, for 0<τ,ξ<10<\tau,\xi<1, their randomized algorithm constructs a graph with O(n/τ)O(n/\tau) edges in O(nlog⁡(n/ξ)/τ)O(n\log(n/\xi)/\tau) time with success probability at least 1−ξ1-\xi, 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 Θ(nmin⁡{τ−1,n})\Theta(n\min\{\tau^{-1},\sqrt{n}\}) for all sufficiently large nn and all sufficiently small τ>0\tau>0. These results characterize the worst-case edge count for almost navigability. Our algorithm approximates the optimum on each input metric while ensuring α\alpha-navigability for every ordered pair, without assuming distinct distances.

Technical Overview

For a fixed source ss, choosing outgoing neighbors can be formulated as a Set Cover problem, following previous work [CDFC^{+}26, KPW26]. For each possible intermediate point p≠sp\ne s, define the set of targets for which the edge (s,p)(s,p) satisfies the navigation requirement:

Ss(p)={t∈P∖{s}:αd(p,t)<d(s,t)}.S_s(p)=\{t\in P\setminus\{s\}:\alpha d(p,t)<d(s,t)\}.

Choosing outgoing neighbors that satisfy the navigation requirement for ss is equivalent to covering P∖{s}P \setminus\{s\} with the corresponding sets Ss(p)S_s(p). Let ksk_s denote the minimum number of sets needed, equivalently the minimum feasible outdegree of ss.

We say that pp covers tt when t∈Ss(p)t \in S_s(p). Let UU denote the uncovered targets, those not covered by any selected intermediate point. Initially, U=P∖{s}U = P \setminus\{s\}. Adding pp to the outgoing neighborhood inserts (s,p)(s,p) and updates U←U∖Ss(p)U \leftarrow U \setminus S_s(p).

An incidence is a pair (p,t)(p,t) with t∈Ss(p)t \in S_s(p). These incidences define a bipartite incidence graph: each left vertex corresponds to an intermediate point p≠sp \ne s and represents the set Ss(p)S_s(p), while each right vertex corresponds to a target t≠st \ne s. The two vertices are adjacent exactly when t∈Ss(p)t \in S_s(p). The degree of a target is its frequency, the number of sets containing it; the degree of an intermediate point pp is the set size ∣Ss(p)∣\lvert S_s(p)\rvert.

The graph has at most nn vertices on each side and can contain Θ(n2)\Theta(n^2) edges. Constructing it explicitly and running greedy, which repeatedly selects a set covering the most uncovered targets, takes O(n2)O(n^2) time per source and O(n3)O(n^3) time overall. Our goal is to preserve the O(log⁡n)O(\log n) approximation while reducing the total running time to near-quadratic.

Limiting target frequency by random pivots. Suppose that we know a degree estimate DD satisfying ks≤D≤2ksk_s \le D \le2k_s. Since we seek an O(log⁡n)O(\log n) approximation, we can afford O(Dlog⁡n)O(D \log n) outgoing edges. Let QQ be the set of points obtained from O(Dlog⁡n)O(D \log n) independent uniform samples from PP; we call these points pivots. Add the edges (s,q)(s,q) for q∈Q∖{s}q \in Q \setminus\{s\}.

We show that after adding the pivot edges, every uncovered target has frequency O(n/D)O(n/D) with high probability. Figure 1 illustrates the argument.

Random pivots bound target frequency

Figure 1. (a) Few points closer than the nearest pivot. Here points are ordered from left to right by their distance from tt for illustration. The nearest pivot q∗q_* has distance μQ(t)=d(q∗,t)\mu_Q(t) = d(q_*,t) from tt. With high probability, only O(n/D)O(n/D) points satisfy d(p,t)<μQ(t)d(p,t) < \mu_Q(t). (b) Uncovered targets have few choices. If tt remains uncovered after adding edges from ss to Q∖{s}Q \setminus\{s\}, then d(s,t)/α≤μQ(t)d(s,t)/\alpha\le\mu_Q(t). Every intermediate point that covers tt satisfies d(p,t)<d(s,t)/αd(p,t) < d(s,t)/\alpha. Denote these points by Bs(t)B_s(t); all satisfy d(p,t)<μQ(t)d(p,t) < \mu_Q(t). Sampled pivots; Points with d(p,t)<μQ(t)d(p,t) < \mu_Q(t); Intermediate points covering tt; Source.

Let μQ(t)\mu_Q(t) be the distance from tt to its nearest pivot:

μQ(t)=min⁡q∈Qd(q,t).\mu_Q(t) = \min_{q \in Q} d(q,t).

If tt remains uncovered, no pivot covers it, so μQ(t)≥d(s,t)/α\mu_Q(t) \ge d(s,t)/\alpha. Every intermediate point pp covering tt must therefore satisfy

d(p,t)<d(s,t)α≤μQ(t).d(p,t) < \frac{d(s,t)}{\alpha} \le\mu_Q(t).

Thus it suffices to bound the number of points strictly closer to tt than its nearest pivot.

For a fixed target tt, hitting one of its ⌈n/D⌉\lceil n/D\rceil nearest points, with ties broken arbitrarily, ensures that fewer than ⌈n/D⌉\lceil n/D\rceil points lie strictly closer to tt than its nearest pivot. Each draw hits these points with probability at least 1/D1/D, so O(Dlog⁡n)O(D\log n) independent draws hit one with high probability. Thus, with high probability, if tt remains uncovered, its frequency is O(n/D)O(n/D). A union bound over all nn targets gives this frequency bound for every uncovered target simultaneously with high probability. The event that QQ 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 DD can share QQ.

Sampled greedy coverage. In each iteration, we aim to choose at most DD additional intermediate points covering at least half of the current uncovered targets UU. We sample targets from UU and run greedy on the sampled Set Cover instance to choose these points. We then check their coverage on UU exactly. If they cover at least half of UU, we add the corresponding edges (s,p)(s,p) and remove the covered targets from UU. Otherwise, we discard the proposed points and report failure.

At the start of each iteration, draw a uniform sample TT of O(Dlog⁡n)O(D\log n) targets from UU without replacement. If ∣U∣|U| is smaller than the prescribed sample size, take T=UT=U. This defines a sampled Set Cover instance with targets TT and sets Ss(p)∩TS_s(p)\cap T for p≠sp\ne s. Its incidence graph retains all left vertices and only the target vertices in TT.

Run greedy on the sampled instance for at most DD 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 ss provides at most ksk_s sets covering TT. At each step, one of these sets covers at least a 1/ks1/k_s fraction of the remaining sampled targets, and greedy covers at least as many. Since D≥ksD\ge k_s, the covered fraction of TT is therefore at least

1−(1−1/ks)D≥1−e−1>5/8.1-(1-1/k_s)^D \ge1-e^{-1}>5/8.

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 DD intermediate points covering less than half of UU. Hoeffding’s inequality bounds the probability that it covers at least 5/85/8 of TT by e−∣T∣/32e^{-|T|/32}. There are at most nDn^D such collections. Thus O(Dlog⁡n)O(D\log n) sampled targets suffice, by a union bound, to ensure that every collection covering at least 5/85/8 of TT also covers at least half of UU, with high probability. If T=UT=U, this implication holds deterministically. This guarantee holds simultaneously for all such choices on the same sample TT. It therefore applies to greedy’s choices, even though they are made after examining TT. Consequently, the proposed points cover at least half of UU with high probability.

For each target tt, we sort PP by distance to tt once and reuse this order for all sources. By the frequency bound, each sampled target has degree O(n/D)O(n/D), so the sampled incidence graph has O(Dlog⁡n)⋅O(n/D)=O(nlog⁡n)O(D\log n)\cdot O(n/D)=O(n\log n) edges. For each t∈Tt\in T, we scan its distance order until d(p,t)≥d(s,t)d(p,t)\ge d(s,t) 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 O(1)O(1) times, so constructing the sampled incidence graph and running greedy take O(nlog⁡n)O(n\log n) time in total.

Each successful iteration halves ∣U∣|U|, so O(log⁡n)O(\log n) such iterations use O(Dlog⁡n)O(D\log n) neighbors in total. However, we must still find the targets in UU covered by the proposed points, both to check their coverage exactly and to update UU. Since a selected set may cover O(n)O(n) targets, directly processing up to DD selected sets can cost O(Dn)O(Dn) time per iteration.

Bounding set sizes with pivots. We obtain a second pivot set RR of size O(Dlog⁡n)O(D \log n) using a variant of Thorup and Zwick’s center-selection method [25 Theorem 3.1]. Define the nearest-pivot distances and the lists by

μR(t)=min⁡r∈Rd(r,t),IR(p)={t∈P:d(p,t)<μR(t)}.\mu_R(t) = \min_{r \in R} d(r,t), \qquad I_R(p) = \{t \in P : d(p,t) < \mu_R(t)\}.

The list IR(p)I_R(p) contains the targets for which pp is closer than every pivot in RR. These lists coincide with their clusters. We require

∣IR(p)∣≤n/Dfor every p∈P.|I_R(p)| \le n/D \qquad\text{for every } p \in P.

We first explain how these lists eliminate the update bottleneck, then show how to construct RR and the lists.

After adding the edges (s,r)(s,r) for r∈R∖{s}r \in R \setminus\{s\}, every target tt remaining in UU satisfies μR(t)≥d(s,t)/α\mu_R(t) \ge d(s,t)/\alpha. Thus an intermediate point pp can cover tt only if

d(p,t)<d(s,t)α≤μR(t),d(p,t) < \frac{d(s,t)}{\alpha} \le\mu_R(t),

and consequently

Ss(p)∩U⊆IR(p).S_s(p) \cap U \subseteq I_R(p).

For the at most DD intermediate points proposed by greedy, we scan their lists IR(p)I_R(p) and check which listed targets belong to UU and satisfy the navigation inequality. Marking each covered target only once gives the exact coverage in O(D⋅n/D)=O(n)O(D \cdot n/D) = O(n) time. If at least half of UU is covered, we add the proposed edges and remove the marked targets from UU; otherwise, we leave UU unchanged.

Since RR, μR\mu_R, and the lists IR(p)I_R(p) for p∈Pp \in P do not depend on the source, they can be shared by all sources with the same degree estimate DD. For each source ss, we add both Q∖{s}Q \setminus\{s\} and R∖{s}R \setminus\{s\} to its neighborhood before the greedy iterations, contributing O(Dlog⁡n)O(D \log n) neighbors in total. Using μQ(t)\mu_Q(t), μR(t)\mu_R(t), we can filter the current UU in O(n)O(n) time, retaining exactly the targets satisfying

d(s,t)α≤min⁡{μQ(t),μR(t)}.\frac{d(s,t)}{\alpha} \le\min\{\mu_Q(t), \mu_R(t)\}.

The set QQ bounds target frequencies, allowing us to construct the sampled incidence graph and run greedy in O(nlog⁡n)O(n \log n) time. The lists obtained from RR support exact validation and updates in O(n)O(n) time. Together, they give O(nlog⁡n)O(n \log n) time per iteration. Figure 2 illustrates this combination of pivots, sampled greedy coverage, and exact validation.

Pivots and sampled greedy coverage

Figure 2. (a) Intermediate points and targets. Fix a source ss. Left vertices represent intermediate points p≠sp \ne s, and right vertices represent targets t≠st \ne s. An edge (p,t)(p,t) means t∈Ss(p)t \in S_s(p), equivalently αd(p,t)<d(s,t)\alpha d(p,t) < d(s,t).

(b) After adding the pivot edges. Add edges from ss to (Q∪R)∖{s}(Q \cup R) \setminus\{s\} and remove covered targets, leaving UU. With high probability, the remaining graph has maximum degree O(n/D)O(n/D) on both sides: QQ bounds target frequencies, and RR bounds set sizes. This graph is kept implicit.

(c) Sampled greedy coverage. Sample targets T⊆UT \subseteq U uniformly without replacement. Keep all intermediate points and only target vertices in TT. Construct the sampled graph explicitly and run greedy for at most DD choices, obtaining SS (orange). Unsampled targets and their edges are faded.

(d) Exact validation on UU. Check the same selected points SS against all targets in UU by scanning their lists IR(p)I_R(p). If at least half of UU is covered, add SS to the neighborhood and remove the covered targets; otherwise, leave UU unchanged.

Selected intermediate points SS; Covered targets; Sampled, not covered by SS; Unsampled in (c).

Pivots and sampled greedy coverage.

Constructing RR by adaptive sampling. Call a point pp satisfied when its current list IR(p)I_R(p) has size at most n/Dn/D. Start with pivots R=∅R = \varnothing and set A=PA = P, interpreting μ∅(t)=+∞\mu_{\varnothing}(t) = +\infty. While ∣A∣>2D|A| > 2D, perform a round: draw 2D2D points independently and uniformly from AA, add them to RR, and remove from AA every point that is now satisfied. When ∣A∣≤2D|A| \le2D, add all remaining points of AA to RR and finish.

Adding pivots can only shrink the lists, so every point removed from AA remains satisfied. Each point added to RR has IR(p)=∅I_R(p) = \varnothing, so the final insertion satisfies all remaining points. Thus every point is satisfied when the construction finishes. Figure 3 illustrates one round.

One round of adaptive sampling for R

Figure 3. (a) AA before the round. Each p∈Ap \in A has ∣IR(p)∣>n/D|I_R(p)| > n/D. Bars show list sizes; the dashed line marks the satisfaction threshold. Here R=∅R = \varnothing and all six lists have size nn.

(b) Sample pivots and update. Draw 2D2D points independently and uniformly from AA with replacement. Add the distinct pivots BB (orange) to RR, forming R′=R∪BR' = R \cup B. Their lists become empty; other points can also become satisfied.

(c) Retain unsatisfied points. Keep only points with ∣IR′(p)∣>n/D|I_{R'}(p)| > n/D. Faded points are removed from AA, while sampled pivots remain in R′R'. Two points survive in this illustrated round.

Sampled pivots; Newly satisfied; Retained; Removed from AA

Contraction in expectation

E[∣Anext∣]≤∣A∣2\mathbb{E}[|A_{\mathrm{next}}|] \le\frac{|A|}{2}

One round of adaptive sampling for RR.

To bound the number of rounds, fix RR and AA before a round’s draws. For each target tt, the expected number of points in AA closer to tt than every new pivot is at most ∣A∣/(2D+1)|A|/(2D + 1). Summing over all nn targets, the expected total size of the lists IR(p)I_R(p) for p∈Ap \in A, after adding the new pivots, is at most n∣A∣/(2D+1)n|A|/(2D + 1). Every point that remains in AA contributes more than n/Dn/D to this sum. So the expected number of unsatisfied points is less than ∣A∣/2|A|/2.

This contraction holds for every state before a round. Consequently, all points are satisfied after O(log⁡n)O(\log n) rounds with high probability. Since each round adds at most 2D2D pivots, this gives a set RR of size O(Dlog⁡n)O(D \log n). A round can be implemented by scanning the distance matrix in O(n2)O(n^2) time. Thus constructing RR and its lists takes O(n2log⁡n)O(n^2 \log n) time with high probability. This preprocessing is performed once for each degree estimate DD and reused by all sources with that estimate.

Completing the construction. To handle the unknown value of ksk_s, try degree estimates D=1,2,4,…D = 1, 2, 4, \ldots, capping the last estimate at n−1n - 1. At each estimate, add edges to the corresponding pivots and remove the targets they cover from UU. Repeat the sampled greedy iterations, adding the proposed points as neighbors only if they cover at least half of UU. If this check fails, move to the next estimate, retaining all previously added neighbors and the current UU. Stop when UU becomes empty.

With high probability, every iteration at the first estimate D≥ksD \ge k_s passes the check, so the source finishes at that estimate or earlier. This estimate is less than 2ks2k_s. Each successful iteration therefore adds O(ks)O(k_s) neighbors, and there are only O(log⁡n)O(\log n) successful iterations across all estimates because each halves UU. The pivot sets also contribute O(kslog⁡n)O(k_s \log n) neighbors in total, since their sizes grow geometrically with the degree estimates. Summing over sources gives O(log⁡n)OPT⁡αO(\log n)\operatorname{OPT}_{\alpha} edges.

There is at most one failed iteration per estimate, so each source performs O(log⁡n)O(\log n) iterations in total. Each takes O(nlog⁡n)O(n \log n) time, giving O(nlog⁡2n)O(n \log^2 n) time per source. The shared preprocessing for all O(log⁡n)O(\log n) degree estimates costs O(n2log⁡2n)O(n^2 \log^2 n) in expectation and with high probability. Thus the total running time is O(n2log⁡2n)O(n^2 \log^2 n).

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 QQ; 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 α=1\alpha= 1, Conway et al. partition unfinished sources into O(n/D)O(n / D) groups of at most DD vertices and make each group CC a clique in the output graph. In their setting, the vertex of CC closest to an external target tt is a valid intermediate point for every other source in CC, but need not satisfy the navigation requirement for α>1\alpha> 1. Thus, when α=1\alpha= 1, each clique leaves at most one uncovered source–target pair per external target, giving O(n)O(n) such pairs per clique. Across all groups, this leaves O(n2/D)O(n^2 / D) uncovered source–target pairs. Their O~(D)\widetilde{O}(D) update cost per pair therefore gives O~(n2)\widetilde{O}(n^2) total update time. To control this update cost for general α\alpha, 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 α≥1\alpha\ge1.

Refining the approximation factor. To reduce the leading constant, use O(εDlog⁡n)O(\varepsilon D \log n) pivots at degree estimate DD, for 0<ε≤10 < \varepsilon\le1. The two residual degree bounds then become O(n/(εD))O(n / (\varepsilon D)). Use O(ε−2Dlog⁡n)O(\varepsilon^{-2}D \log n) sampled targets and accept the first greedy prefix leaving at most an ε−1+O(ε)\varepsilon^{-1} + O(\varepsilon) fraction of UU uncovered, updating the exact coverage incrementally. When D≥ksD \ge k_s, this rule accepts a prefix of at most ksk_s choices with high probability. The smaller pivot sets contribute only O(εkslog⁡n)O(\varepsilon k_s \log n) neighbors in total. Choosing the constants appropriately gives a (1+ε)(ln⁡n+1)(1 + \varepsilon)(\ln n + 1) approximation while preserving exact α\alpha-navigability through validation.

These refinements take O(ε−3n2log⁡2n)O(\varepsilon^{-3}n^2 \log^2 n) time with high probability. The factor ε−3\varepsilon^{-3} combines the ε−1\varepsilon^{-1} increase in the residual degree bounds with the ε−2\varepsilon^{-2} increase in sample size needed to control the coverage error to O(ε)O(\varepsilon). The known hardness results [KPWV26, CDFC+26] establish the logarithmic dependence, but do not show that the leading coefficient 11 is optimal for this problem.

Preliminaries

Let (P,d)(P,d) be an nn-point metric and α≥1\alpha\ge1. All pairwise distances are given by the matrix (d(p,t))p,t∈P(d(p,t))_{p,t\in P}. We use log⁡\log for base-2 logarithms and ln⁡\ln for natural logarithms. Unless stated otherwise, we round up to integers where necessary and omit the ceiling notation.

For a fixed source ss, an intermediate point p∈P∖{s}p \in P \setminus\{s\} is a possible outgoing neighbor of ss. Define its covered targets by

Ss(p)={t∈P∖{s}:αd(p,t)<d(s,t)}.S_s(p) = \{t \in P \setminus\{s\} : \alpha d(p,t) < d(s,t)\}.

We say that pp covers tt for source ss precisely when t∈Ss(p)t \in S_s(p), meaning that the edge (s,p)(s,p) satisfies the navigation requirement toward tt. We allow p=tp=t. For t∈P∖{s}t \in P \setminus\{s\}, the intermediate points that cover it form

Bs(t)={p∈P∖{s}:t∈Ss(p)}.B_s(t) = \{p \in P \setminus\{s\} : t \in S_s(p)\}.

The frequency of tt is ∣Bs(t)∣|B_s(t)|. The optimum outdegree for ss is

ks=min⁡{∣Ns∣:Ns⊆P∖{s}, ⋃p∈NsSs(p)=P∖{s}}.k_s = \min\left\{ |N_s| : N_s \subseteq P \setminus\{s\},\ \bigcup_{p\in N_s} S_s(p) = P \setminus\{s\} \right\}.

The constraints and edge costs decompose by source, so OPTα=∑s∈Pks\mathrm{OPT}_{\alpha} = \sum_{s\in P} k_s.

The analysis uses the following coverage and concentration bounds.

Lemma 3.1 (Greedy maximum coverage [21]). Let VV be a finite nonempty universe and F\mathcal{F} a finite family of subsets of VV. Suppose that VV can be covered by at most kk sets from F\mathcal{F}. Repeatedly choose a set covering the largest number of currently uncovered elements, stopping after kk choices or when all elements are covered. The chosen sets cover at least (1−e−1)∣V∣(1-e^{-1})|V| elements.

Proof. Fix at most kk sets covering VV. If UU is the set of currently uncovered elements, one of these sets contains at least ∣U∣/k|U|/k elements of UU. Greedy covers at least as many. If the procedure stops before kk choices, it therefore covers all of VV. Otherwise each choice reduces the number of uncovered elements by a factor at most 1−1/k1-1/k. After kk choices, at most

(1−1/k)k∣V∣≤e−1∣V∣(1-1/k)^k|V| \le e^{-1}|V|

elements remain uncovered, proving the bound.

Lemma 3.2 (Hoeffding upper-tail inequality [12]). Let VV be a finite nonempty set with fixed values xv∈[0,1]x_v \in[0,1] for v∈Vv \in V. For an integer 1≤q≤∣V∣1 \le q \le|V|, let WW be uniformly distributed among the qq-element subsets of VV. For every η>0\eta> 0,

P[1q∑v∈Wxv−1∣V∣∑v∈Vxv≥η]≤e−2qη2.\mathbb{P}\left[\frac{1}{q}\sum_{v\in W}x_v-\frac{1}{|V|}\sum_{v\in V}x_v\ge\eta\right]\le e^{-2q\eta^2}.

Construction and Analysis

We begin with a high-level description of the algorithm. For each source ss, let UU denote the targets not covered by its chosen outgoing neighbors. The algorithm tries increasing degree estimates. At degree estimate DD, 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 DD 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 UU.

Setup and Conventions. We assume n≥2n \ge2 below; for n≤1n \le1, the empty graph (P,∅)(P,\varnothing) is optimal. For each source ss, we try increasing degree estimates for its optimum outdegree ksk_s. We process stages j=0,…,ℓj=0,\ldots,\ell in increasing order. Stage jj uses the estimate DjD_j, where

Dj=min⁡{2j,n−1},ℓ=min⁡{j∈Z≥0:2j≥n−1}.(1)D_j=\min\{2^j,n-1\},\qquad\ell=\min\{j\in\mathbb{Z}_{\ge0}:2^j\ge n-1\}. \tag*{(1)}

For any set X⊆PX\subseteq P, define

μX(t)=min⁡x∈Xd(x,t),IX(p)={t∈P:d(p,t)<μX(t)}.\mu_X(t)=\min_{x\in X}d(x,t),\qquad I_X(p)=\{t\in P:d(p,t)<\mu_X(t)\}.

We interpret minima over empty sets as +∞+\infty. Thus μX(t)\mu_X(t) is the distance to the nearest pivot, and IX(p)I_X(p) lists the targets for which pp is closer than every pivot in XX. In particular, I∅(p)=PI_{\varnothing}(p)=P. For each target tt, sort and store the points as pt,1,…,pt,np_{t,1},\ldots,p_{t,n} so that

d(pt,1,t)≤⋯≤d(pt,n,t),d(p_{t,1},t)\le\cdots\le d(p_{t,n},t),

resolving equal distances by a fixed total order on PP. Sorting and storing these orders takes O(n2log⁡n)O(n^2\log n) time.

Constructing Pivots

Fix an integer degree estimate 1≤D≤n1\le D\le n. We construct two pivot sets Q,R⊆PQ,R\subseteq P, shared by all sources with this estimate. For each source ss, adding edges from ss to Q∖{s}Q\setminus\{s\} bounds the number of intermediate points that can cover each target remaining in UU. Adding edges from ss to R∖{s}R\setminus\{s\} bounds the sizes of the remaining sets Ss(p)∩US_s(p)\cap U. Both constructions treat every point of PP as a potential intermediate point; when adding outgoing edges from ss, we exclude ss itself.

Bounding Target Frequency with QQ. We construct QQ by sampling and verification (Algorithm 1), ensuring that, for every target tt, at most n/Dn/D points lie strictly closer to tt than its nearest pivot. To explain the role of this property, fix a source ss and let UU be its uncovered targets after adding edges from ss to Q∖{s}Q\setminus\{s\}. The frequency of a target t∈Ut\in U is the number of intermediate points p≠sp\ne s that cover it, namely ∣Bs(t)∣|B_s(t)|. For every t∈Ut\in U and p∈Bs(t)p\in B_s(t), we have

d(p,t)<d(s,t)α≤μQ(t).d(p,t)<\frac{d(s,t)}{\alpha}\le\mu_Q(t).

Thus every remaining target has frequency at most n/Dn/D. The following lemma establishes the required property of QQ and bounds its size and construction time.

Lemma 4.1. Algorithm 1 constructs a pivot set Q⊆PQ\subseteq P and its nearest-pivot distances μQ\mu_Q satisfying

∣Q∣≤8Dlog⁡n,∣{p∈P:d(p,t)<μQ(t)}∣≤n/D(t∈P).|Q|\le8D\log n,\qquad|\{p\in P:d(p,t)<\mu_Q(t)\}|\le n/D\quad(t\in P).

The algorithm runs in O(n2)O(n^2) time with probability at least 1−n−71-n^{-7}.

Algorithm 1: Constructing the pivot set QQ

Input: Distance matrix and degree estimate DD. Output: A pivot set QQ and its nearest-pivot distances μQ\mu_Q.

  1. if 8Dlog⁡n≥n8D\log n \ge n then return (P,0)(P,0)

  2. while true do

  3. Draw 8Dlog⁡n8D\log n independent uniform points from PP with replacement

  4. Q←Q \leftarrow the set of distinct sampled points

  5. μQ(t)←min⁡p∈Qd(p,t)\mu_Q(t) \leftarrow\min_{p\in Q} d(p,t) for every t∈Pt\in P

  6. if ∣{p∈P:d(p,t)<μQ(t)}∣≤n/D\left|\{p\in P:d(p,t)<\mu_Q(t)\}\right|\le n/D for every t∈Pt\in P then

  7. return (Q,μQ)(Q,\mu_Q)

  8. // Discard this failed pass and restart with fresh samples.

Proof. Output properties. If 8Dlog⁡n≥n8D\log n \ge n, the algorithm returns Q=PQ=P and μQ(t)=0\mu_Q(t)=0. Then ∣Q∣=n≤8Dlog⁡n|Q|=n\le8D\log n, and no point pp satisfies d(p,t)<μQ(t)d(p,t)<\mu_Q(t) for any target tt. Otherwise, QQ consists of the distinct points among 8Dlog⁡n8D\log n draws, so ∣Q∣≤8Dlog⁡n|Q|\le8D\log n. The algorithm returns a sampled set QQ only after verifying that, for every target tt, at most n/Dn/D points satisfy d(p,t)<μQ(t)d(p,t)<\mu_Q(t). For every target left uncovered by the pivot edges, Bs(t)⊆{p∈P:d(p,t)<μQ(t)}B_s(t)\subseteq\{p\in P:d(p,t)<\mu_Q(t)\}, so its frequency is at most n/Dn/D.

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 D=1D=1, the bound holds automatically. Otherwise, fix a target tt. If more than n/Dn/D points satisfy d(p,t)<μQ(t)d(p,t)<\mu_Q(t), every sampled point must appear after more than n/Dn/D points in the stored distance order around tt. The fraction of PP occupying such positions is at most 1−1/D1-1/D. Independence of the draws therefore gives

P(∣{p∈P:d(p,t)<μQ(t)}∣>n/D)≤(1−1D)8Dlog⁡n≤e−8log⁡n≤n−8\mathbb{P}\left(\left|\{p\in P:d(p,t)<\mu_Q(t)\}\right|>n/D\right)\le\left(1-\frac{1}{D}\right)^{8D\log n}\le e^{-8\log n}\le n^{-8}

using log⁡n≥ln⁡n\log n\ge\ln n. A union bound over all nn targets gives a failure probability of at most n−7n^{-7}.

Computing μQ\mu_Q takes O(n∣Q∣)=O(n2)O(n|Q|)=O(n^2) time, and the check in Line 6 of Algorithm 1 requires one scan of the distance matrix. Hence one pass costs O(n2)O(n^2) time. With probability at least 1−n−71-n^{-7}, the first pass succeeds, giving the same bound on the total time. The same running-time bound holds in expectation.

Bounding Set Sizes with RR. We construct RR by adaptive sampling (Algorithm 2), using a variant of Thorup and Zwick’s center-selection method [25 Theorem 3.1]. The construction ensures that ∣IR(p)∣≤n/D|I_R(p)|\le n/D for every p∈Pp\in P.

To explain the role of this property, fix a source ss and let UU be its uncovered targets after adding edges from ss to R∖{s}R\setminus\{s\}. Every t∈Ut\in U satisfies d(s,t)/α≤μR(t)d(s,t)/\alpha\le\mu_R(t), so

Ss(p)∩U⊆IR(p)(p∈P∖{s}).S_s(p)\cap U\subseteq I_R(p)\qquad(p\in P\setminus\{s\}).

Thus every remaining set has size at most n/Dn/D. The following lemma establishes the required property of RR and bounds its size and construction time.

Lemma 4.2. Algorithm 2 constructs a pivot set R⊆PR\subseteq P and its nearest-pivot distances μR(t)=min⁡p∈Rd(p,t)\mu_R(t)=\min_{p\in R}d(p,t) such that

∣R∣≤16Dlog⁡n,∣IR(p)∣≤n/D(p∈P).|R|\le16D\log n,\qquad|I_R(p)|\le n/D\qquad(p\in P).

The algorithm runs in O(n2log⁡n)O(n^2\log n) time with probability at least 1−n−71-n^{-7}.

Algorithm 2: Constructing the pivot set RR

Input: Distance matrix and degree estimate DD.

Output: A pivot set RR and its nearest-pivot distances μR\mu_R.

  1. while true do

  2. A←PA \leftarrow P; R←∅R \leftarrow\varnothing; μR(t)←+∞\mu_R(t) \leftarrow+\infty for all t∈Pt \in P

  3. for i←1i \leftarrow1 to 8log⁡n8\log n do

  4. if ∣A∣≤2D|A| \le2D then

  5. B←AB \leftarrow A

  6. else

  7. Draw 2D2D independent uniform points from AA with replacement

  8. B←B \leftarrow the set of distinct sampled points

  9. R←R∪BR \leftarrow R \cup B

  10. foreach t∈Pt \in P do

  11. μR(t)←min⁡(μR(t),min⁡p∈Bd(p,t))\mu_R(t) \leftarrow\min\bigl(\mu_R(t),\min_{p\in B} d(p,t)\bigr)

  12. A←{p∈A:∣IR(p)∣>n/D}A \leftarrow\{p \in A : |I_R(p)| > n/D\}

  13. if A=∅A = \varnothing then return (R,μR)(R,\mu_R)

  14. // 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 AiA_i and RiR_i denote the sets AA and RR after round ii, respectively; μRi\mu_{R_i} denotes the corresponding nearest-pivot distances. In particular, A0=PA_0=P, R0=∅R_0=\varnothing, and μR0(t)=+∞\mu_{R_0}(t)=+\infty. For analysis, if AA becomes empty early, keep these values unchanged through the remaining rounds.

Output properties. The updates maintain μRi(t)=min⁡p∈Rid(p,t)\mu_{R_i}(t)=\min_{p\in R_i}d(p,t). These distances never increase because RiR_i only grows. Call an intermediate point pp satisfied after round ii if ∣IRi(p)∣≤n/D|I_{R_i}(p)|\le n/D. Every point removed from AA is satisfied and remains so, since its list can only shrink as the nearest-pivot distances decrease. Thus, when AA becomes empty, every intermediate point is satisfied. Each round adds at most 2D2D pivots, and a pass contains at most 8log⁡n8\log n rounds, giving ∣R∣≤16Dlog⁡n|R|\le16D\log n.

Contraction in one round. Condition on the random choices made before round ii, so that Ai−1A_{i-1} is fixed. If ∣Ai−1∣≤2D|A_{i-1}|\le2D, every point of Ai−1A_{i-1} is added to RR. Hence IRi(p)=∅I_{R_i}(p)=\varnothing for every p∈Ai−1p\in A_{i-1}, and Ai=∅A_i=\varnothing.

Suppose ∣Ai−1∣>2D|A_{i-1}|>2D. We bound ∣Ai∣|A_i| by counting pairs (p,t)(p,t) with p∈Ai−1p\in A_{i-1} and d(p,t)<μRi(t)d(p,t)<\mu_{R_i}(t) in two ways. Fix a target tt, and list Ai−1A_{i-1} as p1,…,p∣Ai−1∣p_1,\ldots,p_{|A_{i-1}|} in the stored distance order around tt. For d(pj,t)<μRi(t)d(p_j,t)<\mu_{R_i}(t) to hold, all 2D2D draws must come from points strictly farther from tt than pjp_j. There are at most ∣Ai−1∣−j|A_{i-1}|-j such points. Thus, independence of the draws and linearity of expectation give

E[{p∈Ai−1:d(p,t)<μRi(t)}]≤∑j=1∣Ai−1∣(∣Ai−1∣−j∣Ai−1∣)2D≤∣Ai−1∣∫01x2D dx=∣Ai−1∣2D+1.\begin{aligned} \mathbb{E}\bigl[\{p\in A_{i-1}:d(p,t)<\mu_{R_i}(t)\}\bigr]\le\sum_{j=1}^{|A_{i-1}|}\left(\frac{|A_{i-1}|-j}{|A_{i-1}|}\right)^{2D} \\ &\le|A_{i-1}|\int_0^1 x^{2D}\,\mathrm{d}x=\frac{|A_{i-1}|}{2D+1}. \end{aligned}

Every point in AiA_i has more than n/Dn/D targets in its list and therefore contributes more than n/Dn/D such pairs. Counting these pairs first by intermediate point and then by target gives

nD∣Ai∣≤∑p∈Ai−1∣IRi(p)∣=∑t∈P∣{p∈Ai−1:d(p,t)<μRi(t)}∣.\begin{aligned} \frac{n}{D}|A_i|\le\sum_{p\in A_{i-1}}|I_{R_i}(p)| \\ &=\sum_{t\in P}|\{p\in A_{i-1}:d(p,t)<\mu_{R_i}(t)\}|. \end{aligned}

Taking expectations and applying the bound for each target yields

E∣Ai∣≤D∣Ai−1∣2D+1≤∣Ai−1∣2.\mathbb{E}\lvert A_i\rvert\le\frac{D\lvert A_{i-1}\rvert}{2D+1} \le\frac{\lvert A_{i-1}\rvert}{2}.

Averaging over the random choices in the preceding rounds gives

E∣Ai∣≤12E∣Ai−1∣,and henceE∣Ai∣≤n2−i.\mathbb{E}\lvert A_i\rvert\le\frac{1}{2}\mathbb{E}\lvert A_{i-1}\rvert,\qquad\text{and hence}\qquad\mathbb{E}\lvert A_i\rvert\le n2^{-i}.

Here the expectations are over the random draws within this pass.

Running time. A pass fails only if A8log⁡n≠∅A_{8\log n}\ne\varnothing. By Markov’s inequality,

P(A8log⁡n≠∅)≤E∣A8log⁡n∣≤n2−8log⁡n≤n−7.\mathbb{P}(A_{8\log n}\ne\varnothing)\le\mathbb{E}\lvert A_{8\log n}\rvert\le n2^{-8\log n}\le n^{-7}.

Each round takes O(n∣B∣+n∣A∣+n)=O(n2)O(n\lvert B\rvert+n\lvert A\rvert+n)=O(n^2) time, including distance updates, filtering, and all other operations. Hence one pass takes O(n2log⁡n)O(n^2\log n) time. With probability at least 1−n−71-n^{-7}, the first pass succeeds, giving the same bound on the total time. Fresh retries require at most (1−n−7)−1≤2(1-n^{-7})^{-1}\le2 passes in expectation, so the expected running time is also O(n2log⁡n)O(n^2\log n). □\square

Combining the Two Pivot Sets. The following lemma combines the two pivot guarantees and includes the explicit construction of all lists IQ∪R(p)I_{Q\cup R}(p).

Lemma 4.3. For every degree estimate 1≤D≤n1\le D\le n, the combined pivot set Q∪RQ\cup R, the lists IQ∪R(p)I_{Q\cup R}(p), and the nearest-pivot distances μQ∪R\mu_{Q\cup R} satisfy

∣Q∪R∣≤24Dlog⁡n,\lvert Q\cup R\rvert\le24D\log n,
∣IQ∪R(p)∣≤n/D(p∈P),\lvert I_{Q\cup R}(p)\rvert\le n/D\qquad(p\in P),
∣{p∈P:d(p,t)<μQ∪R(t)}∣≤n/D(t∈P).\lvert\{p\in P:d(p,t)<\mu_{Q\cup R}(t)\}\rvert\le n/D\qquad(t\in P).

These data can be constructed in O(n2log⁡n)O(n^2\log n) time with probability at least 1−2n−71-2n^{-7}. All lists IQ∪R(p)I_{Q\cup R}(p) are explicitly constructed within this time bound.

Proof. The size bounds on QQ and RR give

∣Q∪R∣≤∣Q∣+∣R∣≤24Dlog⁡n.\lvert Q\cup R\rvert\le\lvert Q\rvert+\lvert R\rvert\le24D\log n.

For each intermediate point pp, the inequality μQ∪R(t)≤μR(t)\mu_{Q\cup R}(t)\le\mu_R(t) implies IQ∪R(p)⊆IR(p)I_{Q\cup R}(p)\subseteq I_R(p). Hence ∣IQ∪R(p)∣≤n/D\lvert I_{Q\cup R}(p)\rvert\le n/D by Lemma 4.2. For each target tt, the inequality μQ∪R(t)≤μQ(t)\mu_{Q\cup R}(t)\le\mu_Q(t) gives

{p∈P:d(p,t)<μQ∪R(t)}⊆{p∈P:d(p,t)<μQ(t)}.\{p\in P:d(p,t)<\mu_{Q\cup R}(t)\}\subseteq\{p\in P:d(p,t)<\mu_Q(t)\}.

The latter set has size at most n/Dn/D by Lemma 4.1, proving the third bound.

By the same lemmas and a union bound, constructing QQ and RR takes O(n2log⁡n)O(n^2\log n) time with probability at least 1−2n−71-2n^{-7}. The same total time bound holds in expectation. Scan all pairs (p,t)(p,t) and append tt to IQ∪R(p)I_{Q\cup R}(p) when d(p,t)<μQ∪R(t)d(p,t)<\mu_{Q\cup R}(t); this takes O(n2)O(n^2) additional time. □\square

For stage jj, write QjQ_j and RjR_j for the pivot sets of Lemma 4.3 with D=DjD=D_j, with nearest-pivot distances μQj∪Rj\mu_{Q_j\cup R_j} and lists IQj∪Rj(p)I_{Q_j\cup R_j}(p).

Sampled Greedy Coverage

This subsection presents the procedure Cover⁡j(s,U)\operatorname{Cover}_j(s,U) in Algorithm 3. At stage jj, it uses greedy maximum coverage on a sample of the uncovered targets UU to propose at most DjD_j intermediate points. It then computes their coverage in UU and returns the points together with the covered targets if at least half of UU is covered; otherwise, it returns ⊥\perp.

Parameters and Input. At stage jj, the procedure takes a source ss and a nonempty set U⊆P∖{s}U \subseteq P \setminus\{s\} satisfying

αμQj∪Rj(t)≥d(s,t)(t∈U).(2)\alpha\mu_{Q_j\cup R_j}(t) \ge d(s,t) \qquad(t \in U). \tag*{(2)}

This condition states that none of the stage’s pivot edges covers a target in UU. It draws a uniformly random subset T⊆UT \subseteq U of size

∣T∣=min⁡{∣U∣,256Djln⁡n}.|T| = \min\{|U|,256D_j \ln n\}.

In particular, T=UT = U when ∣U∣≤256Djln⁡n|U| \le256D_j \ln n.

Incidence Graphs. For a fixed source ss, the remaining Set Cover instance has targets UU and sets Ss(p)∩US_s(p) \cap U. We represent it by a bipartite graph.

Definition 4.4 (Incidence graph). For a source ss and a target set U⊆P∖{s}U \subseteq P \setminus\{s\}, the incidence graph GUG_U is the bipartite graph with vertex and edge sets

V(GU)=(P∖{s})⊔U,V(G_U) = (P \setminus\{s\}) \mathbin{\sqcup} U,
E(GU)={(p,t)∈(P∖{s})×U:αd(p,t)<d(s,t)}.E(G_U) = \{(p,t) \in(P \setminus\{s\}) \times U : \alpha d(p,t) < d(s,t)\}.

Here ⊔\sqcup denotes disjoint union: the left vertex class is a copy of P∖{s}P \setminus\{s\} representing intermediate points, and the right vertex class is a copy of UU representing targets. The two copies of the same point are distinct vertices; in particular, (t,t)(t,t) joins the left copy of tt to its right copy.

The neighbors of a target tt in GUG_U are Bs(t)B_s(t), and the neighbors of an intermediate point pp are Ss(p)∩US_s(p) \cap U. Under (2), Claim 4.6 bounds both degrees by n/Djn/D_j. We access GUG_U implicitly. For each t∈Ut \in U, scan the stored points in nondecreasing order of distance from tt, stopping at the first point pp with αd(p,t)≥d(s,t)\alpha d(p,t) \ge d(s,t). The points preceding it are exactly Bs(t)B_s(t). To find Ss(p)∩US_s(p) \cap U, scan IQj∪Rj(p)I_{Q_j\cup R_j}(p) and retain the targets t∈Ut \in U satisfying αd(p,t)<d(s,t)\alpha d(p,t) < d(s,t).

Restricting the target set from UU to TT gives the sampled Set Cover instance, whose sets are Ss(p)∩TS_s(p) \cap T.

Definition 4.5 (Sampled incidence graph). For a sample T⊆UT \subseteq U, the sampled incidence graph GTG_T is the subgraph of GUG_U obtained by deleting the target vertices in U∖TU \setminus T and their incident edges. All left vertices are retained. It represents the Set Cover instance with universe TT and sets Ss(p)∩TS_s(p) \cap T.

Construct GTG_T explicitly by enumerating Bs(t)B_s(t) for each t∈Tt \in T and adding the edges (p,t)(p,t) for p∈Bs(t)p \in B_s(t). Write NGT(v)N_{G_T}(v) for the neighbors of a vertex vv. Here pp denotes a left vertex and tt a right vertex, so

NGT(p)=T∩Ss(p),NGT(t)=Bs(t)(t∈T).N_{G_T}(p) = T \cap S_s(p), \qquad N_{G_T}(t) = B_s(t) \quad(t \in T).

Each sampled target has at most n/Djn/D_j neighbors, so GTG_T has at most n∣T∣/Dj=O(nlog⁡n)n|T|/D_j = O(n \log n) edges.

Greedy and Validation Steps. After constructing GTG_T, the procedure has two steps. The greedy step (Lines 8–12) starts with S=∅S = \varnothing and Tunc=TT_{\mathrm{unc}} = T, where TuncT_{\mathrm{unc}} contains the sampled targets not yet covered by SS. While ∣S∣<Dj|S| < D_j and Tunc≠∅T_{\mathrm{unc}} \ne\varnothing, choose an intermediate point p≠sp \ne s maximizing ∣NGT(p)∩Tunc∣|N_{G_T}(p) \cap T_{\mathrm{unc}}|, resolving ties arbitrarily. Add pp to SS and remove its neighbors from TuncT_{\mathrm{unc}}. Every choice has positive gain: a target t∈Tunct \in T_{\mathrm{unc}} is covered by the intermediate point p=tp = t. Thus the selected intermediate points are distinct.

The validation step (Lines 13–17) computes the targets in UU covered by SS. Initialize C=∅C = \varnothing. For each p∈Sp \in S, scan IQj∪Rj(p)I_{Q_j\cup R_j}(p) and insert into CC every target t∈Ut \in U satisfying αd(p,t)<d(s,t)\alpha d(p,t) < d(s,t). Return (S,C)(S,C) if ∣C∣≥∣U∣/2|C| \ge|U|/2, and return ⊥\bot otherwise.

Algorithm 3: Cover⁡j(s,U)\operatorname{Cover}_j(s,U)

Input: Source s∈Ps \in P and nonempty U⊆P∖{s}U \subseteq P \setminus\{s\} satisfying (2) at stage jj.

Output: (S,C)(S,C) with ∣S∣≤Dj|S| \le D_j, C=U∩⋃p∈SSs(p)C = U \cap\bigcup_{p\in S} S_s(p), and ∣C∣≥∣U∣/2|C| \ge|U|/2; or ⊥\bot if the chosen points cover fewer than ∣U∣/2|U|/2 targets of UU.

  1. if ∣U∣≤256Djln⁡n|U| \le256D_j\ln n then

  2. T←UT \leftarrow U

  3. else

  4. Draw 256Djln⁡n256D_j\ln n targets uniformly without replacement from UU to form TT

  5. Initialize GTG_T with vertex set (P∖{s})⊔T(P \setminus\{s\}) \sqcup T and no edges

  6. foreach t∈Tt \in T do

  7. Enumerate Bs(t)B_s(t) and add (p,t)(p,t) to E(GT)E(G_T) for every p∈Bs(t)p \in B_s(t)

  8. S←∅S \leftarrow\varnothing; Tunc←TT_{\mathrm{unc}} \leftarrow T

  9. while ∣S∣<Dj|S| < D_j and Tunc≠∅T_{\mathrm{unc}} \ne\varnothing do

  10. Choose p∈P∖{s}p \in P \setminus\{s\} maximizing ∣NGT(p)∩Tunc∣|N_{G_T}(p) \cap T_{\mathrm{unc}}|

  11. S←S∪{p}S \leftarrow S \cup\{p\}

  12. Tunc←Tunc∖NGT(p)T_{\mathrm{unc}} \leftarrow T_{\mathrm{unc}} \setminus N_{G_T}(p)

  13. C←∅C \leftarrow\varnothing

  14. foreach p∈Sp \in S do

  15. C←C∪{t∈U∩IQj∪Rj(p):αd(p,t)<d(s,t)}C \leftarrow C \cup\{t \in U \cap I_{Q_j\cup R_j}(p) : \alpha d(p,t) < d(s,t)\}

  16. if ∣C∣≥∣U∣/2|C| \ge|U|/2 then return (S,C)(S,C)

  17. return ⊥\bot

The following claim shows how the pivot bounds support sampled incidence graph construction and exact validation.

Claim 4.6. For a source ss and a nonempty set U⊆P∖{s}U \subseteq P \setminus\{s\} satisfying (2) at stage jj,

∣Bs(t)∣≤n/Dj(t∈U),U∩Ss(p)⊆IQj∪Rj(p)(p∈P∖{s}),∣IQj∪Rj(p)∣≤n/Dj(p∈P∖{s}).\begin{aligned} |B_s(t)| &\le n/D_j && (t \in U),\\ U \cap S_s(p) &\subseteq I_{Q_j\cup R_j}(p) && (p \in P \setminus\{s\}),\\ |I_{Q_j\cup R_j}(p)| &\le n/D_j && (p \in P \setminus\{s\}). \end{aligned}

For each t∈Ut \in U, Bs(t)B_s(t) can be enumerated in O(n/Dj)O(n/D_j) time using the stored distance order around tt.

Proof. If p∈Bs(t)p \in B_s(t) for t∈Ut \in U, then

d(p,t)<d(s,t)/α≤μQj∪Rj(t).d(p,t) < d(s,t)/\alpha\le\mu_{Q_j\cup R_j}(t).

Thus Bs(t)⊆{p∈P:d(p,t)<μQj∪Rj(t)}B_s(t) \subseteq\{p \in P : d(p,t) < \mu_{Q_j\cup R_j}(t)\} and t∈IQj∪Rj(p)t \in I_{Q_j\cup R_j}(p). Lemma 4.3 bounds both the set of intermediate points and the list by n/Djn/D_j. To enumerate Bs(t)B_s(t), scan the stored distance order around tt until the first point pp satisfying αd(p,t)≥d(s,t)\alpha d(p,t) \ge d(s,t). This takes at most ∣Bs(t)∣+1=O(n/Dj)|B_s(t)| + 1 = O(n/D_j) comparisons.

Lemma 4.7. Algorithm 3 returns either ⊥\perp or a pair (S,C)(S,C) satisfying

∣S∣≤Dj,C=U∩⋃p∈SSs(p),∣C∣≥∣U∣/2.|S| \le D_j,\qquad C = U \cap\bigcup_{p\in S} S_s(p),\qquad|C| \ge|U|/2.

It runs in O(nlog⁡n)O(n\log n) time.

Proof. The greedy step chooses at most DjD_j intermediate points. By Claim 4.6, every target in UU covered by a chosen point p∈Sp \in S lies in IOj∪Rj(p)I_{O_j\cup R_j}(p). Filtering this list by membership in UU and the navigation inequality finds exactly Ss(p)∩US_s(p) \cap U. The validation step therefore computes the stated set CC and returns it only if ∣C∣≥∣U∣/2|C| \ge|U|/2.

For each sampled target, Claim 4.6 enumerates its neighbors in O(n/Dj)O(n/D_j) time. Since ∣T∣=O(Djlog⁡n)|T| = O(D_j\log n), constructing GTG_T takes O(n+n∣T∣/Dj)=O(nlog⁡n)O(n+n|T|/D_j)=O(n\log n) time. For the greedy step, maintain only unselected intermediate points in buckets indexed by their current gains ∣NGT(p)∩Tun∣|N_{G_T}(p) \cap T_{\mathrm{un}}|. 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 O(n+∣E(GT)∣)=O(nlog⁡n)O(n+|E(G_T)|)=O(n\log n) time as well.

Using Boolean arrays for membership tests, validation takes O(Dj⋅n/Dj)=O(n)O(D_j\cdot n/D_j)=O(n) time. All other operations take O(n)O(n) time, so the total running time is O(nlog⁡n)O(n\log n).

Lemma 4.8. If Dj≥ksD_j \ge k_s, the set SS chosen by the greedy step satisfies

∣⋃p∈SNGT(p)∣≥(1−e−1)∣T∣>5∣T∣/8.\left|\bigcup_{p\in S}N_{G_T}(p)\right| \ge(1-e^{-1})|T| > 5|T|/8.

Proof. An optimum set of ksk_s outgoing neighbors covers every target in UU, so its neighborhoods in GTG_T cover TT. Lemma 3.1 guarantees coverage of at least (1−e−1)∣T∣(1-e^{-1})|T| targets after at most ksk_s greedy choices. Since Dj≥ksD_j \ge k_s, the final greedy set SS achieves at least this coverage.

Lemma 4.9. If Dj≥ksD_j \ge k_s, then Cover⁡j(s,U)\operatorname{Cover}_j(s,U) returns a pair (S,C)(S,C) with probability at least 1−n−61-n^{-6}. If T=UT=U, the call succeeds deterministically.

Proof. We use a standard sampling argument [15, 13]. Fix all random choices made before this execution of Cover⁡j(s,U)\operatorname{Cover}_j(s,U). With probability at least 1−n−61-n^{-6}, every choice of at most DjD_j intermediate points that covers at least 5/85/8 of TT also covers at least half of UU. We prove this guarantee for all such sets on the same sample TT, so it also applies to the set chosen by greedy after observing TT.

If T=UT=U, Lemma 4.8 guarantees coverage of more than ∣U∣/2|U|/2 targets, so validation succeeds. Suppose T≠UT\ne U. Before drawing TT, fix a set S⊆P∖{s}S\subseteq P\setminus\{s\} with ∣S∣≤Dj|S|\le D_j, and let

CS=U∩⋃p∈SSs(p)C_S = U \cap\bigcup_{p\in S} S_s(p)

be the targets it covers. Suppose ∣CS∣<∣U∣/2|C_S|<|U|/2. If ∣T∩CS∣≥5∣T∣/8|T\cap C_S|\ge5|T|/8, the fraction of targets covered by SS in TT exceeds that in UU by more than 1/81/8. Applying Lemma 3.2 to the indicators 1{t∈CS}\mathbf{1}_{\{t\in C_S\}}, t∈Ut\in U, with η=1/8\eta=1/8 gives

P[∣T∩CS∣≥5∣T∣/8]≤P[∣∣T∩CS∣∣T∣−∣CS∣∣U∣∣≥18]≤e−2∣T∣(1/8)2=e−∣T∣/32.\mathbb{P}\left[|T\cap C_S|\ge5|T|/8\right] \le \mathbb{P}\left[ \left|\frac{|T\cap C_S|}{|T|}-\frac{|C_S|}{|U|}\right|\ge\frac{1}{8} \right] \le e^{-2|T|(1/8)^2}=e^{-|T|/32}.

There are at most nDjn^{D_j} sets SS of size at most DjD_j. A union bound therefore bounds the probability of any such event by

nDjexp⁡(−∣T∣/32)≤nDjexp⁡(−8Djln⁡n)=n−7Dj≤n−6,n^{D_j}\exp(-|T|/32) \le n^{D_j}\exp(-8D_j\ln n) = n^{-7D_j} \le n^{-6},

since ∣T∣=256Djln⁡n|T| = 256D_j\ln n and Dj≥1D_j \ge1.

By Lemma 4.8, the greedy set SS covers more than 5∣T∣/85|T|/8 sampled targets, and ∣S∣≤Dj|S| \le D_j. The guarantee applies to SS even though it depends on TT. Hence ∣C∣≥∣U∣/2|C| \ge|U|/2 with probability at least 1−n−61 - n^{-6}, and the validation step returns (S,C)(S, C).

The Complete Construction

Algorithm 4, ConstructGraph(P,d,α)(P,d,\alpha), takes the distance matrix of (P,d)(P,d) and α≥1\alpha\ge1. If ∣P∣≤1|P| \le1, it returns (P,∅)(P,\varnothing). 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 Ns=Neighbors⁡(s)N_s = \operatorname{Neighbors}(s) for each s∈Ps \in P and returns the graph with edges (s,p)(s,p) for p∈Nsp \in N_s.

Algorithm 4: ConstructGraph(P,d,α)(P,d,\alpha)

Input: Metric (P,d)(P,d) given by its distance matrix and α≥1\alpha\ge1.

Output: An α\alpha-navigable graph on PP.

  1. if ∣P∣≤1|P| \le1 then return (P,∅)(P,\varnothing)

  2. Set the degree estimates and stages by (1)

  3. Sort and store the distance order around each target using the fixed tie-breaking order

  4. for j←0j \leftarrow0 to ℓ\ell do

  5. &nbsp;&nbsp;&nbsp;&nbsp;Apply Lemma 4.3 with degree estimate DjD_j to construct QjQ_j, RjR_j, μQj∪Rj\mu_{Q_j\cup R_j}, and all IQj∪Rj(p)I_{Q_j\cup R_j}(p)

  6. E←∅E \leftarrow\varnothing

  7. foreach s∈Ps \in P do

  8. &nbsp;&nbsp;&nbsp;&nbsp;Ns←Neighbors⁡(s)N_s \leftarrow\operatorname{Neighbors}(s)

  9. &nbsp;&nbsp;&nbsp;&nbsp;Add (s,p)(s,p) to EE for each p∈Nsp \in N_s

  10. return (P,E)(P,E)

For a fixed source ss, the procedure Neighbors⁡(s)\operatorname{Neighbors}(s) in Algorithm 5 maintains its chosen outgoing neighbors NN and its uncovered targets UU. Initialize N=∅N = \varnothing and U=P∖{s}U = P \setminus\{s\}, and process stages j=0,…,ℓj = 0,\ldots,\ell in order. At stage jj, it adds (Qj∪Rj)∖{s}(Q_j \cup R_j) \setminus\{s\} to NN and removes the targets covered by these pivots using μQj∪Rj\mu_{Q_j\cup R_j}.

While UU is nonempty, call Cover⁡j(s,U)\operatorname{Cover}_j(s,U). If a pair (S,C)(S,C) is returned, it adds SS to NN, removes CC from UU, and continues at the same stage. If ⊥\perp is returned, it proceeds to the next stage without changing NN or UU. The procedure returns NN when UU becomes empty. Lemma 4.10 shows that this happens by stage ℓ\ell.

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 N⊆P∖{s}N \subseteq P \setminus\{s\} satisfying

⋃p∈NSs(p)=P∖{s}.\bigcup_{p\in N} S_s(p) = P \setminus\{s\}.

Consequently, every graph returned by Algorithm 4 is α\alpha-navigable.

Proof. We show that Neighbors(ss) maintains

U=(P∖{s})∖⋃p∈NSs(p).U = (P \setminus\{s\}) \setminus\bigcup_{p\in N} S_s(p).

The equality holds initially.

At stage jj, a target t∈Ut \in U is covered by the pivot edges exactly when αμQj∪Rj(t)<d(s,t)\alpha\mu_{Q_j\cup R_j}(t) < d(s,t). Excluding ss from the pivot neighbors does not affect this test, since αd(s,t)≥d(s,t)\alpha d(s,t) \ge d(s,t). Previously covered targets remain covered because NN only grows. Thus adding the pivots and filtering UU preserves the equality and establishes (2).

By Lemma 4.7, the returned set SS covers exactly the targets in CC within the current UU. The updates N←N∪SN \leftarrow N \cup S and U←U∖CU \leftarrow U \setminus C therefore preserve the equality. A return of ⊥\bot changes neither set.

Every successful call reduces ∣U∣|U| by at least half, and the first failed call exits its stage. At the last stage, Dℓ=n−1D_\ell= n - 1 and the construction sets Qℓ=PQ_\ell= P. Adding these pivots makes U=∅U = \varnothing. The procedure therefore terminates with the claimed coverage. □

Lemma 4.11. For every outcome of the random choices, Neighbors(ss) processes O(log⁡n)O(\log n) stages and makes O(log⁡n)O(\log n) calls to Cover⁡j(s,U)\operatorname{Cover}_j(s,U).

Proof. The degree estimates double until reaching n−1n - 1, giving O(log⁡n)O(\log n) stages. Each successful call halves the number of uncovered targets, and adding pivots can only decrease it further. Hence at most 1+log⁡(n−1)1 + \log(n - 1) 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 O(log⁡n)O(\log n). □

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 1−n−41-n^{-4}, the neighborhoods NsN_s returned by Neighbors(s)(s) satisfy ∣Ns∣=O(kslog⁡n)|N_s|=O(k_s\log n) simultaneously for all s∈Ps\in P.

Proof. Fix all pivot sets constructed by Algorithm 4. All probabilities below are over the fresh samples drawn by Cover⁡j\operatorname{Cover}_j. For each source ss, let jj be the first stage with Dj≥ksD_j\ge k_s. Since D0=1≤ks≤DℓD_0=1\le k_s\le D_\ell and each estimate is at most twice the preceding one, this stage exists and satisfies ks≤Dj<2ksk_s\le D_j<2k_s.

At this stage, the source makes at most nn calls: each successful call removes at least one target, and a return of ⊥\perp exits the stage. For each r=1,…,nr=1,\ldots,n, condition on the random choices preceding the rr-th call, if it occurs. Since Dj≥ksD_j\ge k_s, Lemma 4.9 bounds its conditional probability of returning ⊥\perp by n−6n^{-6}. Averaging over the preceding choices, the probability that this call occurs and returns ⊥\perp is therefore at most n−6n^{-6}. A union bound over all nn sources and nn possible call indices per source shows that, with probability at least 1−n−41-n^{-4}, no call at a source’s first stage with Dj≥ksD_j\ge k_s returns ⊥\perp. On this event, every source finishes at that stage or earlier.

Fix a source ss and assume this simultaneous event holds. At every visited stage i≤ji\le j, each successful call adds at most Di≤Dj<2ksD_i\le D_j<2k_s neighbors. By Lemma 4.11, there are O(log⁡n)O(\log n) such calls, so the greedy choices contribute O(kslog⁡n)O(k_s\log n) neighbors. Since the estimates preceding DjD_j are distinct powers of two smaller than DjD_j, we have ∑i=0jDi=O(ks)\sum_{i=0}^{j}D_i=O(k_s). The pivots contribute at most

∑i=0j∣Qi∪Ri∣≤24log⁡n∑i=0jDi=O(kslog⁡n).\sum_{i=0}^{j}|Q_i\cup R_i|\le24\log n\sum_{i=0}^{j}D_i=O(k_s\log n).

Adding the two contributions proves the claim.

Running Time

Lemma 4.13. Algorithm 4 runs in O(n2log⁡2n)O(n^2\log^2 n) time with probability at least 1−2n−61-2n^{-6}. The same bound holds in expectation.

Proof. For each source, Lemmas 4.11 and 4.7 bound the time spent in Cover⁡j\operatorname{Cover}_j by O(nlog⁡2n)O(n\log^2 n). Adding pivots and updating UU take O(n)O(n) time per stage or call. Processing all sources therefore takes O(n2log⁡2n)O(n^2\log^2 n) time for every outcome of the random choices.

Sorting the distance orders takes O(n2log⁡n)O(n^2\log n) time. There is one pivot construction for each of the ℓ+1=O(log⁡n)\ell+1=O(\log n) stages. By Lemma 4.3 and a union bound over ℓ+1≤n\ell+1\le n stages, all pivot constructions together take O(n2log⁡2n)O(n^2\log^2 n) time with probability at least 1−2n−61-2n^{-6}. The same bound holds in expectation by the expected-time bounds proved for the pivot constructions.

Proof of Theorem 1.2. Exact α\alpha-navigability follows from Lemma 4.10. Summing the outdegree bounds of Lemma 4.12 gives ∣E∣=O(log⁡n)∑sks=O(log⁡n)OPT⁡α|E|=O(\log n)\sum_s k_s=O(\log n)\operatorname{OPT}_{\alpha}. Lemma 4.13 provides the running-time bounds. The space usage is O(n2)O(n^2), since the stored pivot lists have total size O(∑j=0ℓn2/Dj)=O(n2)O(\sum_{j=0}^{\ell}n^2/D_j)=O(n^2) 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

n−4+2n−6<n−2.n^{-4}+2n^{-6}<n^{-2}.

Disclosure of AI Use

ActivityAI used
Asking the research questionNo
Coming up with the approachYes
Proof developmentYes
Writing and expositionYes
Checking for bugsYes
Other supporting tasksYes

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 QQ together with sampling techniques from streaming Set Cover. Building on these ideas, GPT-6.1 Sol proposed using adaptive sampling to construct RR and completed the algorithm, analysis, and proofs. The construction of RR 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

  1. [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
  2. [4]Pratyush Avi and Christopher Musco. Almost navigable graphs. VecDB Workshop at VLDB 2026, 2026.arxiv.org/abs/2607.14564
  3. [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
  4. [6][CZ27] Hongyi Chen and Tianyi Zhang. Bicriteria approximate navigable graphs in general metrics. In Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2027. To appear. arXiv:2610.34302.arxiv.org/abs/2610.34302
  5. [7][DGM+24] Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, pages 59513–59531, 2024.arxiv.org/abs/2405.18680
  6. [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
  7. [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
  8. [12][Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.
  9. [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.
  10. [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.
  11. [15][HPS11] Sariel Har-Peled and Micha Sharir. Relative (p, ε)-approximations in geometry. Discrete & Computational Geometry, 45(3):462–496, 2011.DOI
  12. [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
  13. [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
  14. [18]Sanjeev Khanna, Ashwin Padaki, and Erik Waingarten. Sparse navigable graphs for nearest neighbor search: Algorithms and hardness. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1606–1630. Society for Industrial and Applied Mathematics, 2026.arxiv.org/abs/2507.14060
  15. [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
  16. [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.
  17. [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
  18. [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
  19. [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
  20. [26]Tomer Waizer and Yoav Danieli. The price of almost navigability, 2026. arXiv:2609.02498.arxiv.org/abs/2609.02498

Paper details

vlnc:W_tmmcxuvx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents