Truly Subquadratic Time Algorithms for Diameter in Geometric Intersection Graphs and Beyond
Date
Thursday, November 13, 2025 11:00 - 12:00
Speaker
Da Wei Zheng (ISTA)
Location
Office Bldg West / Ground floor / Foyer seminar room (I21.EG.128)
Series
Seminar/Talk
Host
TCS Seminar
Contact
Abstract:
A simple algorithm for computing the diameter of an unweighted n-vertex graph is to run a breadth-first search from every vertex of the graph. This leads to quadratic time algorithms for computing diameter in sparse graphs and geometric intersection graphs. There are matching fine-grained lower bounds that show that this is essentially optimal in general sparse graphs and many types of geometric intersection graphs; it is not possible to get a truly subquadratic time algorithm for diameter computation.
To contrast, we give the first truly subquadratic time algorithm, with $O^*(n^{2-1/18})$ running time, for computing the diameter of an $n$-vertex unit-disk graph. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or -divisions) which were used in all previous subquadratic time algorithms for diameter. Instead, we use low-diameter decompositions in their most elementary form. To obtain these results, we exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas with geometric data structures.
Based on joint work to appear in FOCS 2025 with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sndor Kisfaludi-Bak, and Hung Le. Arxiv: https://arxiv.org/abs/2510.16346