Show simple item record

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822		*
hal.structure.identifierInstitute of Computer Science
dc.contributor.authorGiannopoulos, Panos*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierFaculty of Mathematics and Information Science [Warszawa]
dc.contributor.authorRzążewski, Pawel*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258		*
dc.date.accessioned2019-03-21T10:35:52Z
dc.date.available2019-03-21T10:35:52Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18543
dc.language.isoenen
dc.subjectdisk graphen
dc.subjectmaximum cliqueen
dc.subjectcomputational complexityen
dc.subject.ddc511en
dc.titleQPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenA (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.en
dc.identifier.citationpages12:1-12:15en
dc.relation.ispartoftitle34th International Symposium on Computational Geometry (SoCG 2018)en
dc.relation.ispartofeditorSpeckmann, Bettina
dc.relation.ispartofeditorD. Tóth, Csaba
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpublcityWadernen
dc.relation.ispartofdate2018
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-95977-066-8en
dc.relation.conftitleSoCG 2018en
dc.relation.confdate2018-06
dc.relation.confcityBudapesten
dc.relation.confcountryHungaryen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.SoCG.2018.12en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-21T10:22:03Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
LIPIcs-SoCG-2018-12.pdf
Size:
496.7Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record