Felix Broberg

Prediction Assisted Fully Dynamic All-Pairs Effective Resistance

Abstract

We study the approximate fully dynamic online all-pairs effective resistance problem in a prediction assisted setting. We introduce a prediction model for predicting which vertex pairs will be involved in future edge insertions, deletions or effective resistance queries that is general enough to be compatible with some link predictors and can be used by other prediction assisted algorithm researchers. A minor contribution is that we give the best known algorithm for the offline problem. Our main result is a data structure for maintaining the effective resistance between all vertex pairs that utilizes the devised prediction model. The running time matches the performance of the best known offline algorithm if the predictions are good and the best known online data structure if the predictions are bad.