Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorGiannopoulos, Panos
dc.contributor.authorKim, Eun Jung
dc.contributor.authorRzazewski, Pawel
dc.contributor.authorSikora, Florian
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.person.labIds989
hal.person.labIds131976
hal.person.labIds989
hal.person.labIds161255
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record