Pith. sign in

REVIEW 1 major objections 3 minor 45 references

On Incremental Approximate Shortest Paths in Directed Graphs

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read New data structures maintain approximate shortest paths in sparse directed graphs under edge insertions with faster total update times than previously known, and give a near-linear offline solver.

desk verdict Strong deterministic APSP and offline SSSP results, but the randomized APSP bound has a genuine proof gap in the Section 7 reset lemma that must be fixed before that claim can stand. read the letter →

arxiv 2502.10348 v1 pith:IILOEN5U submitted 2025-02-14 cs.DS

Adam Górkiewicz , Adam Karczmarz This is my paper · ORCID
classification cs.DS MSC 68W2568W2068R10
keywords incrementalshortestpathsall-pairssingle-sourceadaptiveadversaryapproximationalgorithmsdirectedgraphsofflinedynamicgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies how to keep approximate shortest-path information in directed graphs as edges are inserted. Its central move is to solve a restricted single-source version—only edges leaving the source may change—with near-linear total update time, and then to show this restricted solver can absorb whole batches of arbitrary insertions with only a small accuracy loss. This yields incremental all-pairs data structures whose total update times, for sparse graphs, are polynomial improvements over the previous best bounds against an adaptive adversary. The same ideas also produce a deterministic near-linear offline incremental single-source solver, which rules out a natural class of lower-bound arguments against online partially dynamic shortest paths.

What carries the argument

The engine is the Propagate procedure, a Dijkstra-like relaxation that only pushes a vertex when its estimate drops by a factor of at least $1+\xi$. Around it, the paper maintains a certificate system: a vertex is $k$-certified when its estimate is within $(1+\xi)^k$ of the true distance along every path in $G[V\setminus\{s\}]$, and a rank stores the smallest known $k$. Running Propagate on the complement of the certified set lifts every touched vertex from $k$-certified to $(k+1)$-certified, while untouched vertices keep their certificates; Synchronize then rebalances degree sums so that the maximum rank never exceeds $\log_2 m$, which controls the final approximation factor. The APSP construction layers this source-restricted solver over phases of $b$ updates, using shortcut edges whose weights track estimates, a complete graph on the phase endpoints maintained by a dense APSP data structure, and periodic resets to keep the rank offset small. The offline solver instead uses a recursive Search over time intervals, running Dijkstra on the midpoint graph restricted to vertices whose stored bounds are not already tight, with a charging argument bounding the total work per vertex.

What would settle it

To test the central mechanism, instrument the source-incident data structure on a small digraph and insert source edges in an order that forces repeated Propagate and Synchronize calls; then check whether every final estimate is within $(1+\xi)^{1+\log_2 m}$ of the true distance. The construction fails concretely if a vertex is touched by Propagate($V\setminus U$) without its estimate decreasing and is not promoted to rank $k+1$, or if an untouched vertex outside the touched set loses its accuracy level in the process.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that source-incident incremental SSSP is a viable primitive: a deterministic data structure explicitly maintains distance estimates $d(v)$ with $\operatorname{dist}(s,v) \leq d(v) \leq (1+\epsilon)\operatorname{dist}(s,v)$ while edges of the form $sv$ are inserted or decreased, in $O(m \log(nW) \log^2 n/\epsilon + \Delta)$ total update time. The authors then wrap this primitive in a phase-based construction—per-source and per-sink copies with shortcut edges, plus a dense incremental APSP structure on the endpoints of recent updates—to obtain deterministic incremental $(1+\epsilon)$-APSP in $O(m^{3/2}n^{3/4} \log^2(nW) \log n/\epsilon^{3/2} + \Delta)$ and a randomized adaptive-adversary version in $O(m^{4/3}n^{5/6} \log^3(nW) \log n/\epsilon^{7/3} + \Delta)$. Separately, a divide-and-conquer over time gives a deterministic offline SSSP structure with near-linear preprocessing and $O(\log\log n)$ queries, and this implies that lower bounds for online approximate partially dynamic SSSP cannot come from reductions to static problems like Min-Weight $k$-Clique.

