Bringmann, Karl ;
Kisfaludi‑Bak, Sándor ;
Künnemann, Marvin ;
Nusser, André ;
Parsaeian, Zahra
Towards SubQuadratic Diameter Computation in Geometric Intersection Graphs
Abstract
We initiate the study of diameter computation in geometric intersection graphs from the finegrained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in ddimensional 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 nearquadratic 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 𝒪̃(n^{5/3}) time [Cabello 2019, Gawrychowski et al. 2021].
In this work we (conditionally) rule out subquadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time 𝒪(n^{2δ}) for some δ > 0. In particular, there are no subquadratic algorithms already for fat objects in small dimensions: unit balls in ℝ³ or congruent equilateral triangles in ℝ². For unit segments and congruent equilateral triangles, we can even rule out strong subquadratic approximations already in ℝ². It seems that the hardness of approximation may also depend on dimensionality: for axisparallel unit hypercubes in ℝ^{12}, distinguishing between diameter 2 and 3 needs quadratic time (ruling out (3/2ε) approximations), whereas for axisparallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in nearlinear time.
Note that many of our lower bounds match the best known algorithms up to subpolynomial factors. Ultimately, this finegrained perspective may enable us to determine for which shapes we can have efficient algorithms and approximation schemes for diameter computation.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.21,
author = {Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Nusser, Andr\'{e} and Parsaeian, Zahra},
title = {{Towards SubQuadratic Diameter Computation in Geometric Intersection Graphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {21:121:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16029},
URN = {urn:nbn:de:0030drops160294},
doi = {10.4230/LIPIcs.SoCG.2022.21},
annote = {Keywords: Hardness in P, Geometric Intersection Graph, Graph Diameter, Orthogonal Vectors, Hyperclique Detection}
}
01.06.2022
Keywords: 

Hardness in P, Geometric Intersection Graph, Graph Diameter, Orthogonal Vectors, Hyperclique Detection 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 