pith. sign in

arxiv: 1907.02266 · v1 · pith:OOMM6QP4new · submitted 2019-07-04 · 💻 cs.DS

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

Adam Karczmarz , Jakub {\L}\k{a}cki This is my paper

Pith reviewed 2026-05-25 09:32 UTC · model grok-4.3

classification 💻 cs.DS
keywords all-pairs shortest pathsdynamic algorithmsincremental algorithmsapproximationdirected graphshub setssubquadratic time
0
0 comments X

The pith

A new deterministic incremental algorithm maintains (1+ε)-approximate all-pairs distances in directed graphs with total Õ(m n^{4/3} log W / ε) update time.

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

The paper develops algorithms for dynamically maintaining a small set of hubs in directed graphs. These hubs are a collection of Õ(n/d) vertices guaranteed to lie on every shortest path whose length in hops is at least Ω(d). The hub-maintenance routines run in subquadratic time under either edge insertions or deletions and support both deterministic and Las Vegas randomized versions. The resulting hub data structure yields an incremental algorithm that keeps an explicit (1+ε)-approximate distance matrix for every pair of vertices. For any fixed ε > 0 this is the first deterministic partially-dynamic APSP result in directed graphs whose per-update cost is o(n²) independent of the number of edges.

Core claim

New subquadratic deterministic and Las Vegas algorithms maintain a set of Õ(n/d) hubs that hit every shortest path of hop-length Ω(d) under edge insertions or deletions; these routines produce the first deterministic incremental (1+ε)-approximate APSP algorithm for weighted directed graphs whose total update time is Õ(m n^{4/3} log W / ε) and that explicitly stores the distance matrix.

What carries the argument

Dynamically maintained hubs: a set of Õ(n/d) vertices that intersect every shortest path of hop-length Ω(d).

If this is right

  • An explicit (1+ε)-approximate distance matrix can be maintained under edge insertions in the stated total time.
  • Prior Monte Carlo randomized APSP algorithms can be upgraded to Las Vegas randomized versions without worsening the Õ bounds.
  • The same hub technique works for both incremental and decremental settings.
  • The result holds for weighted directed graphs with integer weights in [1, W].

Where Pith is reading between the lines

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

  • The subquadratic hub maintenance may extend to other path-hitting problems such as dynamic reachability or distance oracles.
  • If the hub size or maintenance cost can be further reduced, the same framework could yield even faster APSP updates.
  • The deterministic guarantee removes the need for randomness in applications that require worst-case correctness.

Load-bearing premise

A set of Õ(n/d) hubs hitting all shortest paths of hop-length Ω(d) can be maintained under edge insertions or deletions using subquadratic time algorithms.

What would settle it

A proof or counter-example showing that no subquadratic-time algorithm can maintain such a hub set under a sequence of insertions (or deletions) would falsify the claimed running times.

read the original abstract

We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in $\widetilde{O}(mn^{4/3}\log{W}/\epsilon)$ total time (where the edge weights are from $[1,W]$) and explicitly maintains a $(1+\epsilon)$-approximate distance matrix. For a fixed $\epsilon>0$, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is $o(n^2)$ regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC'02, Bernstein STOC'13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the $\widetilde{O}(\cdot)$ notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of $\widetilde{O}(n/d)$ vertices which hit a shortest path between each pair of vertices, provided it has hop-length $\Omega(d)$. We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.

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 claims new deterministic and Las Vegas randomized algorithms for dynamically maintaining a set of Õ(n/d) hubs that hit all shortest paths of hop length Ω(d) under edge insertions or deletions in weighted directed graphs. These hub algorithms are used to obtain a deterministic incremental (1+ε)-approximate APSP algorithm with total update time Õ(m n^{4/3} log W / ε) that explicitly maintains the distance matrix, claimed to be the first deterministic partially dynamic directed APSP result with o(n²) update time independent of m; prior Monte Carlo randomized algorithms are also upgraded to Las Vegas without worsening the Õ bounds.

Significance. If the hub maintenance results and the reduction to APSP hold, the work would advance dynamic graph algorithms by supplying the first deterministic subquadratic-update directed APSP primitive and a reusable hub-maintenance tool. The explicit distance-matrix maintenance and the Monte Carlo to Las Vegas improvement are concrete strengths that could influence follow-up work on dynamic shortest paths.