Load-bearing premise

The load-bearing premise is that the accuracy-level bookkeeping is tight: after a propagation wave, vertices whose estimates were changed gain one level of extra allowed error, vertices whose estimates did not change keep their old accuracy level, and the highest level stays at $\log_2 m$; if this bookkeeping ever fails, the claimed $(1+\epsilon)$ guarantee collapses.

Editorial extensions

If this is right

  • For sparse directed graphs, the deterministic APSP bound improves the previous best adaptive-adversary structure by a factor of $n^{1/12}$, and the randomized one by $n^{1/6}$.
  • The source-incident SSSP primitive may be reused independently: it maintains valid path weights in near-linear total update time, and its batch-insertion extension accepts arbitrary edge batches when the stored estimates are already accurate.
  • A near-linear deterministic offline solver for approximate incremental (equivalently decremental) SSSP exists, so showing the online problem requires more time cannot be done by reductions to static $k$-clique or $k$-cycle detection.
  • The offline construction yields a deterministic near-optimal all-pairs bounded-leg shortest paths data structure for sparse graphs.
  • All maintained structures can be extended to report an approximately shortest path in near-optimal time proportional to the path length.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implicit consequence is that any future improvement to the dense APSP component transfers immediately to the sparse APSP bounds, since the phase-endpoint graph is the only quadratic-size object in the construction.
  • The source-restricted primitive might accelerate other dynamic problems whose updates arrive near a fixed root, such as maintaining bounded-hop distances or reachability certificates; the paper does not explore this.
  • The offline recursion could likely answer queries about intermediate versions between stored checkpoints by combining surrounding estimates; the paper only stores and queries per-version estimates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper presents new data structures for incremental (1+epsilon)-approximate shortest paths in weighted directed graphs. The main contributions are a deterministic incremental APSP data structure with total update time O-tilde(m^{3/2} n^{3/4}) and a Monte Carlo randomized one with O-tilde(m^{4/3} n^{5/6}) total update time, both against an adaptive adversary, improving the previous best bounds of Karczmarz and Lacki (KŁ19) for sparse graphs. The technical core is an SSSP data structure for the special case of source-incident edge insertions, built from a certificate/rank machinery inspired by CZ21 and KMG22. The paper also gives a deterministic near-linear-time offline incremental SSSP data structure with O(log log n) query time for polynomially bounded parameters, and derives an all-pairs bounded-leg shortest paths data structure as a corollary.

Significance. If the main results hold, they give the first polynomial improvements over KŁ19 for incremental approximate APSP in sparse directed graphs against an adaptive adversary, and the offline SSSP result is a clean contribution that rules out certain classes of conditional lower bounds. The deterministic APSP bound and the offline SSSP algorithm are, on my reading, supported by coherent arguments: I checked the central lemmas (3.3, 3.4, 4.5, 4.7, 4.8, 5.4, 6.1, 6.3) at a line-by-line level, and the phase-based running-time arithmetic with b = sqrt(n) and the stated p values reproduces the claimed m^{3/2} n^{3/4} and m^{4/3} n^{5/6} bounds. The randomized APSP claim, however, depends on Lemma 7.1, whose proof has a genuine gap as written; this is a load-bearing issue for the second bullet of Theorem 1.2.

