A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
复制标题
低度图中图交叉数的次多项式逼近算法
DOI：
10.1145/3519935.3519984
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tan, Zihan
中科院分区：
文献类型：
--
作者：
Chuzhoy, Julia;Tan, Zihan
我们考虑经典的最小交叉数问题：给定一个顶点图G，计算G在平面上的一个绘图，同时最小化它的边的像之间的交叉数。这是一个基本的和广泛研究的问题，其近似状态是广泛开放的。在目前已知的所有近似算法中，近似因子多项式地依赖于G中的最大顶点度Δ.最佳电流近似算法实现了O（n1/2−·（Δ·logn））-近似，对于一个小的固定常数ε，而最佳的负结果是APX-硬度，在我们对这个基本问题的理解中留下了很大的差距。本文设计了一个随机化的O（2 O（（logn）7/8loglogn）·（Δ））-近似最小交叉数算法。这是问题的第一个近似算法，它实现了一个子多项式ln近似因子（尽管仅在最大顶点度是次多项式的图中）.为了实现这个近似因子，我们设计了一个新的算法来解决一个密切相关的问题，称为交叉数与旋转系统，其中，对于每个顶点v ∈V（G），循环排序，其中，入射到V的边缘的图像必须进入作为输入的一部分固定的图中的图像。将这个结果与[Chuzhoy，Mahabadi，Tan '20]的最新约化结合起来，立即产生了最小交叉数的改进近似算法。
We consider the classical Minimum Crossing Number problem: given ann-vertex graphG, compute a drawing ofGin the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree inG. The best current approximation algorithm achieves anO(n1/2−· (Δ·logn))-approximation, for a small fixed constant є, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomizedO(2O((logn)7/8loglogn)·(Δ))-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial innapproximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial inn).In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertexv∈V(G), the circular ordering, in which the images of the edges incident tovmust enter the image ofvin the drawing is fixed as part of input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan ’20] immediately yields the improved approximation algorithm for Minimum Crossing Number.