论文标题
有损平面化：平面顶点缺失的恒定因子近似内核化
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
论文作者
论文摘要
在无F-Minor的删除问题中，我们希望在给定图中找到一个最小顶点，该图形与家族F的所有次要图形相交。顶点平面化问题是f = {k_5，k_5，k__ {3,3,3}} family F = {k_5，k_5，k_5，k_5，k_5}}的特殊情况。每当Family F包含至少一个平面图时，就知道无F-Minor的缺失可以接收恒定的因子近似算法和多项式内核[Fomin，Lokshtanov，Misra和Saurabh，focs'12]。顶点平面化问题可以说是F的最简单设置，F f含有平面图，并且存在恒定因子近似或多项式核心化仍然是一个主要的开放问题。 在这项工作中，我们表明顶点平面化接受了两种方法的组合算法。也就是说，我们提出了一个多项式的A-值，对于某些常数A> 1，基于有损核的框架[Lokshtanov，Panolan，Ramanujan和Saurabh，Stoc'17]。简而言之，当给定图G和整数K时，我们显示了如何在poly（k）顶点上计算图G'，以便可以将任何B-抗浓度的解决方案提升到A*B*opt（g）<= k的（a*b） - 对g的（a*b） - 适应性解决方案。为了实现这一目标，我们开发了一个平面图的稀疏框架，该框架大约保留了给定终端集合的子集之间的所有分离器和近分隔符。 我们的结果对顶点平面化的最新近似算法有所改善。对于任何EPS> 0，该问题接受多项式时O（n^eps）-Approximation算法，并且准多种元素时间（log n）^o（1）近似算法都随机[kawarabayashi and Sidiropoulos，focs'17]。通过使用我们的近似内核来管道这些算法，我们将近似因子分别提高到O（opt^eps）和（log opt）^o（1）。
In the F-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family F. The Vertex planarization problem is a special case of F-minor-free deletion for the family F = {K_5, K_{3,3}}. Whenever the family F contains at least one planar graph, then F-minor-free deletion is known to admit a constant-factor approximation algorithm and a polynomial kernelization [Fomin, Lokshtanov, Misra, and Saurabh, FOCS'12]. The Vertex planarization problem is arguably the simplest setting for which F does not contain a planar graph and the existence of a constant-factor approximation or a polynomial kernelization remains a major open problem. In this work we show that Vertex planarization admits an algorithm which is a combination of both approaches. Namely, we present a polynomial A-approximate kernelization, for some constant A > 1, based on the framework of lossy kernelization [Lokshtanov, Panolan, Ramanujan, and Saurabh, STOC'17]. Simply speaking, when given a graph G and integer k, we show how to compute a graph G' on poly(k) vertices so that any B-approximate solution to G' can be lifted to an (A*B)-approximate solution to G, as long as A*B*OPT(G) <= k. In order to achieve this, we develop a framework for sparsification of planar graphs which approximately preserves all separators and near-separators between subsets of the given terminal set. Our result yields an improvement over the state-of-art approximation algorithms for Vertex planarization. The problem admits a polynomial-time O(n^eps)-approximation algorithm, for any eps > 0, and a quasi-polynomial-time (log n)^O(1) approximation algorithm, both randomized [Kawarabayashi and Sidiropoulos, FOCS'17]. By pipelining these algorithms with our approximate kernelization, we improve the approximation factors to respectively O(OPT^eps) and (log OPT)^O(1).
