pith. sign in

arxiv: 2606.01187 · v1 · pith:6UJRIBFJnew · submitted 2026-05-31 · 💻 cs.DS

Dynamic Breadth First Search with Predictions

Shahbaz Khan , Shubham Kumar Verma , Utkarsh Lohiya This is my paper

Pith reviewed 2026-06-28 16:34 UTC · model grok-4.3

classification 💻 cs.DS
keywords dynamic graphsBFS treeprediction modelincremental algorithmsdecremental algorithmsfully dynamic algorithmsEven-Shiloach trees
0
0 comments X

The pith

BFS trees under dynamic edge updates can be maintained with time linear in the size of prediction errors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents algorithms that maintain a BFS tree from a fixed source while the graph receives online edge insertions and deletions, but only when a predicted sequence of those updates is also supplied. The running time of each update is bounded by measures of how much the prediction differs from reality, specifically the summed degrees of vertices whose distances were predicted wrong, an error-weighted version of that sum, and the count of wrongly predicted updates. These bounds improve on the classical O(m) per update or O(mn) total time whenever the predictions are reasonably accurate. The approach works by extending a standard dynamic shortest-path structure to process batches of changes suggested by the prediction.

Core claim

Extending Even-Shiloach trees to batch updates guided by a predicted update sequence yields an incremental algorithm with O(η_v + η_e) worst-case update time, a decremental algorithm with O(min{m, η*_v + η_e}) worst-case update time and O(η*_v + η_e) total update time, and a fully-dynamic algorithm with O(min{m, η*_v + η_e}) worst-case update time, all after O(mn) preprocessing, where η_v, η*_v and η_e are the vertex, weighted-vertex and edge prediction-error measures.

What carries the argument

The extension of Even-Shiloach trees to process batches of predicted updates while tracking only the vertices whose distances deviate from the prediction.

If this is right

  • Incremental maintenance requires only O(η_v + η_e) worst-case time per update after O(mn) preprocessing.
  • Decremental maintenance requires O(min{m, η*_v + η_e}) worst-case time per update and O(η*_v + η_e) total time.
  • Fully-dynamic maintenance requires O(min{m, η*_v + η_e}) worst-case time per update.
  • The same batch-extension technique is presented as applicable to other dynamic graph problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • When predictions are nearly perfect the per-update cost can drop well below the graph size, opening the possibility of sublinear dynamic algorithms in practice.
  • Space-optimization and error-correction techniques mentioned in the paper could be combined with the core extension to reduce the O(mn) preprocessing cost.
  • The prediction model could be tested on real-world evolving networks where update patterns are partially forecastable, such as social graphs or transportation networks.

Load-bearing premise

The model requires that every online update sequence is accompanied by a predicted update sequence so that the error measures η_v, η*_v and η_e are well-defined after the fact.

What would settle it

A concrete graph, source, online update sequence and accompanying prediction for which the error measures are o(m) yet any correct maintenance algorithm still requires Ω(m) time on some update.

