Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

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 [19, 28]. 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) [28]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: (i) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1 - ε)-approximate maximum clique in expected time Õ(n/ε²); and (ii) 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).