Going Beyond Surfaces in Diameter Approximation

Michał Włodarczyk · 2025

Read Going Beyond Surfaces in Diameter Approximation by Michał Włodarczyk (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03447.txt.

Introduction

Michal Wlodarczyk speeds up a classic graph task: finding the widest gap between any two points in a network. Exact answers take too long on big graphs, and even rough answers hit a hard wall in general. Past fast methods worked only for flat or near-flat graphs. The 2025 paper pushes past that limit.

Two new methods give answers within a hair of exact, in near-linear time, for two wider graph families. One covers graphs that avoid a fixed peak-like pattern; the other covers graphs built from a flat base plus a few extra hubs. A stepping stone is a fast distance lookup tool for the first family, the first of its kind beyond flat graphs. All the methods are fixed, with no random steps.

Catalog record

CREATORMichał Włodarczyk
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03447

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Going Beyond Surfaces in Diameter Approximation Michał Włodarczyk Abstract Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3 / 2 3/2 . For planar graphs with positive edge weights, there are known ( 1 + ε ) (1+\varepsilon) -approximation algorithms with running time 𝗉𝗈𝗅𝗒 ⁡ ( 1 / ε , log ⁡ n ) ⋅ n \mathsf{poly}(1/\varepsilon,\,\log n)\cdot n . However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving ( 1 + ε ) (1+\varepsilon) -approximation algorithms with the following running times: • 𝒪 h ​ ( ( 1 / ε ) 𝒪 ⁡ ( h ) ⋅ n ​ log 2 ​ n ) \mathcal{O}_{h}((1/\varepsilon)^{\mathcal{O}(h)}\cdot n\log^{2}n) -time algorithm for graphs excluding an apex graph of size h h as a minor, • 𝒪 d ​ ( ( 1 / ε ) 𝒪 ⁡ ( d ) ⋅ n ​ log 2 ​ n ) \mathcal{O}_{d}((1/\varepsilon)^{\mathcal{O}(d)}\cdot n\log^{2}n) -time algorithm for the class of d d -apex graphs. As a stepping stone, we obtain efficient ( 1 + ε ) (1+\varepsilon) -approximate distance oracles for graphs excluding an apex graph of size h h as a minor. Our oracle has preprocessing time 𝒪 h ​ ( ( 1 / ε ) 8 ⋅ n ​ log ⁡ n ​ log ⁡ W ) \mathcal{O}_{h}((1/\varepsilon)^{8}\cdot n\log n\log W) and query time 𝒪 h ​ ( ( 1 / ε ) 2 ⋅ log ⁡ n ​ log ⁡ W ) \mathcal{O}_{h}((1/\varepsilon)^{2}\cdot\log n\log W) , where W W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic. University of Warsaw, [email protected]://orcid.org/0000-0003-0968-8414 ccs Theory of computation Graph algorithms analysis keywords diameter, approximation, distance oracles, graph minors, treewidth † † runningauthor: M. Włodarczyk † † copyright: Michał Włodarczyk † † funding: Supported by Polish National Science Centre SONATA-19 grant 2023/51/D/ST6/00155. † † editors: Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman † † event-title: 33rd Annual European Symposium on Algorithms (ESA 2025) † † event-shorttitle: ESA 2025 † † event-acronym: ESA † † year: 2025 † † event-date: September 15–17, 2025 † † event-location: Warsaw, Poland † † series-volume: 351 † † articleno: 37 alculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+eps)-approximation algorithms with running time poly(1/eps, log n) * n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+eps)-approximation algorithms with the following running times: 1. O_h((1/eps)^O(h) * n log^2 n)-time algorithm for graphs excluding an apex graph of size h as a minor, 2. O_d((1/eps)^O(d) * n log^2 n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+eps)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time O_h((1/eps)^8 * n log n log W) and query time O((1/eps)^2 * log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic. 1 Introduction The diameter of a graph G , denoted \mathsf{diam}(G) , is the largest distance between a pair of its vertices in the shortest path metric. We assume that each edge is assigned some real positive weight, and the length of a path is the sum of its weights. The obvious way to calculate \mathsf{diam}(G) is to check the distances for all vertex pairs, but this inevitably requires quadratic time. This trivial approach is essentially optimal because already unweighted graphs of diameter 2 or 3 cannot be distinguished in time \mathcal{O}(m^{1.99}) under the Strong Exponential Time Hypothesis [ 49 ] (see [ 2 ] for hardness in sparse graphs). On the other hand, truly subquadratic algorithms to compute diameter are available in planar graphs [ 10 , 34 ] and graph classes excluding a minor [ 26 , 42 , 46 ] . Still, the best algorithm for planar graphs runs in time 1 1 1 The variable n refers to the number of vertices in a graph but all the considered graph classes are sparse so the number of edges is \mathcal{O}(n) . The \tilde{\mathcal{O}} -notation hides factors polylogarithmic in n . We refer to the dependence \tilde{\mathcal{O}}(n) as almost-linear . \tilde{\mathcal{O}}(n^{5/3}) [ 34 ] , which is far from linear. The absence of fast algorithms calculating the diameter exactly led the researchers to seek fast approximation algorithms. Weimann and Yuster [ 55 ] gave the first almost-linear (1+\varepsilon) -approximation for planar diameter, running in time \tilde{\mathcal{O}}(2^{\mathcal{O}(1/\varepsilon)}\cdot n) . This was improved to randomized time \tilde{\mathcal{O}}((1/\varepsilon)^{5}\cdot n) by Chan and Skrepetos [ 12 ] (see also [ 18 ] ). Li and Parter [ 47 ] gave a deterministic algorithm of this type, as well as a distributed algorithm with a small number of rounds. Observe that each of these can be used to recognize unweighted planar graphs of diameter D , simply by setting \varepsilon=1/(2D) . There are also specialized algorithms for this task by Eppstein [ 28 ] , with running time 2^{\mathcal{O}(D\log D)}\cdot n , and by Abboud, Mozes, and Weimann [ 1 ] , with running time \tilde{\mathcal{O}}(D^{2}\cdot n) . Shortest path separators. An area that is technique-wise related is the design of approximate distance oracles. After a preprocessing step, we would like to quickly estimate any (u,v) -distance within factor (1+\varepsilon) . Thorup [ 53 ] exploited the fact that planar graphs admit balanced separators consisting of two shortest paths to give an oracle with preprocessing time \mathcal{O}((1/\varepsilon)^{2}\cdot n\log^{3}n) , space \mathcal{O}((1/\varepsilon)\cdot n\log n) , and query time \mathcal{O}(1/\varepsilon) . The shortest path separators constitute a crucial ingredient of all the three aforementioned algorithms for estimating planar diameter as well. Abraham and Gavoille [ 3 ] presented a generalization of shortest path separators to graph classes excluding a minor and extended Thorup’s oracle to such classes. However, their separators no longer enjoy such a nice structure. The main caveat is that already in a single balanced separator one might need to use paths P_{1},P_{2} such that P_{2} is a shortest path only in G-P_{1} . Hence P_{2} may be much longer than \mathsf{diam}(G) , which is easily seen to be unavoidable already in the class of apex graphs 2 2 2 G is called an apex graph if G can be made planar by removal of a single vertex. , and it is unclear how to exploit such

Read the complete text