@online{vandenBrand2307.09961,
TITLE = {On Dynamic Graph Algorithms with Predictions},
AUTHOR = {van den Brand, Jan and Forster, Sebastian and Nazari, Yasamin and Polak, Adam},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2307.09961},
EPRINT = {2307.09961},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We study dynamic algorithms in the model of algorithms with predictions. We<br>assume the algorithm is given imperfect predictions regarding future updates,<br>and we ask how such predictions can be used to improve the running time. This<br>can be seen as a model interpolating between classic online and offline dynamic<br>algorithms. Our results give smooth tradeoffs between these two extreme<br>settings.<br> First, we give algorithms for incremental and decremental transitive closure<br>and approximate APSP that take as an additional input a predicted sequence of<br>updates (edge insertions, or edge deletions, respectively). They preprocess it<br>in $\tilde{O}(n^{(3+\omega)/2})$ time, and then handle updates in<br>$\tilde{O}(1)$ worst-case time and queries in $\tilde{O}(\eta^2)$ worst-case<br>time. Here $\eta$ is an error measure that can be bounded by the maximum<br>difference between the predicted and actual insertion (deletion) time of an<br>edge, i.e., by the $\ell_\infty$-error of the predictions.<br> The second group of results concerns fully dynamic problems with vertex<br>updates, where the algorithm has access to a predicted sequence of the next $n$<br>updates. We show how to solve fully dynamic triangle detection, maximum<br>matching, single-source reachability, and more, in $O(n^{\omega-1}+n\eta_i)$<br>worst-case update time. Here $\eta_i$ denotes how much earlier the $i$-th<br>update occurs than predicted.<br> Our last result is a reduction that transforms a worst-case incremental<br>algorithm without predictions into a fully dynamic algorithm which is given a<br>predicted deletion time for each element at the time of its insertion. As a<br>consequence we can, e.g., maintain fully dynamic exact APSP with such<br>predictions in $\tilde{O}(n^2)$ worst-case vertex insertion time and<br>$\tilde{O}(n^2 (1+\eta_i))$ worst-case vertex deletion time (for the prediction<br>error $\eta_i$ defined as above).<br>},
}