On Dynamic Graph Algorithms with Predictions

2023/07/19 by Jan van den Brand, Sebastian Forster, Brand, Jan van den +5 · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2307.09961

openalex publication_date 2023/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We study dynamic algorithms in the model of algorithms with predictions. 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. This can be seen as a model interpolating between classic online and offline dynamic algorithms. Our results give smooth tradeoffs between these two extreme settings. First, 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 O(n^(3+ω)/2) time, and then handle updates in O(1) worst-case time and queries in O(η²) 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 O(n²) worst-case vertex insertion time and O(n² (1+η_i)) worst-case vertex deletion time (for the prediction error η_i defined as above).

Cited by

• Answering Conjunctive Queries with Aggregations under Updates
• Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
• Learning-Augmented Streaming Algorithms for Correlation Clustering
• Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
• Efficient Approximate Temporal Triangle Counting in Streaming with Predictions

Related

• The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations
• On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
• Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
• Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
• Deterministic Fully Dynamic Approximate Vertex Cover and Fractional\n Matching in O(1) Amortized Update Time