CS Paper Radar

Navigable Graphs for Low-Dimensional Hyperbolic Spaces

Chengyuan Deng, Jie Gao, Kuijun Liu, Kevin Lu, Feng Luo, Puheng Weng, Cheng Xin

cs.DS cs.CG ·submitted 2026-10-17 21:22 UTC · v1
theory

Abstract

A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy routing always reaches the destination. Existing work on sparse navigable graphs mostly assumes bounded doubling dimensions. In this paper, we show that constant-dimensional hyperbolic spaces that do not have bounded doubling dimension also admit sparse navigable graphs. Specifically, for an $n$-point set in $\mathbb H^k$ with a constant $k$, we construct a navigable graph of size $O_k(n)$ with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every $n$-point set in $\mathbb H^k$ admits a navigable graph on the input points alone with $O_k(n)$ edges, though a single vertex may have out-degree $Ω(n)$. Furthermore, with a refined construction with $O_k(n\log n)$ edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected $O(\log ^2 n)$ in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by $O_k(\log n)$. We complement these upper bounds with matching lower bound results. In the hyperbolic plane, there are point sets for which every navigable graph requires maximum out-degree $Ω(n)$, so the maximum linear out-degree above is unavoidable and constant out-degree is only possible with Steiner points. Next, we show that for every constant $α>1$, an $α$-navigable graph may require $Ω(n^2)$ edges, which rules out the standard route of using $α$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $Ω(\log n)$, there are point sets for which every navigable graph may require $n^{3/2-o(1)}$ edges, matching the upper bounds for general metrics.

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly Optimal Sparse Navigable Graphs in General Metrics

cs.DS ·2026-10-29 ·Hongyi Chen, Tianyi Zhang
similarity 0.67
Abstract · 24 pages, 3 figures

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

0.20

Hyperbolic Sphericity

cs.CG ·2026-10-01 ·Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt
similarity 0.64
Abstract

The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studied in Euclidean space, we initiate the study of hyperbolic sphericity. The hyperbolic sphericity of a graph can be significantly smaller than its Euclidean counterpart, but, contrary to the Euclidean setting, depends strongly on the radius of the balls. We show that, if the radius of the balls can be chosen depending on the graph, the hyperbolic sphericity is upper bounded by the Euclidean sphericity. This extends a previous result for 2-dimensional hyperbolic space, i.e., uniform disk graphs, to arbitrary dimensions. Moreover, our proof is significantly simpler. If we fix the radius, i.e., do not make it dependent on the graph, we show that hyperbolic sphericity can be larger than Euclidean sphericity, but by at most 1. Additionally, we study how hyperbolic sphericity changes with the ball radius. We show that choosing a larger radius can substantially decrease the sphericity while increasing it by at most 1. We also provide a construction of a graph where the sphericity oscillates between different values as the radius increases. Besides being theoretically interesting, we note that these results are relevant for graph embeddings in machine learning, where one is interested in low-dimensional numeric representations of symbolic data like graphs.

0.28

Fast Sparse $α$-Navigable Graph Construction with Improved Resource Augmentation

cs.DS ·2026-10-28 ·Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Ben Landrum, Christopher Musco +3 more
top venue similarity 0.64
Abstract · 26 pages. To appear in SODA 2027

Graph-based nearest neighbor search methods, which run greedy search on a directed graph over the data points, have surged in popularity in recent years. A common goal is to construct a search graph with the $α$-navigability property, which ensures that greedy search returns provably good approximate nearest neighbors and converges in few iterations. Increasing $α\geq 1$ improves accuracy and convergence rate, but requires more edges, which increases both space and search time. This tradeoff has motivated the study of algorithms for constructing a sparsest $α$-navigable graph for a given set of points. For any point set and any distance function, we show how to compute an $α$-navigable graph with at most $O(\log n)$ times as many edges as the sparsest $(1+\varepsilon)α$-navigable graph, in $O(n^ω\log(Δ)/\varepsilon)$ time, where $ω< 2.372$ is the matrix multiplication exponent and $Δ$ is the aspect ratio of the input. This improves on Khanna, Padaki, and Waingarten (SODA 2026), who achieve the same runtime but are only competitive with the sparsest $2(1+\varepsilon)α$-navigable graph. Since sparsity often increases rapidly with $α$ (typically $α\leq 1.1$), their bound can be significantly weaker. Previously, the best algorithm competing with the sparsest $(1+\varepsilon)α$-navigable graph required $\widetilde{O}(n^{2.5})$ time. Our techniques also extend to constructing sparse $τ$-monotonic graphs, another popular target in nearest neighbor search. Finally, we give a fine-grained complexity analysis suggesting that improving the $O(n^ω)$ running time is unlikely, or would require a very different approach. It is based on hardness results for problems related to verifying whether a graph is navigable, a topic of independent interest.

0.37

Bicriteria Approximate Navigable Graphs in General Metrics

cs.DS ·2026-10-25 ·Hongyi Chen, Tianyi Zhang
top venue similarity 0.64
Abstract · To appear in SODA 2027

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge 1$, an $α$-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)/α$. 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 $α$-navigable, while its size is compared against that of an optimal $β$-navigable graph for some relaxed parameter $β\ge α$. They gave a fast matrix-multiplication-based algorithm that computes an $(α,2(1+\varepsilon)α)$-bicriteria $O(\log n)$-approximation in time $\widetilde O(n^ω\log Δ/\varepsilon)$, where $Δ$ denotes the aspect ratio and $ω$ is the matrix multiplication exponent. Our main result is a simpler near-quadratic-time algorithm with stronger bicriteria guarantees. For every constant $α\ge 1$, we compute in time $\widetilde O(n^2\logΔ)$ an $α$-navigable graph that is simultaneously an $(α,2α+O(1))$-bicriteria $O(1)$-approximation and an $(α,α+O(1))$-bicriteria $O(\log n)$-approximation. We complement the algorithm with a hardness result showing that for every constant $η\in(0,1)$, no polynomial-time algorithm can compute an $(α,2α-η)$-bicriteria $o(\log n)$-approximation unless $P=NP$.

0.34

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

cs.CG ·2026-10-01 ·Eunku Park
theory similarity 0.61
Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

0.37

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.61
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Revisiting the directed pathwidth of h-semicomplete digraphs

cs.DS math.CO ·2026-10-30 ·Guilherme C. M. Gomes, Raul Lopes, Matthias Mnich
similarity 0.61
Abstract

A digraph is $h$-semicomplete if every vertex has at most $h$ non-neighbors. In semicomplete digraphs, $k$-triples are obstructions to bounded directed pathwidth with many algorithmic applications: Fradkin and Seymour [JCTB 2013] showed that a large triple contains a subdivision of every small digraph, and triples were used for irrelevant vertex arguments in routing problems by Fomin and Pilipczuk [JCTB 2019] and Gomes, Lopes, and Sau [ICALP 2025]. Fradkin and Seymour also showed that there is a function $f(k)$ such that every semicomplete digraph of directed pathwidth at least $f(k)$ contains a $k$-triple, and their proof gives $f(k)$ triply exponential in $k$. For $h$-semicomplete digraphs, a result of Kitsunai et al. [ESA 2015] also yields a $k$-triple, but only existentially, and finding one in fixed-parameter time remained open. We improve the bound on $f(k)$ to a single exponential and extend the result to $h$-semicomplete digraphs: we show that every $h$-semicomplete digraph of directed pathwidth greater than $(h+1) \cdot k \cdot 2^{27k+9}$ contains a $k$-triple, which we find in polynomial time, and no bound subexponential in $k$ or sublinear in $h$ is possible. We also extend the approximation algorithm for directed pathwidth of Fomin and Pilipczuk to $h$-semicomplete digraphs, so its certificates of large directed pathwidth remain valid. Our proof is much shorter than the analysis of Kitsunai et al., and while their algorithm is exact, ours runs in polynomial time. As an application, we show that Arc-Disjoint Paths on $h$-semicomplete digraphs is fixed-parameter tractable parameterized by the number of paths and $h$, generalizing the semicomplete case. Finally, unlike in semicomplete digraphs, directed pathwidth does not bound directed cliquewidth: for every $k$, some acyclic $1$-semicomplete digraph, so of directed pathwidth zero, has directed cliquewidth at least $k$.

0.25

Improved Lower Bound for Steiner Point Removal

cs.DS ·2026-09-16 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen, Weihao Zhu
theory similarity 0.59
Abstract

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $Ω\left(\sqrt{\frac{\log |T|}{\log\log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $Ω(\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.

0.18