major comments (1)
  1. [Section 7, Lemma 7.1] The proof of Lemma 7.1 contains an invalid inference. The text states: "Since the estimates only decrease, we also have d'(t) > (1+xi)^lambda (d(u)+w(P))" where d' denotes the estimates before Randomized-Reset and d denotes the estimates after. This inequality uses the post-reset value d(u) on the right-hand side. Later, the proof chains pre-reset estimates as d'(t) <= (1+xi)^k (d'(u0)+w(P)), and from the two inequalities concludes k > lambda. But to conclude k > lambda, one would need d'(t) > (1+xi)^lambda (d'(u0)+w(P)), because the upper bound is expressed in terms of d'(u0). Since d(u) <= d'(u0) in general, the displayed inequality is weaker and does not imply the required statement. Consequently, the conclusion k > lambda is not established. This gap invalidates the proof of Theorem 4.11 and, through the use of randomized resets in Section 5, the randomized bullet of Theorem 1.2 as written. The deterministic APSP bound and the offline SSSP result do not depend on this lemma.
minor comments (3)
  1. [Section 7, proof of Lemma 7.1] The chain d'(uk) <= (1+xi)^k (d'(u0)+w(P)) is printed as equal to (1+xi)^k * dist(s,t). The right-hand side should be d'(u0)+w(P), not dist(s,t), since d'(u0) is an estimate, not the true distance; as printed this is a typo, though it does not affect the surrounding argument.
  2. [Section 7, Algorithm 5 and Theorem 4.11] The statement of Theorem 4.11 allows any integer lambda in [1, ell], but the proof's interval-counting argument uses constants such as lambda/8 and lambda/25 and a family of lambda intervals; for small lambda, e.g., lambda < 8, the sampling range {0,...,floor(lambda/8)} degenerates. The proof should either state an explicit lower bound on lambda or handle small lambda separately, since the later application sets lambda = p log m, which is not guaranteed to be large for very small epsilon.
  3. [Section 5.2, parameter setting] The parameters p and b are set to expressions that are not guaranteed to be integers at least 1 for all allowed epsilon, m, and n (for example, p = m^{1/2} epsilon^{1/2}/(n^{1/4} log n) can be below 1 for very small epsilon). The paper should state how to round these parameters or restrict the parameter range so that the phase and reset counts are well-defined.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new bounds are proved from explicitly stated published building blocks, and the only self-citation (Karczmarz–Łącki) is used as an independent black-box theorem rather than as a fitted input.

full rationale

The paper's central claims are algorithmic derivations, not fitted or normalized empirical results. Theorem 1.1 and Theorem 4.1 are proved by constructing Propagate, certificate ranks, and Synchronize, with error bounded by Lemma 4.8 and Lemma 4.7; the resulting estimate d(t) ≤ (1+ξ)^{1+log_2 m} dist(s,t) follows from the invariants and rank bound, not from restating the desired bound. Lemma 4.9 does contain a conditional assumption, namely that before a batch insertion F the estimates satisfy d(v) ≤ (1+ξ)^α dist_{G+F}(s,v), but this is a lemma hypothesis used to derive α-certificates; the conclusion d(v) ≤ (1+ξ)^{1+ρ+log_2 m} dist_G(s,v) is obtained by chaining Lemma 4.10 and the rank argument, not by simply renaming the assumption as a prediction. Theorem 1.2 is assembled from Theorem 4.1, Lemma 4.9, Lemma 5.4, and the cited dense-APSP data structure of KŁ20; the phase argument and shortcut invariants are proved in the text. The only self-citation with author overlap is the use of [KŁ20] as Theorem 5.1, a published, parameter-free result whose stated assumptions do not include the target theorems of this paper, so it constitutes independent support rather than a circularity-raising citation. The offline SSSP result of Theorem 1.3 is a new divide-and-conquer construction with its own correctness and running-time proofs, not a renaming of a known result. The skeptical concern about Lemma 7.1 is a potential proof gap in the randomized reset argument; even if correct, that would be a correctness flaw in one auxiliary lemma, not a circularity where an output equals an input by construction. No equation or theorem in the paper reduces to its own inputs, no fitted parameter is relabeled as a prediction, and no uniqueness claim is imported from the authors' prior work to force the chosen construction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

This is a pure theory paper. There are no fitted parameters; the internal parameters b (phase length) and p (reset period) are optimized in the running-time analysis and their closed forms are derived, not assumed. The axioms listed are standard problem-setting assumptions and cited black-box results. No new physical or mathematical entities are introduced.

assumptions (6)
  • domain assumption Edge weights lie in {0} ∪ [1,W] with W polynomially bounded; all edge weights are non-negative.
    This is the problem setting stated in the abstract and Section 2; all log(nW) factors depend on it.
  • standard math Distances in an incremental graph are monotone non-increasing over time.
    Used throughout, especially in the offline algorithm (Section 6) to justify using older estimates as upper bounds.
  • domain assumption The dense APSP data structure of KŁ20 (Theorem 5.1) is correct and admits witness weights for its estimates.
    Black-box component used in Section 5 for the graph H; the APSP running time and correctness inherit from it.
  • domain assumption Weight decreases can be filtered to those shrinking an edge weight by a factor at least 1+ε, at the cost of a constant-factor loss in approximation.
    Standard reduction from Ber16 used in Section 5 to bound the number of phases by O(m log(W)/(bε)).
  • domain assumption The initial graph may be assumed to contain source edges su of weight nW for all u, so every vertex is reachable from s.
    Simplification stated in Section 4.1 and Section 6 Setup; the paper notes it can be dropped with an incremental reachability data structure.
  • standard math Randomized resets use uniformly sampled value intervals, with independent sampling across iterations.
    Standard probabilistic method used in Section 7, Algorithm 5 and Lemma 7.1, to obtain the w.h.p. certificate guarantee.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Incremental Approximate Shortest Paths in Directed Graphs." pith.science (2026). https://pith.science/paper/IILOEN5U

@misc{pith2026250210348,
  author       = {Pith},
  title        = {Pith review of: On Incremental Approximate Shortest Paths in Directed Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IILOEN5U}},
  note         = {Machine review of arXiv:2502.10348}
}
abstract

