# Colloquium by Michał Włodarczyk (Eindhoven): Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems

Consider 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 *H*. I will cover the case where graphs in *H* have treewidth bounded by *t*, and give a general framework to obtain approximation algorithms basing on two ingredients:

1) approximation algorithms for the *k*-Subset Separator problem,

2) FPT algorithms parameterized by the solution size.

For the vertex deletion setting, this new framework combined with the current best result for *k*-Subset Vertex Separator, improves approximation ratios for basic problems such as *k*-Treewidth Vertex Deletion and Planar *F* Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization.

I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the *H* Vertex Deletion algorithm and explain the differences between deleting vertices or edges.

### Time & Location

Jan 27, 2020 | 05:00 PM s.t.

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)

www.mi.fu-berlin.de/en/fb/contact/location.html