BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Kernelization is a key concept in fixed-parameter algorithmics
  for polynomial-time preprocessing of NP-hard problems. Herein one seeks to
  preprocess any instance of a parameterized problem with parameter k to an 
 “equivalent” instance (the so-called (problem) kernel) with size upper-boun
 ded by some function (preferably by some polynomial) in k. Ten years ago\, 
 with the development of the so-called composition technique\, first NP-hard
  parameterized problems were proven to presumably admit no polynomial-size 
 problem kernel. Since then the line of Research concerning "limits of kerne
 lization" received a lot of attention. We contribute to this line and prese
 nt a new technique exploiting triangle-based fractal structures (so called 
 T-fractals) for extending the range of applicability of compositions. Our t
 echnique makes it possible to prove new no-polynomial-kernel results for a 
 number of graph problems dealing with some sort of cuts\, hereby answering 
 an open question stated in 2009. Our T-fractals---due to their fractal stru
 cture---admit easy-to-prove useful properties exploitable for constructing 
 compositions. They also apply for planar as well as directed variants of th
 e basic problems and also apply to both edge and vertex-deletion problems. 
 This is joint work with Danny Hermelin\, André Nichterlein\, and Rolf Niede
 rmeier. (Journal version appeared in SIAM Journal on Discrete Mathematics 2
 018.) 
DTSTAMP:20181106T161900
DTSTART:20181112T160000
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:Till Fluschnik (Technische Universität Berlin): Fractals for Kernel
 ization Lower Bounds
UID:94443164@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20181112-C-Flu
 schnik.html
END:VEVENT
END:VCALENDAR