Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion

In the F-minor-free deletion problem we are given an undirected graph.. and the goal is to find a minimum vertex set that intersects all minor models of graphs from the family F. This captures numerous important problems including VERTEX COVER, FEEDBACK VERTEX SET, TREEWIDTH-eta MODULATOR, and VERTEX PLANARIZATION. In the latter one, we ask for a minimum vertex set whose removal makes the graph planar. This is a special case of F-MINOR-FREE DELETION for the family F = {K-5, K-3,K-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]. A polynomial kernelization is a polynomial-time algorithm that, given a graph G and integer k, outputs a graph G' on poly (k) vertices and integer k', so that OPT(G) <= k if and only if OPT(G') <= k' The Vertex PLANARIZATION problem is arguably the simplest setting for which F does not contain a planar graph and the existence of a constantfactor 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 alpha-approximate kernelization, for some constant alpha > 1, based on the framework of lossy kernelization [Lokshtanov, Panolan, Ramanujan, and Saurabh, STOC'17]. Simply speaking, when given a graph.. and integer k, we show how to compute a graph G' on poly (k) vertices so that any beta beta-approximate solution to G' can be lifted to an (alpha . beta)-approximate solution to G, as long as OPT(G) <= k/alpha.beta. 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(epsilon))-approximation algorithm, for any epsilon > 0, and a quasi-polynomial-time (log n)(O(1)) -approximation algorithm, where n is the input size, both randomized [Kawarabayashi and Sidiropoulos, FOCS'17]. By pipelining these algorithms with our approximate kernelization, we improve the approximation factors to respectively O(OPT epsilon) and (log OPT)(O(1)).

Automated summary

The article covers the problem of finding the minimum vertex set in F-minor-free deletion, introduces the Vertex Planarization problem and its solution methods, and presents an algorithm with polynomial alpha-approximate kernelization. It also discusses the approximation algorithms for Vertex Planarization, improving the factors of approximation.