- FR
- EN
lundi 25 Février 2019, 14h, en salle A (2ième étage).
Abstract :
The complexity of finding a largest clique in a disk intersection graph is a notorious open question in computational geometry. A polynomial algorithm is known since 1990 for unit disks, and a 2-approximation for general disks is immediate from a structural result known since the fifties. For unit ball (i.e., in a 3-dimensional space) graph, there is a 2.553-approximation due to Ashfani and Chan, and the problem is also not known to be NP-hard.
We prove the first EPTAS (Polynomial Time Approximation Scheme in time f(eps)nO(1)) for computing Max Clique on those two classes. One key ingredient is that (for non apparent common reason) both these classes share a common forbidden induced subgraph : they don’t contain the disjoint union of two odd cycles as an induced subgraph in their complement. It was proven by [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG ’18] for disk graphs and we proved it for unit ball graphs.
In sharp contrast, we prove that Max Clique is APX-hard (i.e., unlikely to admit a PTAS) and ETH-hard (i.e., unlikely to admit a subexponential algorithm) in ball graphs, unit 4-dimensional graphs, and intersection graphs of ellipses with arbitrary low eccentricity.
This is joint work with Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet,
and Stéphan Thomassé.
