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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181112-C-Fluschnik.html
END:VEVENT
END:VCALENDAR