Loading...
Please wait, while we are loading the content...
Similar Documents
Maximum Clique in Disk-Like Intersection Graphs
| Content Provider | arXiv |
|---|---|
| Author | Bonnet, Édouard Grelier, Nicolas Miltzow, Tillmann |
| Date of Submission | 2020-03-05 |
| Abstract | We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomial-time 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 NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes $\mathcal I$ follow the same road. They show that, for every graph $G$ of a large-enough class $\mathcal C$, the complement of an even subdivision of $G$ belongs to the intersection class $\mathcal I$. Then they conclude invoking the hardness of Maximum Independent Set on the class $\mathcal 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 subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks. |
| Related Links | https://arxiv.org/pdf/2003.02583.pdf |
| Page Count | 23 |
| arXiv | 2003.02583 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Geometry Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms Nonnumerical Algorithms and Problems Computer Science Analysis of algorithms and problem complexity Computer graphics; computational geometry |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
