Losing Treewidth by Separating Subsets

Understand

We study the problem of deleting the smallest set $S$ of vertices (resp.

• edges) from a given graph $G$ such that the induced subgraph (resp.
• subgraph) $G \setminus S$ belongs to some class $\mathcal{H}$.
• We consider the case where graphs in $\mathcal{H}$ have treewidth bounded by $t$, and give a general framework to obtain approximation algorithms for both vertex and edge-deletion settings from approximation algorithms for certain natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator, respectively.