TY - GEN

T1 - Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

AU - Bringmann, Karl

AU - Kisfaludi-Bak, Sándor

AU - Künnemann, Marvin

AU - Nusser, André

AU - Parsaeian, Zahra

N1 - Publisher Copyright: © Karl Bringmann, Sndor Kisfaludi-Bak, Marvin Knnemann, Andr Nusser, and Zahra Parsaeian; licensed under Creative Commons License CC-BY 4.0

PY - 2022

Y1 - 2022

N2 - We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in d-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in Oe(n5/3) time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time O(n2-d) for some d > 0. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in R3 or congruent equilateral triangles in R2. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in R2. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in R12, distinguishing between diameter 2 and 3 needs quadratic time (ruling out (3/2-e)- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors. Ultimately, this fine-grained perspective may enable us to determine for which shapes we can have efficient algorithms and approximation schemes for diameter computation.

AB - We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in d-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in Oe(n5/3) time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time O(n2-d) for some d > 0. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in R3 or congruent equilateral triangles in R2. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in R2. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in R12, distinguishing between diameter 2 and 3 needs quadratic time (ruling out (3/2-e)- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors. Ultimately, this fine-grained perspective may enable us to determine for which shapes we can have efficient algorithms and approximation schemes for diameter computation.

KW - Geometric Intersection Graph

KW - Graph Diameter

KW - Hardness in P

KW - Hyperclique Detection

KW - Orthogonal Vectors

U2 - 10.4230/LIPIcs.SoCG.2022.21

DO - 10.4230/LIPIcs.SoCG.2022.21

M3 - Article in proceedings

AN - SCOPUS:85134319419

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th International Symposium on Computational Geometry, SoCG 2022

A2 - Goaoc, Xavier

A2 - Kerber, Michael

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 38th International Symposium on Computational Geometry, SoCG 2022

Y2 - 7 June 2022 through 10 June 2022

ER -