
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Bonnet, Édouard; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, Pawel; Sikora, Florian (2018), QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs, in Speckmann, Bettina; D. Tóth, Csaba, 34th International Symposium on Computational Geometry (SoCG 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik : Wadern, p. 12:1-12:15. 10.4230/LIPIcs.SoCG.2018.12
View/ Open
Type
Communication / ConférenceDate
2018Conference title
SoCG 2018Conference date
2018-06Conference city
BudapestConference country
HungaryBook title
34th International Symposium on Computational Geometry (SoCG 2018)Book author
Speckmann, Bettina; D. Tóth, CsabaPublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
ISBN
978-3-95977-066-8
Pages
12:1-12:15
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, Édouard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Giannopoulos, Panos
Institute of Computer Science
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Rzążewski, Pawel
Faculty of Mathematics and Information Science [Warszawa]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time 2^{O~(n^{2/3})} for Maximum Clique on disk graphs. In stark contrast, Maximum Clique on intersection graphs of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant ratio of approximation which cannot be attained even in time 2^{n^{1-epsilon}}, unless the Exponential Time Hypothesis fails.Subjects / Keywords
disk graph; maximum clique; computational complexityRelated items
Showing items related by title and author.
-
Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2023) Article accepté pour publication ou publié
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020) Communication / Conférence
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié