pith. sign in

arxiv: 2604.27142 · v1 · submitted 2026-04-29 · 💻 cs.DS

New Diameter Approximations via Distance Oracle Techniques

Yael Kirkpatrick , Liam Roditty , Richard Qi , Virginia Vassilevska Williams This is my paper

Pith reviewed 2026-05-07 09:48 UTC · model grok-4.3

classification 💻 cs.DS
keywords diameter approximationdistance oraclesderandomizationshortest pathsgraph algorithmsapproximation algorithmsundirected graphs
0
0 comments X

The pith

A structural link between diameter approximation schemes and approximate distance oracles permits the first deterministic tradeoffs for computing graph diameters.

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

The paper shows that the leading randomized method for approximating the diameter of an undirected graph shares a close structural resemblance with a standard construction for building approximate distance oracles. This resemblance makes it possible to apply known derandomization techniques directly to the diameter problem. The result is a family of deterministic algorithms that achieve the same approximation factors and running-time tradeoffs previously available only in the randomized setting. The same transfer of techniques also produces additional deterministic diameter approximations and removes randomization from several other shortest-paths results.

Core claim

The paper establishes that the current best-known diameter approximation scheme is intimately connected to the (2k-1)-approximate distance oracle construction. This connection lets the derandomization methods developed for oracles be carried over to diameter computation without loss of approximation quality or asymptotic runtime. Consequently the first deterministic diameter approximation tradeoff is obtained, together with further deterministic algorithms derived from other oracle techniques and the derandomization of multiple existing shortest-paths approximation results.

What carries the argument

The structural connection between a diameter approximation scheme and an approximate distance oracle that carries derandomization techniques across while preserving the exact approximation factor and time tradeoff.

If this is right

  • The first deterministic approximation tradeoff for undirected graph diameter is now available.
  • Additional deterministic diameter approximation algorithms arise from derandomizing other distance-oracle techniques.
  • Many existing best-known results in shortest-paths approximation can be made deterministic using the same methods.

Where Pith is reading between the lines

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

  • The same linkage may extend to directed graphs, where conditional lower bounds already exist but deterministic upper bounds are still missing.
  • The connection suggests that other hard graph problems currently solved only with randomization could be derandomized by searching for analogous oracle-style structures.

Load-bearing premise

The resemblance between the diameter approximation scheme and the distance oracle is tight enough that derandomization can be transferred without degrading the stated approximation ratio or runtime bounds.

What would settle it

An explicit graph family on which the derandomized procedure either returns a worse approximation ratio than the original randomized scheme or exceeds the claimed running time would falsify the claim.

read the original abstract

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter has not been improved. Moreover, this scheme is randomized and no similar deterministic scheme is known. Another fundamental field of research in shortest paths computation is the construction of approximate distance oracles. Thorup and Zwick [JACM'05] provided the first such distance oracle with constant query time and (conditionally) optimal space, and in the years since many advances have led to a vast toolbox of techniques and data structures. These two areas of research seem natural to combine since they both concern approximating shortest paths. However, the known diameter approximation algorithms only use a small subset of the techniques used in distance oracles research. In this work we show that in fact approximate diameter and distance oracles are intricately connected. We first demonstrate a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi ("CGR") and the $(2k-1)$-approximate distance oracle of Thorup and Zwick. This allows us to derandomize the CGR algorithm and obtain the first deterministic diameter approximation tradeoff. We further derandomize other central techniques in the field of distance oracles and use them to achieve new deterministic diameter approximation algorithms. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations.

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

1 major / 1 minor

Summary. The paper establishes a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi (CGR) and the (2k-1)-approximate distance oracle of Thorup and Zwick. This allows derandomization of the CGR algorithm to obtain the first deterministic diameter approximation tradeoff. The authors further derandomize other central techniques in distance oracles and use them to achieve new deterministic diameter approximation algorithms, as well as derandomizing many current best known results in various fields of shortest paths approximations.

Significance. If the results hold, this would be a significant contribution by linking two important areas in graph algorithms research. It provides the first deterministic schemes for approximating graph diameter with tradeoffs, addressing the lack of deterministic algorithms despite known randomized ones and conditional lower bounds. The extensions to other shortest paths problems add to its impact.

major comments (1)
  1. [Abstract] The central claim depends on the CGR-TZ structural connection being tight enough for direct transfer of derandomization techniques while preserving the exact approximation factor and time tradeoff. The abstract provides no proof sketches or lemmas to verify this, particularly regarding whether the diameter-specific reduction introduces any hidden randomness that could affect the guarantees.
minor comments (1)
  1. Consider adding a high-level overview of the key technical steps in the introduction for better accessibility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for recognizing the significance of linking diameter approximation schemes to distance oracles. We address the single major comment below and will revise the manuscript accordingly to improve clarity.

read point-by-point responses

  1. Referee: [Abstract] The central claim depends on the CGR-TZ structural connection being tight enough for direct transfer of derandomization techniques while preserving the exact approximation factor and time tradeoff. The abstract provides no proof sketches or lemmas to verify this, particularly regarding whether the diameter-specific reduction introduces any hidden randomness that could affect the guarantees.

    Authors: The full manuscript (Section 3) contains the detailed proof of the CGR-TZ structural connection. Lemma 3.1 establishes a direct, deterministic reduction from the Cairo-Grossi-Rizzi diameter approximation to the Thorup-Zwick (2k-1)-approximate distance oracle that preserves both the approximation factor and the time tradeoff exactly. The diameter-specific reduction introduces no additional randomness; the sole source of randomness is the sampling step already present in the Thorup-Zwick construction, which is derandomized by the techniques introduced in the paper (see also the derandomization of the TZ sampling in Section 4). We will add a concise proof sketch to the abstract (or a new paragraph in the introduction) that references this lemma and explicitly states the deterministic character of the reduction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation builds on independent external priors

full rationale

The paper's central contribution is a new structural connection between the external CGR diameter scheme and the external Thorup-Zwick (2k-1)-oracle construction, followed by transfer of known derandomization techniques from the latter. No equations or steps in the provided abstract reduce a claimed prediction or uniqueness result to a fitted parameter or self-citation chain internal to this work. The derandomization claim rests on the newly demonstrated link rather than on any prior result by these authors being invoked as a uniqueness theorem. The work is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard graph-theoretic assumptions and prior algorithmic constructions; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard assumptions of undirected graphs having well-defined shortest paths and the existence of the cited CGR and Thorup-Zwick constructions.
    The paper invokes these background results to establish the connection and derandomization.

pith-pipeline@v0.9.0 · 5616 in / 1177 out tokens · 49115 ms · 2026-05-07T09:48:43.198638+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

45 extracted references · 45 canonical work pages

  1. [1]

    Abboud, K

    A. Abboud, K. Bringmann, and N. Fischer. Stronger 3-sum lower bounds for approximate distance oracles via additive combinatorics. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 391–404. ACM, 2023. 3

    work page 2023

  2. [2]

    Abboud, K

    A. Abboud, K. Bringmann, S. Khoury, and O. Zamir. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. InSTOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1487–1500. ACM, 2022. 3

    work page 2022

  3. [3]

    Abboud, M

    A. Abboud, M. Dalirrooyfard, R. Li, and V. Vassilevska Williams. On diameter approximation in directed graphs. In I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, and G. Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 ofLIPIcs, pages 2:1–2:17. Schloss Dagstuhl - Leibniz-Zent...

    work page 2023

  4. [4]

    Abboud, V

    A. Abboud, V. Vassilevska Williams, and J. Wang. Approximation and fixed parameter sub- quadratic algorithms for radius and diameter in sparse graphs. InProceedings of the Twenty- Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 377––391, USA, 2016. Society for Industrial and Applied Mathematics. 6

    work page 2016

  5. [5]

    Aingworth, C

    D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication).SIAM Journal on Computing, 28(4):1167–1181, 1999. 2, 3, 4, 7

    work page 1999

  6. [6]

    Akav and L

    M. Akav and L. Roditty. An almost 2-approximation for all-pairs of shortest paths in sub- quadratic time. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1–11, 2020. 3, 4, 15, 16

    work page 2020

  7. [7]

    Alman, R

    J. Alman, R. Duan, V. Vassilevska Williams, Y. Xu, Z. Xu, and R. Zhou. More asymmetry yields faster matrix multiplication. In36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039. SIAM, 2025. 2

    work page 2025

  8. [8]

    Backurs, L

    A. Backurs, L. Roditty, G. Segal, V. V. Williams, and N. Wein. Towards tight approximation bounds for graph diameter and eccentricities. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 267–280, 2018. 2, 4, 5, 6, 19

    work page 2018

  9. [9]

    Baswana and T

    S. Baswana and T. Kavitha. Faster algorithms for all-pairs approximate shortest paths in undirected graphs.SIAM Journal on Computing, 39(7):2865–2896, 2010. 5, 6, 7, 13 22

    work page 2010

  10. [10]

    Berger, J

    A. Berger, J. Kaufmann, and V. Vassilevska Williams. Approximating Min-Diameter: Standard and Bichromatic. In31st Annual European Symposium on Algorithms (ESA 2023), volume 274 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:14, 2023. 6

    work page 2023

  11. [11]

    E. Bonnet. Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. In M. Bläser and B. Monmege, editors,38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 ofLeibniz International Proceedings in Informat- ics (LIPIcs), pages 17:1–17:13, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentr...

    work page 2021

  12. [12]

    Cairo, R

    M. Cairo, R. Grossi, and R. Rizzi. New bounds for approximating extremal distances in undirected graphs. InProceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 363–376. SIAM, 2016. 2, 3, 4, 5, 8

    work page 2016

  13. [13]

    Calabro, R

    C. Calabro, R. Impagliazzo, and R. Paturi. On the exact complexity of evaluating quantified k-cnf. In V. Raman and S. Saurabh, editors,Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 ofLecture Notes in Computer Science, pages 50–59. Springer, 2010. 2

    work page 2010

  14. [14]

    S. Chechik. Approximate distance oracles with constant query time. InProceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 654–663, 2014. 3

    work page 2014

  15. [15]

    Chechik, D

    S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. V. Williams. Better approximation algorithms for the graph diameter. InProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, page 1041–1052, USA,

    work page

  16. [16]

    2, 4, 5, 8, 13, 15

    Society for Industrial and Applied Mathematics. 2, 4, 5, 8, 13, 15

    work page

  17. [17]

    Chechik and T

    S. Chechik and T. Zhang. Constant approximation of min-distances in near-linear time. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 896–906. IEEE, 2022. 6

    work page 2022

  18. [18]

    Choudhary and O

    K. Choudhary and O. Gold. Extremal distances in directed graphs: Tight spanners and near- optimal approximation algorithms. InProceedings of the Fourteenth Annual ACM-SIAM Sym- posium on Discrete Algorithms, pages 495–514. SIAM, 2020. 4, 19

    work page 2020

  19. [19]

    Cohen and U

    E. Cohen and U. Zwick. All-pairs small-stretch paths.Journal of Algorithms, 38(2):335–353,

    work page

  20. [20]

    Announced at SODA 1997. 7

    work page 1997

  21. [21]

    Dalirrooyfard and J

    M. Dalirrooyfard and J. Kaufmann. Approximation Algorithms for Min-Distance Problems in DAGs. In48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 60:1– 60:17, 2021. 6

    work page 2021

  22. [22]

    Dalirrooyfard, R

    M. Dalirrooyfard, R. Li, and V. Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs.J. ACM, 72(1), Jan. 2025. 5

    work page 2025

  23. [23]

    Dalirrooyfard, V

    M. Dalirrooyfard, V. Vassilevska Williams, N. Vyas, and N. Wein. Tight approximation algo- rithms for bichromatic graph diameter and related problems. In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, editors,46th International Colloquium on Automata, Languages, 23 and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 ofLI...

    work page 2019

  24. [24]

    Dalirrooyfard, V

    M. Dalirrooyfard, V. Vassilevska Williams, N. Vyas, N. Wein, Y. Xu, and Y. Yu. Approxima- tion Algorithms for Min-Distance Problems. In46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:14, 2019. 6

    work page 2019

  25. [25]

    Dalirrooyfard and N

    M. Dalirrooyfard and N. Wein. Tight conditional lower bounds for approximating diameter in directed graphs. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1697–1710, 2021. 5

    work page 2021

  26. [26]

    M. Deng, Y. Kirkpatrick, V. Rong, V. Vassilevska Williams, and Z. Zhong. New additive approximations for shortest paths and cycles. In49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 50:1–50:10, 2022. 7

    work page 2022

  27. [27]

    D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths.SIAM Journal on Com- puting, 29(5):1740–1759, 2000. 2, 6, 7

    work page 2000

  28. [28]

    M. Dory, S. Forster, Y. Kirkpatrick, Y. Nazari, V. Vassilevska Williams, and T. de Vos. Fast 2-approximate all-pairs shortest paths. InProceedings of the 2024 Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA), pages 4728–4757. SIAM, 2024. 7

    work page 2024

  29. [29]

    A. Dürr. Improved bounds for rectangular monotone min-plus product and applications.In- formation Processing Letters, page 106358, 2023. 7

    work page 2023

  30. [30]

    Impagliazzo and R

    R. Impagliazzo and R. Paturi. On the complexity of k-sat.Journal of Computer and System Sciences, 62(2):367–375, 2001. 2

    work page 2001

  31. [31]

    Jin and Y

    C. Jin and Y. Xu. Removing additive structure in 3sum-based reductions. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 405–418. ACM, 2023. 3

    work page 2023

  32. [32]

    T. Kavitha. Faster algorithms for all-pairs small stretch distances in weighted graphs.Algo- rithmica, 63(1-2):224–245, 2012. Announced at FSTTCS 2007. 7

    work page 2012

  33. [33]

    M. B. T. Knudsen. Additive spanners and distance oracles in quadratic time, 2017. 6

    work page 2017

  34. [34]

    R. Li. Settling seth vs. approximate sparse directed unweighted diameter (up to (nu)nseth). InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1684–1696, New York, NY, USA, 2021. Association for Computing Machinery. 5

    work page 2021

  35. [35]

    Patrascu, L

    M. Patrascu, L. Roditty, and M. Thorup. A new infinity of distance oracles for sparse graphs. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 738–747. IEEE, 2012. 3

    work page 2012

  36. [36]

    Pˇ atraşcu and L

    M. Pˇ atraşcu and L. Roditty. Distance oracles beyond the thorup–zwick bound.SIAM Journal on Computing, 43(1):300–311, 2014. 3, 4, 13, 14 24

    work page 2014

  37. [37]

    L. Roditty. New algorithms for all pairs approximate shortest paths. In B. Saha and R. A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 309–320. ACM, 2023. 7

    work page 2023

  38. [38]

    Roditty, M

    L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. InAutomata, Languages and Programming, 32nd International Collo- quium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 ofLecture Notes in Computer Science, pages 261–272. Springer, 2005. 3, 5, 6, 7, 8, 11

    work page 2005

  39. [39]

    Roditty and V

    L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. InProceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 515–524, New York, NY, USA, 2013. Association for Computing Machinery. 2, 3, 5, 8, 13

    work page 2013

  40. [40]

    Saha and C

    B. Saha and C. Ye. Faster approximate all pairs shortest paths. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4758–4827. SIAM,

    work page 2024

  41. [41]

    Thorup and U

    M. Thorup and U. Zwick. Compact routing schemes. InProceedings of the Thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1–10, 2001. 4, 6, 11

    work page 2001

  42. [42]

    Thorup and U

    M. Thorup and U. Zwick. Approximate distance oracles.J. ACM, 52(1):1–24, Jan. 2005. 2, 3, 8

    work page 2005

  43. [43]

    R. R. Williams. Faster all-pairs shortest paths via circuit complexity.SIAM J. Comput., 47(5):1965–1985, 2018. 2

    work page 1965

  44. [44]

    Wulff-Nilsen

    C. Wulff-Nilsen. Approximate distance oracles with improved query time. InProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 539–549. SIAM,

    work page

  45. [45]

    U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289–317, 2002. 2 25

    work page 2002