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

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

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

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)