Bonnet, Édouard ;
Grelier, Nicolas ;
Miltzow, Tillmann
Maximum Clique in DiskLike Intersection Graphs
Abstract
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomialtime algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomialtime approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convex set.
The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NPhard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes I follow the same road. They show that, for every graph G of a largeenough class C, the complement of an even subdivision of G belongs to the intersection class I. Then they conclude by invoking the hardness of Maximum Independent Set on the class C, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. '18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponentialtime approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either halfplanes (or unit disks) or axisparallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NPhard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NPhardness for (convex) pseudodisks.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2020:13258,
author = {{\'E}douard Bonnet and Nicolas Grelier and Tillmann Miltzow},
title = {{Maximum Clique in DiskLike Intersection Graphs}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {17:117:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771740},
ISSN = {18688969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13258},
URN = {urn:nbn:de:0030drops132587},
doi = {10.4230/LIPIcs.FSTTCS.2020.17},
annote = {Keywords: Disk Graphs, Intersection Graphs, Maximum Clique, Algorithms, NPhardness, APXhardness}
}
04.12.2020
Keywords: 

Disk Graphs, Intersection Graphs, Maximum Clique, Algorithms, NPhardness, APXhardness 
Seminar: 

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 