Losing Treewidth by Separating Subsets

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\S belongs to some class ℋ. We consider the case where graphs in ℋ 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 -S ubset V ertex S eparator and k -S ubset E dge S eparator, respectively. For the vertex deletion setting, our framework combined with the current best result for k -S ubset V ertex S eparator, improves approximation ratios for basic problems such as k -T reewidth V ertex D eletion and P lanar -ℱ V ertex D eletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. For the edge deletion setting, we give improved approximation algorithms for k -S ubset E dge S eparator combining ideas from LP relaxations and important separators. We present their applications in bounded-degree graphs, and also give an APX-hardness result for the edge deletion problems.

Authors

• Anupam Gupta 0001
• Euiwoong Lee
• Jason Li 0006
• Pasin Manurangsi
• Michal Wlodarczyk 0001

Keywords

No keywords are indexed for this paper.