Source-linked AI summary
Bicriteria Approximate Navigable Graphs in General Metrics
Hongyi Chen, Tianyi Zhang
TL;DR
Sparse navigable graphs seek to minimize edges while supporting progress toward every target, but the single-criterion problem has a Set Cover approximation barrier. The paper uses shared representatives to build near-quadratic-time graphs with two bicriteria guarantees, and shows the 2α threshold is essentially tight.
Problem
The goal is to minimize edges in α-navigable graphs in general metrics, where Set Cover gives O(log n) approximations but makes o(log n) approximations NP-hard.
Source: §1 · p. 2Method
The algorithm builds α-navigable graphs using globally shared representatives across hierarchical distance-scale covers, with separate constructions for the two guarantees.
Source: §1.2 · p. 5Results
In ~O(n^2 log Δ) time, the algorithm gives a (α, 2α + 8 + 4/α)-bicriteria 5-approximation and a (α, α + 5 + 2/α)-bicriteria O(log n)-approximation.
Source: §1.1 · p. 3Takeaways & Limitations
For every constant η in (0, 1), an (α, 2α − η)-bicriteria o(log n)-approximation is NP-hard, making the 2α threshold essentially tight.
Source: §1.1 · p. 3The work focuses on large α; greedy-search nearest-neighbor guarantees for the often-used smaller values remain poorly understood and outside its scope.
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $\alpha\ge 1$, an $\alpha$-navigable graph is a directed graph $G=(P,E)$ such that for every ordered pair of distinct points $s,t\in P$, the vertex $s$ has an outgoing edge $(s,p)$ with $d(p,t)<d(s,t)/\alpha$. The objective is to minimize the number of edges. Approximation algorithms for this problem were recently studied by Khanna, Padaki, and Waingarten (SODA 2026), and independently by Conway et al. (SODA 2026). These works show that the single-criterion problem faces a Set Cover barrier: an $O(\log n)$-approximation is achievable, whereas obtaining an $o(\log n)$-approximation is NP-hard. To obtain faster algorithms, Khanna, Padaki, and Waingarten introduced bicriteria approximation, in which the output graph is required to be $\alpha$-navigable, while its size is compared against that of an optimal $\beta$-navigable graph for some relaxed parameter $\beta \ge \alpha$. They gave a fast matrix-multiplication-based algorithm that computes an $(\alpha,2(1+\varepsilon)\alpha)$-bicriteria $O(\log n)$-approximation in time $\widetilde O(n^\omega \log \Delta/\varepsilon)$, where $\Delta$ denotes the aspect ratio and $\omega$ is the matrix multiplication exponent. Our main result is a simpler near-quadratic-time algorithm with stronger bicriteria guarantees. For every constant $\alpha\ge 1$, we compute in time $\widetilde O(n^2\log\Delta)$ an $\alpha$-navigable graph that is simultaneously an $(\alpha,2\alpha+O(1))$-bicriteria $O(1)$-approximation and an $(\alpha,\alpha+O(1))$-bicriteria $O(\log n)$-approximation. We complement the algorithm with a hardness result showing that for every constant $\eta\in(0,1)$, no polynomial-time algorithm can compute an $(\alpha,2\alpha-\eta)$-bicriteria $o(\log n)$-approximation unless $P=NP$.
1 Introduction.
The paper studies sparse navigable graphs in general metrics and gives a near-quadratic construction with two simultaneous bicriteria guarantees. Its technical overview explains how shared representatives yield navigation while supporting different bounds on graph size.
1 Introduction.
- The objective is an instance-sparse α-navigable graph; prior work established an O(log n) approximation and Set Cover-based hardness of o(log n)-approximations.Earlier bicriteria work left open whether an O(log n)-approximation could be obtained in quadratic time.Source: §1 · pp. 2–3
1.1 Our Results.
- In ~O(n^2 log Δ) time, the algorithm gives a (α, 2α + 8 + 4/α)-bicriteria 5-approximation and a (α, α + 5 + 2/α)-bicriteria O(log n)-approximation.Both guarantees apply to the same α-navigable output graph.Source: §1.1 · p. 3
- For every constant α ≥ 1 and η ∈ (0, 1), some constant cη > 0 makes it NP-hard to compute a (α, 2α − η)-bicriteria cη ln n-approximation for sparsest α-navigable graphs on n-point metrics.Below 2α, an o(log n)-approximation remains NP-hard.Source: §1.1 · p. 3
1.2 Technical Overview.
- A source-wise ordered-greedy warm-up uses no more outgoing edges than any 2α-navigable graph, but its direct implementation takes O(n^3) time.It processes targets in nondecreasing distance from the source and adds an edge when no earlier edge navigates to the target.Source: §1.2 · p. 5
- The algorithm uses shared representatives from hierarchical covers across distance scales, with balls of radius Θ(ri/α) chosen to ensure α-navigation.Centers covering targets at a scale are selected as out-neighbors of sources in an appropriate annulus.Source: §1.2 · p. 5
- For the constant-factor bound, separated covers let the selected centers map injectively at each scale to edges of a sparse (2α + O(1))-navigable graph.Each comparison edge is used by these maps at only constantly many scales.Source: §1.2 · p. 6
- For the logarithmic bound, greedy Set Cover selects centers for local instances, whose optima are bounded by edges in a sparse (α + O(1))-navigable graph.Each outgoing edge is counted at only constantly many scales.Source: §1.2 · p. 6
- Running both constructions and returning the smaller graph preserves α-navigation and both bicriteria bounds.Each candidate graph is α-navigable, and the returned graph is no larger than either one.Source: §1.2 · p. 6
2 Bicriteria Approximation in Near-Quadratic Time.
This section develops near-quadratic constructions of α-navigable graphs using separated or greedy ball covers, with constant- and logarithmic-factor bicriteria guarantees for fixed α. It bounds the logarithmic construction and combines it with the constant-factor construction by returning the smaller graph, preserving both guarantees.
2.1 Algorithm Description.
- At each level, the construction connects each source to cover centers in its annulus, using separated covers for the constant approximation and greedy set cover for the logarithmic one.The separated cover has clusters contained in radius-r balls with pairwise-separated centers; the greedy routine covers the point set with radius-r balls.Source: §2.1 · pp. 6–7
2.2 Running Time.
- For fixed α, both algorithms run in ˜O(n^2 log ∆) time.They compute O(α log ∆) level covers, then construct edges by checking sources and selected centers against each level’s annulus.Source: §2.2 · pp. 7–8
2.3 Proof of Correctness.
- Both constructions produce α-navigable graphs: for every distinct source-target pair, a level-cover center yields an outgoing edge that makes progress toward the target.The proof selects a level covering the source-target distance, places the target in a covered cluster, and shows its center lies in the source’s annulus.Source: §2.3 · p. 9
2.4 Constant Bicriteria Approximation.
- Summing over all sources s ∈ P yields an edge set E satisfying |E| ≤ 5|E⋆|, so its size is at most five times |E⋆|.Source: §2.4 · p. 11
2.5 Logarithmic Bicriteria Approximation.
- The greedy-cover construction is an (α,β′)-bicriteria 8(ln n + 1)-approximation.The stated relaxed parameter is β′ = (1 + δ)(α + 2) + 2.Source: §2.5 · p. 11
- The logarithmic construction satisfies |E| ≤ 8(ln n + 1)|E⋆|.Source: §2.5 · p. 14
2.6 Combining the Two Constructions.
- The algorithm runs both constructions and returns the smaller graph; since both are α-navigable, the output is also α-navigable.Source: §2.6 · p. 14
- The combined construction is an (α, 2α + 8 + 4/α)-bicriteria 5-approximation and an (α, α + 5 + 2/α)-bicriteria O(ln n)-approximation.Source: §2.6 · p. 14
- Its running time is ˜O(αn^2 log ∆), which is ˜O(n^2 log ∆) for constant α.Source: §2.6 · p. 14
3 Hardness Proof.
The proof reduces Set Cover to approximating α-navigable graphs with bicriteria parameter 2α −η. A graph returned by such an approximation would yield a comparably small Set Cover, contradicting Set Cover hardness at logarithmic approximation ratios.
Hardness Proof
- The construction makes K copies of a Set Cover instance, each with a hub, set vertices, and element vertices, and uses unit-weight hub-to-set and set-element incidence edges.Every pair of points in different copies is joined by an edge of weight 2α; the metric is the graph's shortest-path metric.Source: §3 · pp. 14–15, Figure 1 · p. 15
- For a selected source s and copy j, the out-neighbor sets Vs,j ∩Fj cover every element in Uj \ Vs,j.An uncovered element must be within distance strictly less than 2 of a set vertex containing it, by α-navigability and the cross-copy distance 2α.Source: §3 · p. 15
- Adding one containing set for each element in Uj ∩Vs,j completes a cover of the original instance with size at most |Vs,j|.The selected copy's completed cover is bounded by the number of out-neighbors in Fj ∪Uj.Source: §3 · p. 15
- G⋆ is (2α − η)-navigable, with direct directed edges between distinct points in each copy and edges from each point to other-copy hubs and every point in C⋆.The edge count is |E⋆| = K(K − 1)(m + n + 1)(|C⋆| + 1) + K(m + n + 1)(m + n).Source: §3 · p. 16
- No polynomial-time (α, 2α −η)-bicriteria cη ln N-approximation exists unless P = NP, for cη = 1/(10d).The reduction uses hard Set Cover instances with m ≤ nd for constant d.Source: §3 · pp. 14, 17
Disclosure of AI Use.
The authors report using ChatGPT to refine the manuscript's exposition and to check technical arguments. They state that the authors reviewed and finalized the mathematical claims, proofs, and text and take responsibility for the final paper.
Disclosure of AI Use
- ChatGPT was used to refine the manuscript's exposition and presentation after the authors wrote an initial draft.Source: Disclosure of AI Use · p. 17
- ChatGPT was used to check technical arguments and helped identify a bug in an earlier version of Section 2.5.Source: Disclosure of AI Use · p. 17
- The authors reviewed and finalized all mathematical claims, proofs, and text, and take full responsibility for the final paper.Source: Disclosure of AI Use · p. 17