On Dynamic Graph Algorithms with Predictions

Dynamic algorithms operate on inputs undergoing updates, e.g., insertions or deletions of edges or vertices. After processing each update, the algorithm has to answer queries regarding the current state of the input data. We study dynamic algorithms in the model of algorithms with predictions (also known as learning-augmented algorithms). We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predictions can be used to improve the running time. In other words, we study the complexity of dynamic problems parameterized by the prediction accuracy. This can be seen as a model interpolating between classic online dynamic algorithms -which know nothing about future updates -and offline dynamic algorithms with the whole update sequence known upfront, which is similar to having perfect predictions. Our results give smooth tradeoffs between these two extreme settings.

Our first group of results is about partially dynamic problems with edge updates. We give algorithms for incremental and decremental transitive closure and approximate APSP that take as an additional input a predicted sequence of updates (edge insertions, or edge deletions, respectively). They preprocess it in Õ(n (3+ω)/2 ) time, and then handle updates in Õ(1) worst-case time and queries in Õ(η 2 ) worst-case time.

Here η is an error measure that can be bounded by the maximum difference between the predicted and actual insertion (deletion) time of an edge, i.e., by the ℓ∞-error of the predictions.

The second group of results concerns fully dynamic problems with vertex updates, where the algorithm has access to a predicted sequence of the next n updates. We show how to solve fully dynamic triangle detection, maximum matching, single-source reachability, and more, in O(n ω-1 + nηi) worst-case update time. Here ηi denotes how much earlier the i-th update occurs than predicted.

Our last result is a reduction that transforms a worst-case incremental algorithm without predictions into a fully dynamic algorithm which is given a predicted deletion time for each element at the time of its insertion. As a consequence we can, e.g., maintain fully dynamic exact APSP with such predictions in Õ(n 2 ) worst-case vertex insertion time and Õ(n 2 (1 + ηi)) worst-case vertex deletion time (for the prediction error ηi defined as above).

Our algorithms from the first two groups, given sufficiently accurate predictions, achieve running times that go below known lower bounds for classic (without predictions) dynamic algorithms under the OMv Hypothesis. Moreover, our dependence on the prediction errors (so-called smoothness) is conditionally optimal, under plausible fine-grained complexity assumptions, at least in certain parameter regimes.