English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On Dynamic Graph Algorithms with Predictions

MPS-Authors
/persons/resource/persons289639

Polak,  Adam
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2307.09961.pdf
(Preprint), 457KB

Supplementary Material (public)
There is no public supplementary material available
Citation

van den Brand, J., Forster, S., Nazari, Y., & Polak, A. (2023). On Dynamic Graph Algorithms with Predictions. Retrieved from https://arxiv.org/abs/2307.09961.


Cite as: https://hdl.handle.net/21.11116/0000-0010-837D-E
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 $\tilde{O}(n^{(3+\omega)/2})$ time, and then handle updates in
$\tilde{O}(1)$ worst-case time and queries in $\tilde{O}(\eta^2)$ worst-case
time. Here $\eta$ 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 $\ell_\infty$-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^{\omega-1}+n\eta_i)$
worst-case update time. Here $\eta_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 $\tilde{O}(n^2)$ worst-case vertex insertion time and
$\tilde{O}(n^2 (1+\eta_i))$ worst-case vertex deletion time (for the prediction
error $\eta_i$ defined as above).