Greedy Routing in a Sequentially Grown One-Dimensional Random Graph
2026-04-21 • Data Structures and Algorithms
Data Structures and AlgorithmsNetworking and Internet ArchitectureSocial and Information Networks
AI summaryⓘ
The authors study how a simple step-by-step method for finding a path, called greedy routing, works in a special random network made by adding points in order along a line. They prove that to get from the first point to the last, the number of steps needed grows roughly like the logarithm of the number of points. This matches what previous computer experiments suggested but now has a solid mathematical proof for the one-dimensional case. They also show that this logarithmic behavior holds even when starting and ending points vary, making the result applicable to more realistic scenarios.
greedy routingrandom graphlogarithmic complexitysequential insertionnearest neighborleft-to-right minimaright-to-left minimaBennett rate functionexpected routing stepsdecentralized networks
Authors
Alexander Ponomarenko
Abstract
We analyze greedy routing in a random graph G_n constructed on the vertex set V = {1, 2, ..., n} embedded in Z. Vertices are inserted according to a uniform random permutation pi, and each newly inserted vertex connects to its nearest already-inserted neighbors on the left and right (if they exist). This work addresses a conjecture originating from empirical studies (Ponomarenko et al., 2011; Malkov et al., 2012), which observed through simulations that greedy search in sequentially grown graphs exhibits logarithmic routing complexity across various dimensions. While the original claim was based on experiments and geometric intuition, a rigorous mathematical foundation remained open. Here, we formalize and resolve this conjecture for the one-dimensional case. For a greedy walk GW starting at vertex 1 targeting vertex n -- which at each step moves to the neighbor closest to n -- we prove that the number of steps S_n required to reach n satisfies S_n = Theta(log n) with high probability. Precisely, S_n = L_n + R_n - 2, where L_n and R_n are the numbers of left-to-right and right-to-left minima in the insertion-time permutation. Consequently, E[S_n] = 2H_n - 2 ~ 2 log n and P(S_n >= (2+c) log n) <= n^(-h(c/2) + o(1)) for any constant c > 0, with an analogous lower tail bound for 0 < c < 2, where h(u) = (1+u) ln(1+u) - u is the Bennett rate function. Furthermore, we establish that this logarithmic scaling is robust: for arbitrary or uniformly random start-target pairs, the expected routing complexity remains E[S_{s,t}] = 2 log n + O(1), closely mirroring decentralized routing scenarios in real-world networks where endpoints are chosen dynamically rather than fixed a priori.