2026-07-22T07:02:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26056 2026-06-23T13:18:43Z ddc:004 open_access

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs Gao, Jie Gawrychowski, Paweł Giannopoulos, Panos Mulzer, Wolfgang Singh, Satyam Staals, Frank Zehavi, Meirav Maximum Clique Disk Graphs Unit Disk Graphs FPT Approximation A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jie Gao and Paweł Gawrychowski and Panos Giannopoulos and Wolfgang Mulzer and Satyam Singh and Frank Staals and Meirav Zehavi 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.20 urn:nbn:de:0030-drops-260563 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode