Warm-Starting All-Pairs Shortest Paths with Predictions
2026-07-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors explore how to solve the All-Pairs Shortest Paths (APSP) problem using predictions from past similar problems to speed up the process. They design an algorithm that runs faster than traditional methods if the prediction errors are low, meaning the predictions are mostly accurate. Their approach uses advanced techniques to detect and fix mistakes in predicted shortcuts between points. This work is a first step toward combining machine learning predictions with algorithms for problems that are traditionally considered hard to speed up.
All-Pairs Shortest Paths (APSP)Fine-grained complexityLearning-augmented algorithmsPrediction errorSubcubic timeExact Triangle problemCo-nondeterministic algorithmsShortest detourAlgorithmic certificationComputational lower bounds
Authors
Adam Polak, Jonas Schmidt
Abstract
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, in the worst case. 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 \emph{prediction} (e.g., given by a model learned from similar instances seen in the past) consisting of sets of vertices causing the shortest \emph{detour} for each pair of vertices. The algorithm runs in time $\mathcal{O}(n^{2.83} + ηn)$, where $η$ denotes the \emph{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 values $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.