June 12, 2018, 10:15 a.m.

Title: Losing Treewidth by Separating Subsets
Authors: Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk
Speaker: Michał Włodarczyk
Time and place: Tuesday, 12th of June 2018, 10:15 am, room 310.


In the H-Vertex Deletion problem we are given a graph G and look for the minimum vertex set X, such that G \ X belongs to the class H. We define H-Edge Deletion similarly. We will focus on approximation algorithms for the case, where the class H consists of graphs with a bounded treewidth. Their crucial building block is based on recent results for the k-Subset Separator problem.

Applying the new tools to problems such as k-Treewidth Deletion or Planar-F-Deletion yields a significant improvement of approximation factor and it also improves running times for several other problems. In contrary to previous works in the area, the new techniques are constructive and give uniform algorithms under the natural parameterization.