2019-08-01 Euiwoong Lee (이의웅), Losing treewidth by separating subsets
Автор: IBS Discrete Mathematics Group
Загружено: 2019-07-31
Просмотров: 199
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
https://cims.nyu.edu/~euiwoong/
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.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
