BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A graph class is tame if it admits a polynomial bound on the n
 umber of minimal separators\, and feral if it contains infinitely many grap
 hs with exponential number of minimal separators. The former entails the ex
 istence of polynomial-time algorithms for Maximum Weight Independent Set\, 
 Feedback Vertex Set\, and many other problems\, when restricted to an input
  graph from a tame class\, by a result of Fomin\, Todinca\, and Villanger [
 SIAM J. Comput. 2015].  In the talk\, we show a full dichotomy of hereditar
 y graph classes defined by a finite set of forbidden induced subgraphs into
  tame and feral. To obtain the full dichotomy\, we confirm a conjecture of 
 Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class
  C there exists a constant k such that no member of C contains a k-creature
  or a k-skinny-ladder as an induced minor\, then there exists a polynomial 
 p such that every graph G from C contains at most p(|V(G)|) minimal separat
 ors.  Joint work with Jakub Gajarský\, Lars Jafke\, Paloma T. Lima\, Marcin
  Pilipczuk\, Paweł Rzążewski\, and Uéverton S. Souza.   
DTSTAMP:20220427T003200
DTSTART:20220502T160000
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Humbold
 t-Kabinett (between House 3&4 / 1st Floor [British Reading])\n Johann von N
 eumann-Haus\n Rudower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Jana Novotna (University of Warsaw): Taming Creatures
UID:107920273@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20220502-C-Nov
 otna.html
END:VEVENT
END:VCALENDAR