EPTAS for Max Clique on Disks and Unit Balls

Marthe Bonamy (1, 2) , Edouard Bonnet (3) , Nicolas Bousquet (4, 2) , Pierre Charbit (5, 6) , Stéphan Thomassé (7, 3)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 CNRS - Centre National de la Recherche Scientifique
3 MC2 - Modèles de calcul, Complexité, Combinatoire
4 G-SCOP_OC - Optimisation Combinatoire
5 GANG - Networks, Graphs and Algorithms
6 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
7 IUF - Institut universitaire de France

We propose a polynomial-time algorithm which takes as input a finite set of points of ℝ3 and compute, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii. 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. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rzążewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we 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 large independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails.

Domaines: Algorithme et structure de données [cs.DS]; Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé. EPTAS for Max Clique on Disks and Unit Balls. FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.1109/FOCS.2018.00060⟩. ⟨hal-01962198⟩