moteur de recherche

Séminaire Algo - Edouard Bonnet
Séminaire Algo - Edouard Bonnet
20-Mar-2018 14:30
Age: 2 yrs

Edouard Bonnet

Description :Max Clique in Disk and Ball Graphs

Salle de séminaire (4B05R) - Bâtiment Copernic

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., 3-dimensional disk) graph, there is a 2.553-approximation due to Ashfani and Chan (while the problem is also not known to be NP-hard).We show that disk graphs and unit ball graphs do not admit the disjoint union of two odd cycles as an induced subgraph in their complement. We use this result to get an EPTAS (PTAS in time f(eps)nO(1)) and a subexponential exact algorithm for Max Clique on those two classes. 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, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, Stéphan Thomassé, and Rémi Watrigant.

<- Back to: Accueil