论文标题
密集图属的有效多项式时间近似方案
Efficient polynomial-time approximation scheme for the genus of dense graphs
论文作者
论文摘要
本文的主要结果提供了一个有效的多项式近似方案（EPTA），用于近似密集图的属（和不可取向属）。我们的意思是，对于某些固定的$α> 0 $，我们的意思是$ | e（g）| \geα| v（g）|^2 $。虽然对于这类图表，恒定因子近似是微不足道的，但任意接近1个因子的近似值需要复杂的算法和复杂的数学合理性。 More precisely, we provide an algorithm that for a given (dense) graph $G$ of order $n$ and given $\varepsilon>0$, returns an integer $g$ such that $G$ has an embedding into a surface of genus $g$, and this is $\varepsilon$-close to a minimum genus embedding in the sense that the minimum genus $ \ mathsf {g}（g）$ g $满足：$ \ mathsf {g}（g）（g）\ le g \ le（1+ \ varepsilon）\ Mathsf {g}（g）$。算法的运行时间为$ O（f（\ varepsilon）\，n^2）$，其中$ f（\ cdot）$是一个明确的函数。接下来，我们将此算法扩展到输出一个属为$ g $的嵌入（旋转系统）。该第二个算法是有效的多项式随机近似方案（EPRA），并在时间$ o（f_1（\ varepsilon）\，n^2）$中运行。
The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that $|E(G)|\ge α|V(G)|^2$ for some fixed $α>0$. While a constant factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph $G$ of order $n$ and given $\varepsilon>0$, returns an integer $g$ such that $G$ has an embedding into a surface of genus $g$, and this is $\varepsilon$-close to a minimum genus embedding in the sense that the minimum genus $\mathsf{g}(G)$ of $G$ satisfies: $\mathsf{g}(G)\le g\le (1+\varepsilon)\mathsf{g}(G)$. The running time of the algorithm is $O(f(\varepsilon)\,n^2)$, where $f(\cdot)$ is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is $g$. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time $O(f_1(\varepsilon)\,n^2)$.
