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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We propose a polynomial-time algorithm which takes as input a finite set ofpoints of $\mathbb R^3$ and compute, up to arbitrary precision, a maximumsubset with diameter at most $1$. More precisely, we give the first randomizedEPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Ourapproximation algorithm also works on disk graphs with arbitrary radii. Almostthree decades ago, an elegant polynomial-time algorithm was found for MaximumClique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics'90]. Since then, it has been an intriguing open question whether or nottractability can be extended to general disk graphs. Recently, it was shownthat the disjoint union of two odd cycles is never the complement of a diskgraph [Bonnet, Giannopoulos, Kim, Rz\k{a}\.{z}ewski, Sikora; SoCG '18]. Thisenabled the authors to derive a QPTAS and a subexponential algorithm for MaxClique on disk graphs. In this paper, we improve the approximability to arandomized EPTAS (and a deterministic PTAS). More precisely, we obtain arandomized EPTAS for computing the independence number on graphs having nodisjoint union of two odd cycles as an induced subgraph, bounded VC-dimension,and large independence number. We then address the question of computing MaxClique for disks in higher dimensions. We show that intersection graphs of unitballs, like disk graphs, do not admit the complement of two odd cycles as aninduced subgraph. This, in combination with the first result, straightforwardlyyields a randomized EPTAS for Max Clique on unit ball graphs. In starkcontrast, we show that on ball and unit 4-dimensional disk graphs, Max Cliqueis NP-hard and does not admit an approximation scheme even insubexponential-time, unless the Exponential Time Hypothesis fails.

EPTAS for Max Clique on Disks and Unit Balls