论文标题
在磁盘图的几何超类中计算最大集团
Computing a maximum clique in geometric superclasses of disk graphs
论文作者
论文摘要
在90年代的克拉克（Clark）中，科尔本（Colbourn）和约翰逊（Johnson）撰写了一份开创性的论文，他们证明可以在单位磁盘图中以多项式时间来解决最大集团。从那时起，已经研究了D维（单位）球的交点图中最大集团的复杂性。对于球图，该问题是NP-HARD，如Bonamy等人所示。 （FOCS '18）。他们还为磁盘图提供了有效的多项式时间近似方案（EPTA）。但是，在这种情况下，最大集团的复杂性仍然未知。在本文中，我们显示了单位磁盘图几何超类的多项式时间算法的存在。此外，我们给出了部分结果，以获得凸伪盘的交点图的EPTA。
In the 90's Clark, Colbourn and Johnson wrote a seminal paper where they proved that maximum clique can be solved in polynomial time in unit disk graphs. Since then, the complexity of maximum clique in intersection graphs of d-dimensional (unit) balls has been investigated. For ball graphs, the problem is NP-hard, as shown by Bonamy et al. (FOCS '18). They also gave an efficient polynomial time approximation scheme (EPTAS) for disk graphs. However, the complexity of maximum clique in this setting remains unknown. In this paper, we show the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs. Moreover, we give partial results toward obtaining an EPTAS for intersection graphs of convex pseudo-disks.
