DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.127

New Diameter Approximations via Distance Oracle Techniques

Authors: Yael Kirkpatrick, Liam Roditty, Richard Qi, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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. 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.

Cite as

Yael Kirkpatrick, Liam Roditty, Richard Qi, and Virginia Vassilevska Williams. New Diameter Approximations via Distance Oracle Techniques. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 127:1-127:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kirkpatrick_et_al:LIPIcs.ICALP.2026.127,
  author =	{Kirkpatrick, Yael and Roditty, Liam and Qi, Richard and Vassilevska Williams, Virginia},
  title =	{{New Diameter Approximations via Distance Oracle Techniques}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{127:1--127:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.127},
  URN =		{urn:nbn:de:0030-drops-265169},
  doi =		{10.4230/LIPIcs.ICALP.2026.127},
  annote =	{Keywords: Graph Algorithms, Diameter, Distance Oracle, Approximation Algorithm}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.54

New Approximation Algorithms for Touring Regions

Authors: Benjamin Qi and Richard Qi

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, … , R_n in that order. Our main result is an O (n/√ε log{1/ε} + 1/ε)-time algorithm for touring disjoint disks. We also give an O(min(n/ε, n²/√ε))-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O(n/{ε^{d-1}} log²1/ε + 1/ε^{2d-2}) and O(n/ε^{2d-2})-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.

Cite as

Benjamin Qi and Richard Qi. New Approximation Algorithms for Touring Regions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{qi_et_al:LIPIcs.SoCG.2023.54,
  author =	{Qi, Benjamin and Qi, Richard},
  title =	{{New Approximation Algorithms for Touring Regions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.54},
  URN =		{urn:nbn:de:0030-drops-179047},
  doi =		{10.4230/LIPIcs.SoCG.2023.54},
  annote =	{Keywords: shortest paths, convex bodies, fat objects, disks}
}

Search Results

Documents authored by Qi, Richard

New Diameter Approximations via Distance Oracle Techniques

Abstract

Cite as

New Approximation Algorithms for Touring Regions

Abstract

Cite as

Thanks for your feedback!

Could not send message