In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertions. We give more efficient incremental $(1+\epsilon)$-approximate APSP data structures that work against an adaptive adversary: a deterministic one with $\tilde{O}(m^{3/2}n^{3/4})$ total update time and a randomized one with $\tilde{O}(m^{4/3}n^{5/6})$ total update time. For sparse graphs, these both improve polynomially upon the best-known bound against an adaptive adversary. To achieve that, building on the ideas of [Chechik-Zhang, SODA'21] and [Kyng-Meierhans-Probst Gutenberg, SODA'22], we show a near-optimal $(1+\epsilon)$-approximate incremental SSSP data structure for a special case when all edge updates are adjacent to the source, that might be of independent interest. We also describe a very simple and near-optimal \emph{offline} incremental $(1+\epsilon)$-approximate SSSP data structure. While online near-linear partially dynamic SSSP data structures have been elusive so far (except for dense instances), our result excludes using certain types of impossibility arguments to rule them out. Additionally, our offline solution leads to near-optimal and deterministic all-pairs bounded-leg shortest paths data structure for sparse graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages

  1. [1]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams , Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 , pages 2005--2039. SIAM , 2025

    work page 2025

  2. [2]

    Algorithms and hardness for diameter in dynamic graphs

    Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams , and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 , volume 132 of LIPIcs , pages 13:1--13:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019

    work page 2019

  3. [3]

    Italiano, Alberto Marchetti - Spaccamela, and Umberto Nanni

    Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti - Spaccamela, and Umberto Nanni. On-line computation of minimal and maximal length paths. Theor. Comput. Sci. , 95(2):245--261, 1992

    work page 1992

  4. [4]

    Popular conjectures imply strong lower bounds for dynamic problems

    Amir Abboud and Virginia Vassilevska Williams . Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014 , pages 434--443. IEEE Computer Society, 2014

    work page 2014

  5. [5]

    Fully dynamic shortest path reporting against an adaptive adversary

    Anastasiia Alokhina and Jan van den Brand. Fully dynamic shortest path reporting against an adaptive adversary. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 3027--3039. SIAM , 2024

    work page 2024

  6. [6]

    Consequences of faster alignment of sequences

    Amir Abboud, Virginia Vassilevska Williams , and Oren Weimann. Consequences of faster alignment of sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 , volume 8572 of Lecture Notes in Computer Science , pages 39--51. Springer, 2014

    work page 2014

  7. [7]

    Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time

    Aaron Bernstein. Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009 , pages 693--702. IEEE Computer Society, 2009

    work page 2009

  8. [8]

    Maintaining shortest paths under deletions in weighted directed graphs

    Aaron Bernstein. Maintaining shortest paths under deletions in weighted directed graphs. SIAM J. Comput. , 45(2):548--574, 2016

    work page 2016

