English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the complexity of Maximum Clique in intersection graphs of convexobjects in the plane. On the algorithmic side, we extend the polynomial-timealgorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates ofany fixed convex set. We also generalize the efficient polynomial-timeapproximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet etal. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convexset. The main open question on that topic is the complexity of Maximum Cliquein disk graphs. It is not known whether this problem is NP-hard. We observethat, so far, all the hardness proofs for Maximum Clique in intersection graphclasses $\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 invokingthe hardness of Maximum Independent Set on the class $\mathcal C$, and the factthat the even subdivision preserves that hardness. However there is a strongevidence that this approach cannot work for disk graphs [Bonnet et al. '18]. Wesuggest a new approach, based on a problem that we dub Max Interval PermutationAvoidance, which we prove unlikely to have a subexponential-time approximationscheme. We transfer that hardness to Maximum Clique in intersection graphs ofobjects which can be either half-planes (or unit disks) or axis-parallelrectangles. That problem is not amenable to the previous approach. We hope thata scaled down (merely NP-hard) variant of Max Interval Permutation Avoidancecould help making progress on the disk case, for instance by showing theNP-hardness for (convex) pseudo-disks.

Maximum Clique in Disk-Like Intersection Graphs