QPTAS and subexponential algorithm for maximum clique on disk graphs

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 \textsc{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^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk graphs. In stark contrast, \textsc{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-\varepsilon}}$, unless the Exponential Time Hypothesis fails.

© Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, and Florian Sikora; licensed under Creative Commons License CC-BY (http://creativecommons.org/licenses/by/3.0/).

Published in: 34th International Symposium on Computational Geometry (SoCG 2018). Editors: Bettina Speckmann and Csaba D. Tóth; Article No. 12; pp. 12:1–12:15. ISBN 978-3-95977-066-8, LIPICS Vol. 99. ISSN 1868-8969