2024/02/15 by Jialu Hu, Hu, Jialu, László Kozma +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2402.10343
openalex publication_date 2024/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Bellman-Ford algorithm for single-source shortest paths repeatedly updates tentative distances in an operation called relaxing an edge. In several important applications a non-adaptive (oblivious) implementation is preferred, which means fixing the entire sequence of relaxations upfront, independently of the edge-weights. Such an implementation performs, in a dense graph on n vertices, (1 + o(1))n3 relaxations. An improvement by Yen from 1970 reduces the number of relaxations by a factor of two. We show that no further constant-factor improvements are possible, and every non-adaptive deterministic algorithm based on relaxations must perform ((1)/(2) - o(1))n3 steps. This improves an earlier lower bound of Eppstein of ((1)/(6) - o(1))n3. Given that a non-adaptive randomized variant of Bellman-Ford with at most ((1)/(3) + o(1))n3 relaxations (with high probability) is known, our result implies a strict separation between deterministic and randomized strategies, answering an open question of Eppstein. On the complexity side, we show that deciding whether a given relaxation sequence is guaranteed to yield correct distances is NP-hard, even with the complete graph as input.