2019-08-01 Euiwoong Lee (이의웅), Losing treewidth by separating subsets

IBS Discrete Mathematics Group
IBS Summer Research Program on Algorithms and Complexity in Discrete Structures
Euiwoong Lee (이의웅), Losing treewidth by separating subsets
August 01 2019, Thursday @ 10:00 AM ~ 11:00 AM
Room B232, IBS (기초과학연구원)
Speaker
Euiwoong Lee (이의웅)
NYU, USA
cims.nyu.edu/~...
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 of graphs $H$. When graphs in H have treewidth bounded by $t$, we construct a framework for both vertex and edge deletion versions where approximation algorithms for these problems can be obtained from approximation algorithms for natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator.
For the vertex deletion, our framework, combined with the previous best result for $k$-Subset Vertex Separator, yields improved approximation ratios for fundamental problems such as $k$-Treewidth Vertex Deletion and Planar-$F$ Vertex Deletion. For the edge deletion, we give improved approximation algorithms for $k$-Subset Edge Separator and their applications to various problems in bounded-degree graphs.
Joint work with Anupam Gupta, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk.