CS Paper Radar

The Price of Almost Navigability

Tomer Waizer, Yoav Danieli

cs.DS ·submitted 2026-09-02 12:05 UTC · v1
theory

Abstract

Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $Ω(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-ε)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $ε$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/ε)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $ε$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $ε$, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $Ω(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.

Closest papers

Nearest neighbours by meaning across the whole index.

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.72
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.71
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

Nearly Optimal Sparse Navigable Graphs in General Metrics

cs.DS ·2026-10-29 ·Hongyi Chen, Tianyi Zhang
similarity 0.70
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

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.68
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.68
Abstract

We study the online graph exploration problem, in which an agent must visit every vertex of an initially unknown weighted graph on $n$ vertices and return to its starting vertex. In this model, a vertex's incident edges and their weights are revealed when it is first visited. Despite extensive research, the best known competitive guarantee for general graphs had remained $\mathcal{O}(\log n)$, a bound already established in 1977 for the greedy TSP heuristic Nearest Neighbor. Subsequent approaches, including hierarchical depth-first search (hDFS) and Blocking, achieve better guarantees on restricted graph classes but have logarithmic or worse competitive ratios on general graphs. This raises the question of whether the logarithmic barrier is inherent and Nearest Neighbor is asymptotically optimal. We answer this question in the negative by giving an $\mathcal{O}(\log n/\log \log n)$-competitive algorithm. Our algorithm is a slight modification of hDFS, and we establish its competitive guarantee with a surprisingly short proof.

0.22

Optimal Non-Adaptive Vantage Point Selection

cs.DS ·2026-09-09 ·Jie Gao, Nicole Wein, Chang Wu
theory similarity 0.67
Abstract

We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$

0.23

Query Complexity of Densest Sub(hyper)graph Problems

cs.DS cs.CC ·2026-10-13 ·Sinan G. Aksoy, Eli Friedman, Nate Veldt, Stephen J. Young
theory similarity 0.66
Abstract · 26 pages

Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries. In this work, we examine the query complexity of densest subgraph problems. Our first contribution is to generalize the uniform sparsification approach for Densest Subgraph and other heavy subgraph problems to weighted graphs, achieving the following results. >A $(1+\varepsilon)$-approximation for weighted Densest Subgraph in $O(n\log^2 n/\varepsilon^2)$ queries, roughly matching the $Ω(n/\log n)$ lower bound we prove for randomized algorithms. >A $(1+\varepsilon)$-approximation for weighted Max Cut in $O(n\log^2 n/\varepsilon^2)$ queries. This improves upon the bound of $O(n\log^3 n(\log n+1/\varepsilon^2))$ queries achieved by Plevrakis et al., making significant progress towards their lower bound of $Ω(n/\log n)$ queries. In contrast, we rule out approximation schemes with truly subquadratic query complexity for Densest $k$-Subgraph and settle its exact query complexity in both the unweighted and deterministic settings. For hypergraphs, we show CUT queries alone cannot achieve $o(\sqrt{n})$-approximation for Densest Subhypergraph or $o(n)$-approximation for Densest $k$-Subhypergraph, regardless of the number of queries. Augmenting CUT queries with the EDGE oracle of Chen et al., we overcome this barrier for Densest Subhypergraph and obtain a $(1+\varepsilon)$-approximation on rank-$r$ hypergraphs using $O(nr\log n/\varepsilon^2)$ queries. We also extend our Densest $k$-Subgraph hardness results to hypergraphs and prove exponential query lower bounds for exact Densest $k$-Subhypergraph. Lastly, confirming a conjecture of Chakrabarty and Liao, we show that simulating an ADD query using CUT and IS-EDGE$^?$ queries requires exponentially-many queries.

0.24

Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes

cs.DS ·2026-11-03 ·Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
theory similarity 0.66
Abstract

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $Ω(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).

0.20