CS Paper Radar

Navigating Small-World Networks with Distance Predictions

Ladan Kian, Ming Ming Tan, Dariusz Kowalski

cs.DC cs.DS ·submitted 2026-09-09 22:42 UTC · v1

Abstract

The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented $k$-dimensional lattice a decentralized greedy algorithm delivers a message in $O(\log^2 n)$ expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy $(\varepsilon,δ)$-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an $(\varepsilon,δ)$-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time $O(\log n/(1-4k\varepsilonδ))$, an asymptotic improvement over $Θ(\log^2 n)$. An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an $(\varepsilon,δ)$-prediction of lattice distance instead, it still reaches the target in $O(n/(1-4k\varepsilonδ))$ expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.60
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.60
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

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
similarity 0.59
Abstract · v2: Added a deterministic almost-linear-time incremental SSSP algorithm with efficient approximate path reporting

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

0.21

Variants of Beam Search for DiskANN

cs.DS cs.DBcs.IR ·2026-11-19 ·Viraj Agrawal, Kirankumar Shiragur
similarity 0.59
Abstract · 22 pages, 1 figure, 9 tables

Graph-based data structures such as DiskANN, HNSW, and NSG constitute the state of the art for large-scale approximate nearest-neighbor (ANN) search. Indyk and Xu introduced the notion of $α$-reachable graphs, which include graphs built by DiskANN's slow-preprocessing construction, and proved that greedy search achieves an approximation factor of $\tfrac{α+1}{α-1}$. Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter $γ> 0$, showing a $\tfrac{2}γ$ approximation on navigable graphs ($α\approx 1$), where greedy search admits no guarantees. In this work, we unify and generalize these results by proving that ABS with parameter $γ$ on $α$-reachable graphs achieves an approximation of $\tfrac{α+1}{α(γ+1)-1}$ for any metric. Moreover, on sorted $α$-reachable graphs (introduced by Gollapudi et al.) under the $\ell_2$ metric, we obtain the tighter bound $\max\bigl(\tfracα{α(γ+1)-1}, \tfrac{α^{2}+1}{α^{2}(γ+1)-1}\bigr)$. Beyond these theoretical results, we design a beam predictor using features inspired by fine-grained analysis of ABS, trained via a constrained objective that minimizes mean distance computations subject to a target recall. On three 100-million-point benchmarks, using graphs built by DiskANN's practical construction, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to $29.6\%$ relative to classical beam search (CBS). Relative to ABS, it is faster in $11$ of $15$ settings, by up to $6.5\%$, and at most $1.4\%$ slower in the other $4$; at $95\%$ recall, its advantage over ABS grows from $0.8$--$4.2\%$ for $100$ neighbors to $4.6$--$5.6\%$ for $500$ neighbors. In memory, it needs $1.3$--$23.7\%$ fewer distance computations than CBS and $0.0$--$3.9\%$ fewer than ABS.

0.15

Latent World Models Should Plan with Distances Along the Latent Manifold

cs.LG cs.RO ·2026-10-18 ·Zunzhi You, Linwei Tao, Siyu Xu, Yunke Wang, Chang Xu
benchmark similarity 0.59
Abstract

Latent world models such as LeWM plan by searching for an action sequence whose predicted terminal latent is closest to the goal latent under an ambient norm, such as the Euclidean distance. Planning with such a cost assumes that proximity in the ambient latent space reflects proximity to the goal in the environment. Studying LeWM, we find that this assumption holds only in a small neighborhood around the goal, whereas farther away the L2 cost forms spurious low-cost basins that trap the planner. Yet neighborhood-based embeddings show that the latents retain the underlying physical state. We therefore hypothesize that the latents lie near a curved, low-dimensional manifold, and that the terminal cost should measure the distance along this latent manifold rather than through the ambient space. To estimate this manifold distance, we propose the Neighborhood Graph Cost (NGC), which computes shortest-path distances on a mutual nearest-neighbor graph constructed over training latents. NGC changes only the terminal cost and requires no retraining. This single change improves the planning success rate of LeWM across all four benchmark tasks and nearly solves TwoRoom and Reacher: even at the farthest goal offsets tested, NGC reaches 95% and 100% success, whereas the L2 cost falls to 27% and 81%. These results support the manifold hypothesis and our argument that latent world models should plan with distances along the latent manifold.

0.13

Tight asymptotic competitive ratio for the Canadian Traveller Problem on unit-weighted grids

cs.DS ·2026-10-09 ·Pierre Bergé, Vsevolod Chernyshev, Malory Marin, Alexey Pyrko, Lou Salaün
theory similarity 0.59
Abstract

We study the $k$-Canadian Traveller Problem (k-ctp), an online navigation problem introduced by Papadimitriou and Yannakakis in 1991. Given an undirected weighted graph $G=(V,E,ω)$ and two vertices $s,t\in V$, a traveller aims at navigating from $s$ to $t$ while minimizing the total distance travelled. However, up to $k$ edges of the graph may be blocked, and the traveller discovers that an edge is blocked only upon reaching one of its endpoints. The performance of an online algorithm for k-ctp is measured with the competitive ratio, which is the quotient between the distance actually traversed and the distance traversed by an omniscient traveller who knows all blockages in advance. A general lower bound $2k+1$ for the competitive ratio of deterministic algorithms remains valid even when the input graph is series-parallel, whereas constant competitive ratios can be achieved on restricted graph classes, such as cycles or unit-weighted outerplanar graphs. In this paper, we establish the first intermediate competitive ratio between constant and linear regimes. We prove that, on unit-weighted solid grid graphs, there exists an online algorithm with competitive ratio $O(\sqrt{k})$. This ratio is asymptotically tight and cannot be defeated, even on unit-weighted square grids. Finally, we show that both the unit-weighted and solidity assumptions are essential: going further with arbitrary edge weights (even on square grids) or non-solid unit-weighted grid structures yields a linear lower bound of $Ω(k)$.

0.25

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.58
Abstract · To appear at SODA 2027

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

0.40

Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion

cs.MA ·2026-09-23 ·Ariel Barel
theory similarity 0.58
Abstract

We study connectivity-preserving finite-jump dispersion of anonymous, identical, and oblivious agents under an idealized range-only sensing model. Each agent measures only the distances to its visible neighbors, without bearings, identifiers, communication, memory, or a shared coordinate system. We derive the largest isotropic displacement certifiable as safe from these measurements alone. The resulting rule requires only the distance to the farthest visible neighbor: each agent selects a random direction and moves by half of its remaining visibility margin. The rule preserves every existing visibility edge under synchronous finite motion and therefore preserves connectivity. For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary, and finite expected time to reach any fixed neighborhood of that boundary. A one-million-run Monte Carlo experiment agrees with the exact first-round moments and estimates approximately 9.5 rounds to reach distance 0.97V from coincident initial positions; an independent Bellman-equation computation gives the same estimate. For general swarms, 1,000 runs across five initial-topology classes reproduce the deterministic safety guarantee at implementation level and reveal a consistent topology-dependent ordering of attainable diameter under the tested protocol. These results provide a theoretical foundation for connectivity-preserving multi-robot dispersion under minimal sensing, while isolating the guarantees achievable from anonymous range measurements alone.

0.24