Answers are grounded in this paper and cite their sources.
In the [Formula: see text]-minor-free deletion problem we are given an undirected graph [Formula: see text] and the goal is to find a minimum vertex set that intersects all minor models of graphs from the family [Formula: see text]. This captures numerous important problems including Vertex cover, Feedback vertex set, Treewidth-[Formula: see text] 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 [Formula: see text]-minor-free deletion for the family [Formula: see text]. Whenever the family [Formula: see text] contains at least one planar graph, then [Formula: see text]-minor-free deletion is known to admit a constant-factor approximation algorithm and a polynomial kernelization [F. Fomin et al., Proceedings of the 53 rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, pp. 470–479]. A polynomial kernelization is a polynomial-time algorithm that, given a graph [Formula: see text] and integer [Formula: see text], outputs a graph [Formula: see text] on [Formula: see text] vertices and integer [Formula: see text], so that [Formula: see text] if and only if [Formula: see text]. The Vertex planarization problem is arguably the simplest setting for which [Formula: see text] 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 [Formula: see text]-approximate kernelization, for some constant [Formula: see text], based on the framework of lossy kernelization [D. Lokshtanov et al., Proceedings of the 49 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 224–237]. Simply speaking, when given a graph [Formula: see text] and integer [Formula: see text], we show how to compute a graph [Formula: see text] on [Formula: see text] vertices so that any [Formula: see text]-approximate solution to [Formula: see text] can be lifted to an [Formula: see text]-approximate solution to [Formula: see text], as long as [Formula: see text]. In order to achieve this, we develop a toolkit 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-the-art approximation algorithms for Vertex planarization. The problem admits a polynomial-time [Formula: see text]-approximation algorithm, for any [Formula: see text], and a quasi-polynomial-time [Formula: see text]-approximation algorithm, where [Formula: see text] is the input size, both randomized [K. Kawarabayashi and A. Sidiropoulos, Proceedings of the 51 st Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2019, pp. 164–175]. By pipelining these algorithms with our approximate kernelization, we improve the approximation factors to respectively [Formula: see text] and [Formula: see text].
No takes yet. Share an insight, caveat, or question.
Jansen et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: