One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors. We initiate the study of APSP in the paradigm of algorithms with predictions, also known as learning-augmented algorithms. We propose an APSP algorithm that takes as additional input a prediction (e.g., given by a model learned from similar instances seen in the past) consisting of sets of vertices causing the shortest detour for each pair of vertices. The algorithm runs in time $\mathrm{O}(n^{2.83} + \eta n)$, where $\eta$ denotes the prediction error defined as the number of pairs of vertices for which, informally speaking, the prediction was not sufficient to compute and certify optimality of the shortest path length.
This is already subcubic when the prediction error is (polynomially) smaller than its maximum possible value $n^2$, i.e., whenever the prediction is at least slightly better than terrible. We build on the co-nondeterministic algorithm for the Exact Triangle problem by Chan, Vassilevska Williams, and Xu (STOC 2023), essentially enabling this algorithm to detect mistakes in the nondeterministic certificate and recover from them. Our result constitutes the first necessary step towards designing learning-augmented algorithms for problems with known fine-grained lower bounds conditioned on the APSP Hypothesis.
Blogger's Review: This paper introduces a novel approach to the All-Pairs Shortest Paths problem by incorporating predictive mechanisms. The innovation of combining learning with algorithms suggests a promising future for algorithm design, particularly in addressing complexity lower bounds, warranting further exploration and practical application.