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. The model is general enough to be compatible with some link predictors and can be used by other prediction assisted algorithms. Our main contribution is a data structure that utilizes the devised prediction model to maintain the effective resistance between all vertex pairs. 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. A minor contribution is that we give the best known algorithm for the offline problem.