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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20200127-C-Wlo
 darczyk.html
END:VEVENT
END:VCALENDAR