Finding a Maximum Clique in a Disk Graph
share
A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε>0. However, the maximum clique problem is known to be APX-hard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axis-parallel rectangles. Furthermore, there exists an O(n^3log n)-time algorithm to compute a maximum clique for unit disks. Here we obtain the following results. - We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5log n)-time, which improves the previously best known running time of O(n^3log n) [Eppstein '09]. - We extend a widely used `co-2-subdivision approach' to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 4448/4449 ≈ 0.9997. The use of a `co-2-subdivision approach' was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348≈ 0.9999. - We show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in [1,(1+ε)]. For example, if the minimum lens width is at least 0.265 and ε≤ 0.0001, which still allows for non-Helly triples in the arrangement, then one can find a maximum clique in polynomial time.
READ FULL TEXT
