# A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

Preprint · Jiaqi Mao

- Archive id: arxiv:2608.19538
- Published: 2026-08-20
- arXiv: https://arxiv.org/abs/2608.19538
- Source URL: https://arxiv.org/abs/2608.19538
- PDF: https://arxiv.org/pdf/2608.19538
- Provenance: arxiv

## Abstract

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $β\\in\[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\\log\\log n)/2})$ and, with high probability, returns a path with length within $\\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{Θ(2-1/\\log\\log n)}$-time preprocessing step, its query time improves to $n^{Θ(1/\\log\\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\\times$-$7.76\\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.