major comments (2)
  1. [Abstract] Abstract: The total update time Õ(m n^{4/3} log W / ε) is asserted to imply an update time of o(n²) 'regardless of the number of edges.' When m = Θ(n²) the total time becomes Õ(n^{10/3} log W / ε). The manuscript must derive the resulting amortized or per-update time explicitly (including dependence on the number of updates u) and confirm it remains o(n²) for arbitrary m; this relation is load-bearing for the main novelty claim.
  2. [Hub maintenance sections] The hub-maintenance algorithms are the central primitive supporting both the deterministic and Las Vegas APSP results. The specific subquadratic time bounds for maintaining the Õ(n/d) hubs (under insertions and under deletions separately) and the choice of d that yields the stated APSP bound must be stated and proved; without these the reduction from APSP to hubs cannot be verified.
minor comments (1)
  1. [Introduction] Ensure the definition of the Õ notation and the precise meaning of 'total time' versus amortized update time are stated uniformly in the introduction and technical sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the thorough review. We respond to the major comments point-by-point below. We will revise the manuscript to address the concerns raised regarding the abstract claim and the explicit hub maintenance bounds.

read point-by-point responses

  1. Referee: [Abstract] The total update time Õ(m n^{4/3} log W / ε) is asserted to imply an update time of o(n²) 'regardless of the number of edges.' When m = Θ(n²) the total time becomes Õ(n^{10/3} log W / ε). The manuscript must derive the resulting amortized or per-update time explicitly (including dependence on the number of updates u) and confirm it remains o(n²) for arbitrary m; this relation is load-bearing for the main novelty claim.

    Authors: We agree that this point requires clarification. The total update time bound of Õ(m n^{4/3} log W / ε) is for processing any sequence of updates. The amortized update time is therefore Õ(m n^{4/3} log W / (ε u)). This quantity is o(n²) as long as u = ω(m n^{4/3}/n²) = ω(m/n^{2/3}). When m = Θ(n²), this requires u = ω(n^{4/3}), which holds for sufficiently long update sequences. We will revise the abstract to state the amortized time explicitly and add a discussion in the introduction confirming the condition under which the o(n²) bound holds for arbitrary m. We believe this preserves the novelty as the first deterministic result with this property under standard assumptions on update sequence length. revision: yes

  2. Referee: [Hub maintenance sections] The hub-maintenance algorithms are the central primitive supporting both the deterministic and Las Vegas APSP results. The specific subquadratic time bounds for maintaining the Õ(n/d) hubs (under insertions and under deletions separately) and the choice of d that yields the stated APSP bound must be stated and proved; without these the reduction from APSP to hubs cannot be verified.

    Authors: The hub maintenance results are presented in Sections 3 (deterministic) and 4 (Las Vegas), with the APSP reduction in Section 5. To make the reduction verifiable, we will add explicit statements of the time bounds for hub maintenance under insertions and deletions separately, along with the specific choice of d that yields the APSP bound. We will also include a high-level proof overview of how the hub maintenance time combines with the APSP reduction to achieve the stated total update time. These additions will be made in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces new subquadratic algorithms for dynamically maintaining a set of Õ(n/d) hubs that hit all long shortest paths, then composes them to obtain the stated APSP update bounds. This is a direct algorithmic construction rather than a reduction to fitted parameters, self-definitions, or prior self-citations. The hub-maintenance primitive is presented as the novel contribution whose running time directly yields the APSP result; no equation or claim is shown to be equivalent to its own input by construction. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph theory assumptions rather than new entities or fitted parameters.

axioms (1)
  • domain assumption Graphs are directed with positive integer edge weights bounded by W
    Explicitly used to state the update time bound in the abstract.

pith-pipeline@v0.9.0 · 5771 in / 1102 out tokens · 47432 ms · 2026-05-25T09:32:46.131350+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

31 extracted references · 31 canonical work pages

  1. [1]

    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 Com- puter Science, FOCS 2014, Philadelphia, PA, USA, October 18 -21, 2014 , pages 434–443, 2014. doi:10.1109/FOCS.2014.53

    work page doi:10.1109/focs.2014.53 2014

  2. [2]

    Fully dynamic all-pairs shortest paths with worst-case update-time revisited

    Ittai Abraham, Shiri Chechik, and Sebastian Krinninger . Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 201 7, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 440–452. SIAM, 2017. doi:10.1137/1.978161...

    work page doi:10.1137/1.9781611974782.28 2017

  3. [3]

    Italiano, Alberto Marche tti-Spaccamela, and Umberto Nanni

    Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marche tti-Spaccamela, and Umberto Nanni. In- cremental algorithms for minimal length paths. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San F rancisco, California, USA. , pages 12–21, 1990

    work page 1990

  4. [4]

    Im proved decremental algorithms for maintaining transitive closure and all-pairs shortest pat hs

    Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Im proved decremental algorithms for maintaining transitive closure and all-pairs shortest pat hs. J. Algorithms , 62(2):74–92, 2007. doi:10.1016/j.jalgor.2004.08.004

    work page doi:10.1016/j.jalgor.2004.08.004 2007

  5. [5]

    Maintaining shortest paths under dele tions in weighted directed graphs

    Aaron Bernstein. Maintaining shortest paths under dele tions in weighted directed graphs. SIAM J. Comput., 45(2):548–574, 2016. doi:10.1137/130938670

    work page doi:10.1137/130938670 2016

  6. [6]

    Improved dynamic algo rithms for maintaining approximate shortest paths under deletions

    Aaron Bernstein and Liam Roditty. Improved dynamic algo rithms for maintaining approximate shortest paths under deletions. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, Californ ia, USA, January 23-25, 2011 , pages 1355–1365, 2011. doi:10.1137/1.9781611973082.104

    work page doi:10.1137/1.9781611973082.104 2011

  7. [7]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. Fully dynami c transitive closure: Breaking through the O(n2) barrier. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 381–389, 2000. doi:10.1109/SFCS.2000.892126

    work page doi:10.1109/sfcs.2000.892126 2000

  8. [8]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. A new approac h to dynamic all pairs shortest paths. J. ACM , 51(6):968–992, 2004. doi:10.1145/1039488.1039492

    work page doi:10.1145/1039488.1039492 2004

  9. [9]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. Fully dynami c all pairs shortest paths with real edge weights. J. Comput. Syst. Sci. , 72(5):813–837, 2006. doi:10.1016/j.jcss.2005.05.005

    work page doi:10.1016/j.jcss.2005.05.005 2006

  10. [10]

    An on-line edge-deleti on problem

    Shimon Even and Yossi Shiloach. An on-line edge-deleti on problem. J. ACM , 28(1):1–4, 1981. doi:10.1145/322234.322235

    work page doi:10.1145/322234.322235 1981

  11. [11]

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

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Sublinear-time decremental algorithms for single-source reachability and shortest pa ths on directed graphs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - Jun e 03, 2014 , pages 674–683,

    work page 2014

  12. [12]

    doi:10.1145/2591796.2591869

    work page doi:10.1145/2591796.2591869

  13. [13]

    A subquadratic-time algorithm for decremental single-source shortest paths

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. A subquadratic-time algorithm for decremental single-source shortest paths. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Ore gon, USA, January 5-7, 2014 , pages 1053–1072, 2014. doi:10.1137/1.9781611973402.79

    work page doi:10.1137/1.9781611973402.79 2014

  14. [14]

    Improved algorithms for decre- mental single-source reachability on directed graphs

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Improved algorithms for decre- mental single-source reachability on directed graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, J uly 6-10, 2015, Proceedings, Part I , pages 725–736, 2015. doi:10.1007/978-3-662-47672-7\_59

    work page doi:10.1007/978-3-662-47672-7 2015

  15. [15]

    Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM J. Comput. , 45(3):947– 1006, 2016. doi:10.1137/140957299. 18

    work page doi:10.1137/140957299 2016

  16. [16]

    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, M ilwaukee, Wisconsin, USA, 23-25 October 1995, pages 664–672, 1995. doi:10.1109/SFCS.1995.492668

    work page doi:10.1109/sfcs.1995.492668 1995

  17. [17]

    Randomized dy namic graph algorithms with poly- logarithmic time per operation

    Monika Rauch Henzinger and Valerie King. Randomized dy namic graph algorithms with poly- logarithmic time per operation. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada , USA , pages 519–527, 1995. doi:10.1145/225058.225269

    work page doi:10.1145/225058.225269 1995

  18. [18]

    Poly-logarithmic deterministic fully- dynamic algorithms for connectivity, minimum spanning tre e, 2-edge, and biconnectivity

    Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup . Poly-logarithmic deterministic fully- dynamic algorithms for connectivity, minimum spanning tre e, 2-edge, and biconnectivity. J. ACM , 48(4):723–760, 2001. doi:10.1145/502090.502095

    work page doi:10.1145/502090.502095 2001

  19. [19]

    Kapron, Valerie King, and Ben Mountjoy

    Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynami c graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposiu m on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, Januar y 6-8, 2013 , pages 1131–1142, 2013. doi:10.1137/1.9781611973105.81

    work page doi:10.1137/1.9781611973105.81 2013

  20. [20]

    Fully dynamic algorithms for maintainin g all-pairs shortest paths and transitive closure in digraphs

    Valerie King. Fully dynamic algorithms for maintainin g all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science, F OCS ’99, 17-18 October, 1999, New York, NY, USA , pages 81–91, 1999. doi:10.1109/SFFCS.1999.814580

    work page doi:10.1109/sffcs.1999.814580 1999

  21. [21]

    Improved dynamic reachabil ity algorithms for directed graphs

    Liam Roditty and Uri Zwick. Improved dynamic reachabil ity algorithms for directed graphs. SIAM J. Comput. , 37(5):1455–1471, 2008. doi:10.1137/060650271

    work page doi:10.1137/060650271 2008

  22. [22]

    On dynamic shortest paths pr oblems

    Liam Roditty and Uri Zwick. On dynamic shortest paths pr oblems. Algorithmica, 61(2):389–401,

    work page

  23. [23]

    doi:10.1007/s00453-010-9401-5

    work page doi:10.1007/s00453-010-9401-5

  24. [24]

    Dynamic approximate all-pa irs shortest paths in undirected graphs

    Liam Roditty and Uri Zwick. Dynamic approximate all-pa irs shortest paths in undirected graphs. SIAM J. Comput. , 41(3):670–683, 2012. doi:10.1137/090776573

    work page doi:10.1137/090776573 2012

  25. [25]

    Dynamic transitive closure via dynam ic matrix inverse (extended abstract)

    Piotr Sankowski. Dynamic transitive closure via dynam ic matrix inverse (extended abstract). In 45th Symposium on Foundations of Computer Science (FOCS 200 4), 17-19 October 2004, Rome, Italy, Proceedings, pages 509–517, 2004. doi:10.1109/FOCS.2004.25

    work page doi:10.1109/focs.2004.25 2004

  26. [26]

    A data s tructure for dynamic trees

    Daniel Dominic Sleator and Robert Endre Tarjan. A data s tructure for dynamic trees. J. Comput. Syst. Sci. , 26(3):362–391, 1983. doi:10.1016/0022-0000(83)90006-5

    work page doi:10.1016/0022-0000(83)90006-5 1983

  27. [27]

    Dynamic trees as search trees via e uler tours, applied to the network simplex algorithm

    Robert Endre Tarjan. Dynamic trees as search trees via e uler tours, applied to the network simplex algorithm. Math. Program., 77:169–177, 1997. doi:10.1007/BF02614369

    work page doi:10.1007/bf02614369 1997

  28. [28]

    Near-optimal fully-dynamic graph conn ectivity

    Mikkel Thorup. Near-optimal fully-dynamic graph conn ectivity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000 , Portland, OR, USA , pages 343–350, 2000. doi:10.1145/335305.335345

    work page doi:10.1145/335305.335345 2000

  29. [29]

    Ullman and Mihalis Yannakakis

    Jeffrey D. Ullman and Mihalis Yannakakis. High-probabi lity parallel transitive-closure algorithms. SIAM J. Comput. , 20(1):100–125, 1991. doi:10.1137/0220006

    work page doi:10.1137/0220006 1991

  30. [30]

    Faster deterministic fully-d ynamic graph connectivity

    Christian Wulff-Nilsen. Faster deterministic fully-d ynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algor ithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , pages 1757–1769, 2013. doi:10.1137/1.9781611973105.126

    work page doi:10.1137/1.9781611973105.126 2013

  31. [31]

    All pairs shortest paths using bridging sets and rectangular matrix multiplication

    Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289–317, 2002. doi:10.1145/567112.567114. 19 A Deterministic Incremental Algorithm for Dense Graphs Let us focus on the restricted version of the problem – this as sumption can be dropped by applying Lemma 2.1. So, ∆ = O(n2 log W/ǫ ). Let use k = ⌈...

    work page doi:10.1145/567112.567114 2002