On Dynamic Graph Algorithms with Predictions
Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak · Society for Industrial and Applied Mathematics eBooks · 2024
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.