Bonnet, Édouard ;
Giannopoulos, Panos ;
Kim, Eun Jung ;
Rzazewski, Pawel ;
Sikora, Florian
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Abstract
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomialtime 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^{1epsilon}}, unless the Exponential Time Hypothesis fails.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2018:8725,
author = {{\'E}douard Bonnet and Panos Giannopoulos and Eun Jung Kim and Pawel Rzazewski and Florian Sikora},
title = {{QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8725},
URN = {urn:nbn:de:0030drops87259},
doi = {10.4230/LIPIcs.SoCG.2018.12},
annote = {Keywords: disk graph, maximum clique, computational complexity}
}
2018
Keywords: 

disk graph, maximum clique, computational complexity 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

2018 