Dynamic Breadth First Search with Predictions

Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya · 2026

Read Dynamic Breadth First Search with Predictions by Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01187.txt.

Introduction

Khan, Verma, and Lohiya keep a breadth first search tree fresh under edge updates, with help from predictions in this 2026 paper. A BFS tree records parents and levels from a source vertex. Edge insertions and deletions force costly rebuilds. Classic dynamic methods pay heavy total time, and a known conjecture blocks big gains even when updates are known ahead. Fully dynamic care was stuck at plain recomputation.

Their algorithms take a predicted update sequence as input. Bounds are stated in terms of prediction error, counted over the vertices and edges the forecast got wrong. Insertion only and deletion only versions each run in time near the error mass. That can be far below the classic totals when forecasts are good. The fully dynamic case gets bounds of the same flavor. The work joins a growing line: let algorithms charge their cost to the mistakes of a predictor.

Catalog record

CREATORShahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01187

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Breadth First Search with Predictions Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya Abstract Given a graph G = ( V , E ) G=(V,E) having n n vertices and m m edges, we investigate the problem of maintaining its Breadth-First Search (BFS) tree from a fixed source s ∈ V s\in V , subject to an online sequence of edge insertions and/or deletions in the prediction model. Our approach leverages a predicted update sequence that can be preprocessed to build data structures based on anticipated updates, 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, without using predictions, the incremental and decremental BFS tree can be maintained in total O ⁡ ( m ​ n ) O(mn) time using ES Trees [JACM81], resulting in amortized O ⁡ ( n ) O(n) update time. However, in the worst case, it requires Ω ⁡ ( m ) \Omega(m) time. Moreover, for maintaining BFS trees under fully dynamic edge updates, no algorithm better than trivial recomputation after every update is known, requiring O ⁡ ( m ) O(m) time per update. Further, assuming the combinatorial BMM conjecture, no algorithm can maintain incremental or decremental BFS polynomially faster than O ⁡ ( m ​ n ) O(mn) [FOCS14], even when the entire update sequence is known in advance [STOC15]. Our complexity bounds are expressed in terms of error measures of the prediction, where error vertices are those having incorrectly predicted distance, with the corresponding difference called their error . We define the vertex prediction error η v \eta_{v} as the sum of the degree of error vertices , and the weighted vertex prediction error η v ∗ \eta^{*}_{v} as the error weighted sum of the degree of error vertices . Additionally, we define η e \eta_{e} as the number of incorrectly predicted edge updates. For incremental and decremental BFS our algorithm requires respectively O ⁡ ( η v + η e ) O(\eta_{v}+\eta_{e}) and O ⁡ ( min ⁡ { m , η v ∗ + η e } ) O(\min\{m,\eta^{*}_{v}+\eta_{e}\}) worst case update times using O ⁡ ( m ​ n ) O(mn) preprocessing time and space, and total update time of O ⁡ ( η v ∗ + η e ) O(\eta^{*}_{v}+\eta_{e}) . We also present the space-efficient extensions of the above algorithms requiring O ⁡ ( n 2 ) O(n^{2}) and O ⁡ ( m ​ n k + n 2 ) O(\frac{mn}{k}+n^{2}) space for any k ∈ [ 1 , n ] k\in[1,n] , at the expense of additional O ⁡ ( n ​ log ⁡ n ) O(n\log n) and O ⁡ ( n ​ k ) O(nk) time in the worst case and total time, respectively. For fully-dynamic updates, our algorithm requires an update time of O ⁡ ( min ⁡ { m , η v ∗ + η e } ) O(\min\{m,\eta^{*}_{v}+\eta_{e}\}) in the worst case. At its core, we extend the classical ES Trees [JACM81] for batch updates and fully dynamic updates, which may be of independent interest. Notably, this simple extension of ES Trees for batch updates is sufficient to give a competitive prediction algorithm, which can thus be generalized to other graph problems. Finally, we consider error correction mechanisms to further improve the performance of our results. Department of Computer Science and Engineering, Indian Institute of Technology, Roorkee, India and https://shahbazk.github.io/ [email protected]://orcid.org/0000-0001-9352-0088 Department of Computer Science and Engineering, Indian Institute of Technology, Roorkee, [email protected] Department of Computer Science and Engineering, Indian Institute of Technology, Roorkee, [email protected] We thank the anonymous reviewers for their valuable feedback. \declaretheorem [name=Theorem,numberwithin=section]thm ccs Theory of computation Graph algorithms analysis ccs Theory of computation Online algorithms ccs Theory of computation Dynamic graph algorithms keywords dynamic graphs, breadth-first search, learning-augmented algorithms, algorithms with predictions, batch updates † † runningtitle: Dynamic BFS with Predictions † † runningauthor: S. Khan, S. K. Verma, and U. Lohiya † † copyright: Shahbaz Khan, Shubham Kumar Verma, and Utkarsh Lohiya 1 Introduction The area of dynamic graph algorithms deals with such graphs that evolve over time by a sequence of online updates, i.e., insertion or deletion of edges. The goal is to maintain the data structure or solution after every such update, much faster than trivially recomputing it from scratch after every update. An algorithm is called fully dynamic if it allows both insertion and deletion updates. It is called partially dynamic , i.e., incremental or decremental when the updates are limited to insertions or deletions, respectively. Some of the prominent graph problems studied in this area include connectivity [ 10 , 14 , 16 , 18 , 5 ] , reachability [ 17 , 9 , 13 , 3 , 7 ] , shortest paths [ 6 , 29 , 27 ] , etc. Several such algorithms are also shown to be optimal conditioned on popular conjectures [ 27 , 1 , 12 ] . In this paper, we study the problem of maintaining Breadth First Search (BFS) Trees (or shortest path trees for unweighted graphs) from a given source under dynamic updates. The applications of BFS trees range from network routing and distance estimation to social-influence analysis and web crawling, which fundamentally maintain BFS distances under a stream of edge updates. Given a graph G(V,E) having n nodes and m edges, its BFS tree from any source s\in V can be computed in O(m+n) time. Recomputing the BFS tree from scratch after each update is thus prohibitive when updates arrive at high frequency on large networks. The classical result by Even and Shiloach [ 9 ] maintains a partially dynamic BFS tree in total O(mn) or amortized O(n) update time, a bound that remained the state of the art for directed graphs for decades. Later, Roditty and Zwick [ 27 ] showed that no combinatorial algorithm can improve the bound using the All Pairs Shortest Paths Conjecture. Further, it was shown that no polynomial improvement for partially dynamic BFS was possible using the combinatorial BMM conjecture by Abboud and Williams [ 1 ] , even for offline updates (update sequence known in advance) [ 12 ] . However, in the worst case, the update time can still be O(m) . This was also shown to be tight by Henzinger et al. [ 12 ] using the Online Matrix Vector product (OMv) conjecture. For the fully dynamic setting, no algorithm is known to improve the trivial recomputation in O(m) time. However, a fully dynamic version of ES trees was shown by Hanauer et al. [ 11 ] to perform well in practice despite having no better theoretical bounds. We study the classical dynamic BFS tree problem in the prediction model. A motivating observation about real-world update sequences is that they are rarely adversarial: network changes tend to follow patterns, user behaviour is often repetitive, and future updates can frequently be anticipated from historical data or learned models. The emerging paradigm of algorithms with predictions (also called learning-augmented algorithms ) formalises this intuition by equipping classical algorithms with a prediction —an auxiliary input, potentially produced by a machine-learning oracle. The goal is to determine if predictions

Read the complete text