Losing Treewidth In The Presence Of Weights

In the Weighted Treewidth-η Deletion problem we are given a node-weighted graph G and we look for a vertex subset X of minimum weight such that the treewidth of G -X is at most η. We show that Weighted Treewidth-η Deletion admits a randomized polynomialtime constant-factor approximation algorithm for every fixed η. Our algorithm also works for the more general Weighted Planar F-M-Deletion problem.

This work extends the results for unweighted graphs by [Fomin, Lokshtanov, Misra, Saurabh; FOCS '12] and answers a question posed by [Agrawal, Lokshtanov, Misra, Saurabh, Zehavi; APPROX/RANDOM '18] and [Kim, Lee, Thilikos; APPROX/RANDOM '21]. The presented algorithm is based on a novel technique of random sampling of so-called protrusions.