Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

Roohani Sharma, Michał Włodarczyk

Let F be a finite family of graphs. In the F-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no…