EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
复制标题
圆盘和单位球图上最大团的 EPTAS 和次指数算法
DOI：
10.1145/3433160
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Bonamy M
中科院分区：
文献类型：
--
作者：
Bonamy M
一个（单位）圆盘图是平面上闭（单位）圆盘的交图。近三十年前，一个优雅的多项式时间算法被发现的MAXIMUMCLIQUEon单位盘图[克拉克，Colbourn，约翰逊;离散数学'90]。从那时起，它一直是一个有趣的开放性问题，是否可追溯性可以扩展到一般的磁盘图。我们证明了两个奇圈的不交并不是一个圆盘图的补图，也不是一个单位（三维）球图的补图。从这一事实和现有的结果，我们得到了一个简单的QPTAS和一个次指数算法运行的时间为2 π（n ~ 2/3）的最大化最大化在磁盘和单位球图。然后，我们得到了一个随机EPTAS计算图的独立数没有不相交的两个奇循环作为一个诱导子图，有界VC-维，和线性独立数。这，结合我们的结构结果，产生一个随机EPTAS的MAXCLIQUEon磁盘和单位球图。单位球图上的MAXCLIQUEON等价于给定R3中的一个点集，寻找直径至多为某个固定值的点的最大子集。与之形成鲜明对比的是，球图和单位四维球图上的MAXIMUMCLIQUEON，以及填充椭圆（甚至接近单位圆盘）或填充三角形的相交图不太可能有这样的算法。事实上，我们证明了，对于所有这些问题，存在一个常数的近似比，即使在时间2n 1 − n中也无法达到，除非指数时间假说失败。
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for MAXIMUMCLIQUEon unit disk graphs [Clark, Colbourn, Johnson;Discrete Mathematics’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2Õ(n2/3)for MAXIMUMCLIQUEon disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for MAXCLIQUEon disk and unit ball graphs. MAXCLIQUEon unit ball graphs is equivalent to finding, given a collection of points in R3, a maximum subset of points with diameter at most some fixed value.In stark contrast, MAXIMUMCLIQUEon ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n1−ɛ, unless the Exponential Time Hypothesis fails.
登录
查看更多内容
影响因子：
0.8
作者：
Ross J. Kang;Tobias Müller
通讯作者：
Tobias Müller
DOI：
10.1145/3055399.3055473
发表时间：
2017
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
S. Artmann;R. Weismantel;R. Zenklusen
通讯作者：
R. Zenklusen
DOI：
--
发表时间：
1998
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Warren D. Smith;N. Wormald
通讯作者：
N. Wormald
影响因子：
0.5
作者：
Christoph Ambühl;Uli Wagner
通讯作者：
Uli Wagner
3D 单位圆盘图中最大团的近似算法
DOI：
--
发表时间：
2005
期刊：
Canadian Conference on Computational Geometry
影响因子：
--
作者：
P. Afshani;Timothy M. Chan
通讯作者：
Timothy M. Chan