STOC2022
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
Bart M. P. Jansen, Michal Wlodarczyk
被引用 3 次
摘要
In the F-minor-free deletion problem we are given an undirected graph G 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-η 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 = K5, K3,3.