2026-09-08T02:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26516 2026-09-05T19:46:13Z ddc:004 open_access

New Diameter Approximations via Distance Oracle Techniques Kirkpatrick, Yael Roditty, Liam Qi, Richard Vassilevska Williams, Virginia Graph Algorithms Diameter Distance Oracle Approximation Algorithm 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. As computing the exact diameter in m-edge graphs requires m^{2-o(1)} time under the Strong Exponential Time Hypothesis, much work has gone into approximating this parameter. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs [Dalirrooyfard, Li and Vassilevska W., FOCS'21]. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter [Cairo-Grossi-Rizzi, SODA 2016] 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, including a simpler 3/2-approximation with no additive error and a new 5/3-approximation, the first new step in the diameter approximation tradeoff in almost a decade. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yael Kirkpatrick and Liam Roditty and Richard Qi and Virginia Vassilevska Williams 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.127 urn:nbn:de:0030-drops-265169 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.127 eng https://creativecommons.org/licenses/by/4.0/legalcode