Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

ACM Transactions on Algorithms 2026 Open access

Read full text
Authors: Sunny Atalig, Alexander Hickerson, A. Srivastav, Tingting Zheng, Marek Chrobák
DOI: 10.1145/3816151
Cited by: 0

Abstract

We consider the classical single-source shortest path problem in directed weighted graphs. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.

Fields of Study & Subjects

Network Traffic and Congestion Control Sparse and Compressive Sensing Techniques Stochastic Gradient Optimization Techniques

Publication details

Journal / source
ACM Transactions on Algorithms
Volume
22
Issue
3
Pages
1–21
Publication date
29 May 2026
Language
EN