EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- 6 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (2), 1-38
- https://doi.org/10.1145/3433160
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.Keywords
Funding Information
- French National Research Agency
- EPSRC grant FptGeom (EP/N029143/1)
- ANR grant ESIGMA (ANR-17-CE23-0010)
- “Investissements d’Avenir” (ANR-11-IDEX-0007)
- LABEX MILYON (ANR-17-CE23-0010)
- European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (714704)
- ANR Project DISTANCIA (ANR-17-CE40-0015)
This publication has 36 references indexed in Scilit:
- Approximation Algorithms for Maximum Independent Set of Pseudo-DisksDiscrete & Computational Geometry, 2012
- Sphere and Dot Product Representations of GraphsDiscrete & Computational Geometry, 2012
- Two-query PCP with subconstant errorJournal of the ACM, 2008
- Independent set of intersection graphs of convex objects in 2DComputational Geometry, 2006
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphsJournal of Algorithms, 2004
- Robust algorithms for restricted domainsJournal of Algorithms, 2003
- Polynomial-time approximation schemes for packing and piercing fat objectsJournal of Algorithms, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Geometric representations of graphsComputational Geometry, 1998
- The number of maximal independent sets in connected graphsJournal of Graph Theory, 1987