Polylogarithmic Approximation for Minimum Planarization (Almost)
Polylogarithmic Approximation for Minimum Planarization (Almost)
复制标题
最小平面化的多对数近似（几乎）
DOI：
10.1109/focs.2017.77
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;Anastasios Sidiropoulos
In the minimum planarization} problem, given some n-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in topological graph theory. We present a \log^{O(1)} n-approximation algorithm for this problem on general graphs with running time n^{O(\log n/\log\log n)}. We also obtain a O(n^≥)-approximation with running time n^{O(1/≥)} for any arbitrarily small constant ≥ 0. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a n^{Ω(1)}-approximation \cite{chekuri2013approximation}.As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Specifically, we obtain O(n^{1/2+≥})-approximation and n^{1/2} \log^{O(1)} n-approximation algorithms in time n^{O(1/≥)} and n^{O(\log n/\log\log n)} respectively. The previously best-known result was a polynomial-time n^{9/10}\log^{O(1)} n-approximation algorithm \cite{DBLP:conf/stoc/Chuzhoy11}.Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.
In the minimum planarization} problem, given some n-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in topological graph theory. We present a \log^{O(1)} n-approximation algorithm for this problem on general graphs with running time n^{O(\log n/\log\log n)}. We also obtain a O(n^≥)-approximation with running time n^{O(1/≥)} for any arbitrarily small constant ≥ 0. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a n^{Ω(1)}-approximation \cite{chekuri2013approximation}.As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Specifically, we obtain O(n^{1/2+≥})-approximation and n^{1/2} \log^{O(1)} n-approximation algorithms in time n^{O(1/≥)} and n^{O(\log n/\log\log n)} respectively. The previously best-known result was a polynomial-time n^{9/10}\log^{O(1)} n-approximation algorithm \cite{DBLP:conf/stoc/Chuzhoy11}.Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.
交叉数的更紧密的基于插入的近似
影响因子：
1
作者：
M. Chimani;P. Hlinĕný
通讯作者：
P. Hlinĕný