read the original abstract

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 $\eta_{v}$ is the sum of degrees of error vertices, weighted vertex prediction error $\eta^*_{v}$ is error-weighted sum of degrees of error vertices, and $\eta_e$ counts the incorrectly predicted updates. For incremental and decremental BFS, our algorithm requires respectively $O(\eta_v + \eta_e)$ and $O(\min\{m,\eta^*_v + \eta_e\})$ worst case update time using $O(mn)$ preprocessing time and space, and total update time of $O(\eta^*_v + \eta_e)$. For fully-dynamic updates, our algorithm requires $O(\min\{m,\eta^*_v+\eta_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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper presents algorithms for maintaining a BFS tree (parent and level information) from a fixed source under an online sequence of edge insertions, deletions, or both, in the prediction model. A predicted update sequence is supplied alongside the online updates; prediction errors are measured post hoc via η_v (sum of degrees of vertices with incorrect predicted distances), η*_v (error-weighted version of the same), and η_e (number of incorrectly predicted updates). Using O(mn) preprocessing and space, the claimed bounds are O(η_v + η_e) worst-case update time for incremental, O(min{m, η*_v + η_e}) worst-case and O(η*_v + η_e) total for decremental, and O(min{m, η*_v + η_e}) worst-case for fully dynamic, obtained by a simple extension of Even-Shiloach trees to batch updates.

Significance. If the stated conditional bounds hold, the work supplies the first non-trivial dynamic BFS results that depend on prediction quality rather than graph size, thereby evading the combinatorial BMM-based lower bounds that apply in the prediction-free setting. The reliance on a standard ES-tree extension rather than new data structures is a methodological strength, and the additional consideration of space optimizations and error correction is noted.

major comments (2)
  1. [Abstract] Abstract (paragraph on complexity bounds): the claim that 'a simple extension of the classical ES Trees for batch updates and fully dynamic updates' is sufficient to obtain the stated O(η_v + η_e) and O(min{m, η*_v + η_e}) bounds is load-bearing, yet the abstract supplies neither a proof sketch nor an argument that the chosen error measures capture every correction required to restore correct parent/level information after an arbitrary batch of updates.
  2. [Abstract] Abstract (model description): the running-time expressions are expressed directly in the externally measured quantities η_v, η*_v, η_e; the manuscript must verify that these quantities are well-defined for every online sequence that can arise and that the algorithm's correctness does not depend on additional assumptions about how the predicted sequence is generated.
minor comments (1)
  1. [Abstract] The abstract introduces η*_v as the 'error-weighted sum of degrees of error vertices' but does not explicitly state whether the weight applied to each degree is the absolute distance error or another quantity; a one-sentence clarification would remove ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and suggestions. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on complexity bounds): the claim that 'a simple extension of the classical ES Trees for batch updates and fully dynamic updates' is sufficient to obtain the stated O(η_v + η_e) and O(min{m, η*_v + η_e}) bounds is load-bearing, yet the abstract supplies neither a proof sketch nor an argument that the chosen error measures capture every correction required to restore correct parent/level information after an arbitrary batch of updates.

    Authors: The abstract is necessarily concise and defers detailed arguments to the body of the paper. In Sections 3 and 4, we provide the full analysis showing how the batch update extension of ES-trees, combined with the definitions of η_v, η*_v, and η_e, accounts for all necessary corrections to the BFS tree. The error measures are chosen precisely to bound the number of vertices whose levels and parents may need updating. We can revise the abstract to include a one-sentence indication of this argument if desired. revision: partial

  2. Referee: [Abstract] Abstract (model description): the running-time expressions are expressed directly in the externally measured quantities η_v, η*_v, η_e; the manuscript must verify that these quantities are well-defined for every online sequence that can arise and that the algorithm's correctness does not depend on additional assumptions about how the predicted sequence is generated.

    Authors: The prediction model assumes an arbitrary predicted update sequence is provided in advance, and the error measures η_v, η*_v, η_e are defined post hoc by comparing the predicted distances and updates to the actual ones that occur. These quantities are therefore well-defined for any possible online sequence of updates. The algorithm's correctness and running-time bounds hold for any such predictions without further assumptions on their generation process; the bounds simply degrade gracefully with poorer predictions. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states its update-time bounds directly as functions of externally measured prediction-error quantities η_v, η*_v, and η_e (defined post-facto from actual vs. predicted distances and updates). These quantities are inputs to the analysis rather than outputs of any internal fit or self-definition. The core technical step is an extension of the classical external ES-trees construction [JACM81] to batch updates; the claimed O(η_v + η_e) etc. bounds follow from charging the work to the supplied error measures without reducing to a fitted parameter or a self-citation chain. No load-bearing premise relies on a uniqueness theorem or ansatz imported from the authors' prior work. The derivation is therefore self-contained against the stated prediction model.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard assumption that graphs are undirected and unweighted for BFS, plus the existence of a supplied prediction sequence whose error is measured post hoc; no free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption Graphs are undirected and unweighted; BFS distances and levels are well-defined under edge insertions and deletions.
    Invoked throughout the abstract when defining error vertices and levels.
  • domain assumption A predicted update sequence is provided as input to the online algorithm.
    Stated in the opening sentence of the abstract as the prediction model.

pith-pipeline@v0.9.1-grok · 5920 in / 1490 out tokens · 25991 ms · 2026-06-28T16:34:23.629997+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 3 canonical work pages

  1. [1]

    Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , booktitle =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai and Thatchaphol Saranurak , editor =. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , booktitle =

  2. [2]

    Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , booktitle =

    Amir Abboud and Virginia. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , booktitle =

  3. [3]

    Algorithm Theory -

    Mikkel Thorup , title =. Algorithm Theory -

  4. [4]

    Italiano and Alberto Marchetti

    Giorgio Ausiello and Giuseppe F. Italiano and Alberto Marchetti. Incremental Algorithms for Minimal Length Paths , journal =

  5. [5]

    Proceedings of the 40th Annual Symposium on Foundations of Computer Science , series =

    King, Valerie , title =. Proceedings of the 40th Annual Symposium on Foundations of Computer Science , series =. 1999 , isbn =

    1999

  6. [6]

    Proceedings of the Twenty-Fourth Annual

    Liam Roditty , title =. Proceedings of the Twenty-Fourth Annual

  7. [7]

    Jakub Lacki , title =

  8. [8]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Bernstein, Aaron and Probst, Maximilian and Wulff-Nilsen, Christian , title =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2019 , isbn =

    2019

  9. [9]

    Fast and Simple Connectivity in Graph Timelines

    Karczmarz, Adam and a cki, Jakub. Fast and Simple Connectivity in Graph Timelines. Algorithms and Data Structures. 2015

    2015

  10. [10]

    Assessing metacognitive awareness

    Offline Algorithms for Dynamic Minimum Spanning Tree Problems , journal =. 1994 , issn =. doi:https://doi.org/10.1006/jagm.1994.1033 , url =

    work page doi:10.1006/jagm.1994.1033 1994

  11. [11]

    Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity

    Peng, Richard and Sandlund, Bryce and Sleator, Daniel D. Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity. Algorithms and Data Structures. 2019

    2019

  12. [12]

    Algorithms with Predictions , booktitle=

    Mitzenmacher, Michael and Vassilvitskii, Sergei , year=. Algorithms with Predictions , booktitle=

  13. [13]

    Mitzenmacher, Michael and Vassilvitskii, Sergei , title =. Commun. ACM , month = jun, pages =. 2022 , issue_date =

    2022

  14. [14]

    Proceedings of the 41st International Conference on Machine Learning , pages=

    Incremental topological ordering and cycle detection with predictions , author=. Proceedings of the 41st International Conference on Machine Learning , pages=

  15. [15]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    The predicted-updates dynamic model: Offline, incremental, and decremental to fully dynamic transformations , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  16. [16]

    15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=

    On the Complexity of Algorithms with Predictions for Dynamic Graph Problems , author=. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=. 2024 , organization=

    2024

  17. [17]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    On dynamic graph algorithms with predictions , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  18. [18]

    2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) , pages=

    Fully dynamic single-source reachability in practice: An experimental study , author=. 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) , pages=. 2020 , organization=

    2020

  19. [19]

    Algorithmica , volume =

    Liam Roditty and Uri Zwick , title =. Algorithmica , volume =

  20. [20]

    Proceedings of the 37th Annual

    Mikkel Thorup , title =. Proceedings of the 37th Annual

  21. [21]

    Italiano , title =

    Camil Demetrescu and Giuseppe F. Italiano , title =. J. ACM , volume =. 2004 , pages =

    2004

  22. [22]

    Italiano , title =

    Camil Demetrescu and Giuseppe F. Italiano , title =. Algorithmica , volume =. 2008 , url =. doi:10.1007/S00453-007-9051-4 , timestamp =

    work page doi:10.1007/s00453-007-9051-4 2008

  23. [23]

    Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time , journal =

    Aaron Bernstein and Maximilian Probst Gutenberg and Christian Wulff. Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time , journal =. 2019 , url =. doi:10.1137/20M1312149 , timestamp =

    work page doi:10.1137/20m1312149 2019

  24. [24]

    Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs , booktitle =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , editor =. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs , booktitle =

  25. [25]

    A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , booktitle =

    Julia Chuzhoy and Yu Gao and Jason Li and Danupon Nanongkai and Richard Peng and Thatchaphol Saranurak , editor =. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , booktitle =

  26. [26]

    Kapron and Valerie King and Ben Mountjoy , title =

    Bruce M. Kapron and Valerie King and Ben Mountjoy , title =. SODA , year =

  27. [27]

    Jacob Holm and Kristian de Lichtenberg and Mikkel Thorup , title =. J. ACM , volume =. 2001 , pages =

    2001

  28. [28]

    Monika Rauch Henzinger and Valerie King , title =. J. ACM , volume =. 1999 , pages =

    1999

  29. [29]

    Frederickson , title =

    Greg N. Frederickson , title =

  30. [30]

    Journal of the ACM , volume =

    Shimon Even and Yossi Shiloach , title =. Journal of the ACM , volume =. 1981 , publisher =

    1981

  31. [31]

    Italiano , title =

    Giuseppe F. Italiano , title =. Theoretical Computer Science , volume =. 1986 , publisher =

    1986

  32. [32]

    Proceedings of the 36th Annual

    Liam Roditty and Uri Zwick , title =. Proceedings of the 36th Annual. 2004 , publisher =

    2004

  33. [33]

    Proceedings of the 47th Annual

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai and Thatchaphol Saranurak , title =. Proceedings of the 47th Annual. 2015 , publisher =

    2015

  34. [34]

    Journal of the ACM , volume =

    Mikkel Thorup , title =. Journal of the ACM , volume =. 1999 , publisher =

    1999

  35. [35]

    Journal of the ACM , volume =

    Jacob Holm and Kristian de Lichtenberg and Mikkel Thorup , title =. Journal of the ACM , volume =. 2001 , publisher =

    2001

  36. [36]

    Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT) , series =

    Mikkel Thorup , title =. Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT) , series =. 2004 , publisher =

    2004

  37. [37]

    Proceedings of the 38th International Conference on Machine Learning (ICML) , series =

    Thodoris Lykouris and Sergei Vassilvitskii , title =. Proceedings of the 38th International Conference on Machine Learning (ICML) , series =. 2021 , publisher =

    2021

  38. [38]

    Advances in Neural Information Processing Systems (NeurIPS) , volume =

    Manish Purohit and Zoya Svitkina and Ravi Kumar , title =. Advances in Neural Information Processing Systems (NeurIPS) , volume =. 2018 , publisher =

    2018

  39. [39]

    Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Dhruv Rohatgi , title =. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2020 , publisher =

    2020

  40. [40]

    Communications of the ACM , volume =

    Michael Mitzenmacher and Sergei Vassilvitskii , title =. Communications of the ACM , volume =. 2021 , publisher =

    2021