Dynamic Breadth First Search with Predictions
For dynamic graph algorithms, this work provides the first prediction-based BFS maintenance, offering speedups when predictions are accurate, though the improvement is incremental and relies on extending existing ES trees.
The paper presents algorithms for maintaining BFS trees under edge updates using predictions, achieving worst-case update times of O(η_v + η_e) for incremental, O(min{m, η^*_v + η_e}) for decremental, and O(min{m, η^*_v + η_e}) for fully dynamic settings, where η measures prediction error. This improves over the classical O(mn) total time.
Given a graph $G(V,E)$ having $n$ vertices and $m$ edges, we maintain its Breadth-First Search (BFS) tree from source $s$ under an online sequence of edge updates in the prediction model. Our approach leverages a predicted update sequence aiding online processing. We present algorithms for incremental (insertions-only), decremental (deletions-only), and fully dynamic (insertions and deletions) settings that maintain a BFS tree (parent and level information). Classically, the incremental and decremental BFS tree requires total $O(mn)$ time [JACM81], with amortized $O(n)$ and worst-case $O(m)$ update time. The combinatorial BMM conjecture restricts any polynomial improvement [FOCS14] even when the updates are known in advance [STOC15]. For fully dynamic BFS trees, only the trivial $O(m)$ time recomputation is known. Our complexity bounds are expressed in prediction error measures, where error vertices are those having incorrectly predicted distances, with the corresponding difference as their error. The vertex prediction error $η_{v}$ is the sum of degrees of error vertices, weighted vertex prediction error $η^*_{v}$ is error-weighted sum of degrees of error vertices, and $η_e$ counts the incorrectly predicted updates. For incremental and decremental BFS, our algorithm requires respectively $O(η_v + η_e)$ and $O(\min\{m,η^*_v + η_e\})$ worst case update time using $O(mn)$ preprocessing time and space, and total update time of $O(η^*_v + η_e)$. For fully-dynamic updates, our algorithm requires $O(\min\{m,η^*_v+η_e\})$ worst case update time. At its core, we extend the classical ES Trees [JACM81] for batch updates and fully dynamic updates. This simple extension is sufficient to give a competitive prediction algorithm, which may be generalized to other graph problems. We also consider space optimizations and error correction to improve our results.