Skip to Main content Skip to Navigation
Journal articles

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

Abstract : A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for MAXIMUM CLIQUE on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics ’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2Õ(n2/3) for MAXIMUM CLIQUE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for MAX CLIQUE on disk and unit ball graphs. MAX CLIQUE on unit ball graphs is equivalent to finding, given a collection of points in R3, a maximum subset of points with diameter at most some fixed value. In stark contrast, MAXIMUM CLIQUE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n1−ɛ, unless the Exponential Time Hypothesis fails.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03107441
Contributor : Florian Sikora Connect in order to contact the contributor
Submitted on : Tuesday, August 16, 2022 - 11:15:59 AM
Last modification on : Wednesday, September 7, 2022 - 3:43:15 AM

File

arxiv.pdf
Files produced by the author(s)

Identifiers

Citation

Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, et al.. EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩. ⟨hal-03107441⟩

Share

Metrics

Record views

95

Files downloads

0