BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Consider the problem of deleting the smallest set S of verti
ces (resp. edges) from a given graph G such that the induced subgraph (re
sp. subgraph) G \ S belongs to some class H . I will cover the case wher
e graphs in H have treewidth bounded by t \, and give a general framewor
k to obtain approximation algorithms basing on two ingredients: 1) approxim
ation algorithms for the k -Subset Separator problem\, 2) FPT algorithms p
arameterized 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 -Tr
eewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are
simpler than previous works and give the first deterministic and uniform ap
proximation algorithms under the natural parameterization. I will talk abou
t what it means for several important graph classes and how the bounded tre
ewidth 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.
DTSTAMP:20200120T075400
DTSTART:20200127T170000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Michał Włodarczyk (Eindhoven): Losing treewidth by separating subse
ts: on approximation of vertex/edge deletion problems
UID:104961331@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200127-C-Wlodarczyk.html
END:VEVENT
END:VCALENDAR