Show all 45 references
  1. [9]

    Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing

    Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 , pages 1123--1...

    2020

  2. [10]

    Deterministic decremental SSSP and approximate min-cost flow in almost-linear time

    Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental SSSP and approximate min-cost flow in almost-linear time. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 , pages 1000--1008. IEEE , 2021

    2021

  3. [11]

    Near-optimal decremental SSSP in dense weighted digraphs

    Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff - Nilsen. Near-optimal decremental SSSP in dense weighted digraphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 , pages 1112--1122. IEEE , 2020

    2020

  4. [12]

    Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel H. M. Smid, and Norbert Zeh. Approximating geometric bottleneck shortest paths. Comput. Geom. , 29(3):233--249, 2004

    2004

  5. [13]

    Improving viterbi is hard: Better runtimes imply faster clique algorithms

    Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , volume 70 of Proceedings of Machine Learning Research , pages 311--321. PMLR , 2017

    2017

  6. [14]

    Near-optimal approximate decremental all pairs shortest paths

    Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018 , pages 170--181. IEEE Computer Society, 2018

    2018

  7. [15]

    Liu, Simon Meierhans, and Maximilian Probst Gutenberg

    Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg. Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, s-t shortest path, and minimum-cost flow. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, S...

    2024

  8. [16]

    Incremental single source shortest paths in sparse digraphs

    Shiri Chechik and Tianyi Zhang. Incremental single source shortest paths in sparse digraphs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 , pages 2463--2477. SIAM , 2021

    2021

  9. [17]

    Faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths

    Shiri Chechik and Tianyi Zhang. Faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 , pages 87--99. SIAM , 2023

    2023

  10. [18]

    New tradeoffs for decremental approximate all-pairs shortest paths

    Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos. New tradeoffs for decremental approximate all-pairs shortest paths. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 , volume 297 of LIPIcs , pages 58:1--58:19. Schloss Dagstuh...

    2024

  11. [19]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM , 51(6):968--992, 2004

    2004

  12. [20]

    Bounded-leg distance and reachability oracles

    Ran Duan and Seth Pettie. Bounded-leg distance and reachability oracles. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 20081 , pages 436--445. SIAM , 2008

    2008

  13. [21]

    Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time

    Ran Duan and Hanlin Ren. Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , volume 107 of LIPIcs , pages 42:1--42:12. Schloss Dagstuhl - Leibniz-Zentrum f \...

    2018

  14. [22]

    Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan

    James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan. Making data structures persistent. J. Comput. Syst. Sci. , 38(1):86--124, 1989

    1989

  15. [23]

    An on-line edge-deletion problem

    Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. J. ACM , 28(1):1--4, 1981

    1981

  16. [24]

    Bootstrapping dynamic distance oracles

    Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. Bootstrapping dynamic distance oracles. In 31st Annual European Symposium on Algorithms, ESA 2023 , volume 274 of LIPIcs , pages 50:1--50:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023

    2023

  17. [25]

    Deterministic incremental APSP with polylogarithmic update time and stretch

    Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg. Deterministic incremental APSP with polylogarithmic update time and stretch. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 , pages 1173--1186. ACM , 2023

    2023

  18. [26]

    New algorithms and hardness for incremental single-source shortest paths in directed graphs

    Maximilian Probst Gutenberg, Virginia Vassilevska Williams , and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 , pages 153--166....

    2020

  19. [27]

    Fully dynamic biconnectivity and transitive closure

    Monika Rauch Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In 36th Annual Symposium on Foundations of Computer Science, FOCS 1995 , pages 664--672. IEEE Computer Society, 1995

    1995

  20. [28]

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

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on Theory of Computing, STOC 2014 , pages 674--683. ACM , 2014

    2014

  21. [29]

    Improved algorithms for decremental single-source reachability on directed graphs

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015 , volume 9134 of Lecture Notes in Computer Scie...

    2015

  22. [30]

    Dynamic deterministic constant-approximate distance oracles with n\( ^ \( \) \) worst-case update time

    Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with n\( ^ \( \) \) worst-case update time. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 , pages 2033--2044. IEEE , 2024

    2024

  23. [31]

    Italiano

    Giuseppe F. Italiano. Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci. , 48(3):273--281, 1986

    1986

  24. [32]

    Tight dynamic problem lower bounds from generalized BMM and omv

    Ce Jin and Yinzhan Xu. Tight dynamic problem lower bounds from generalized BMM and omv. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1515--1528. ACM , 2022

    2022

  25. [33]

    Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs

    Adam Karczmarz and Jakub ącki. Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs. In 27th Annual European Symposium on Algorithms, ESA 2019 , volume 144 of LIPIcs , pages 65:1--65:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019

    2019

  26. [34]

    Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs

    Adam Karczmarz and Jakub ącki. Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs. In 3rd Symposium on Simplicity in Algorithms, SOSA 2020 , pages 106--120. SIAM , 2020

    2020

  27. [35]

    Incremental SSSP for sparse digraphs beyond the hopset barrier

    Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. Incremental SSSP for sparse digraphs beyond the hopset barrier. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 , pages 3452--3481. SIAM , 2022

    2022

  28. [36]

    A dynamic shortest paths toolbox: Low-congestion vertex sparsifiers and their applications

    Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. A dynamic shortest paths toolbox: Low-congestion vertex sparsifiers and their applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024 , pages 1174--1183. ACM , 2024

    2024

  29. [37]

    Ryan Williams

    Andrea Lincoln, Virginia Vassilevska Williams , and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 , pages 1236--1252. SIAM , 2018

    2018

  30. [38]

    Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

    Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010 , pages 121--130. ACM , 2010

    2010

  31. [39]

    Fully dynamic all-pairs shortest paths: Likely optimal worst-case update time

    Xiao Mao. Fully dynamic all-pairs shortest paths: Likely optimal worst-case update time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024 , pages 1141--1152. ACM , 2024

    2024

  32. [40]

    Incremental approximate single-source shortest paths with predictions, 2025

    Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh. Incremental approximate single-source shortest paths with predictions, 2025. https://arxiv.org/abs/2502.08125

    2025 arXiv

  33. [41]

    On bounded leg shortest paths problems

    Liam Roditty and Michael Segal. On bounded leg shortest paths problems. Algorithmica , 59(4):583--600, 2011

    2011

  34. [42]

    On dynamic shortest paths problems

    Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica , 61(2):389--401, 2011

    2011

  35. [43]

    Combining all pairs shortest paths and all pairs bottleneck paths problems

    Tong - Wook Shinn and Tadao Takaoka. Combining all pairs shortest paths and all pairs bottleneck paths problems. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium , volume 8392 of Lecture Notes in Computer Science , pages 226--237. Springer, 2014

    2014

  36. [44]

    Fine-grained optimality of partially dynamic shortest paths and more

    Barna Saha, Virginia Vassilevska Williams , Yinzhan Xu, and Christopher Ye. Fine-grained optimality of partially dynamic shortest paths and more. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 , pages 5147--5190. SIAM , 2025

    2025

  37. [45]

    Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time

    Jan van den Brand and Danupon Nanongkai. Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , pages 436--455. IEEE Computer Society, 2019

    2019

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.