Colloquium by Till Fluschnik (Technische Universität Berlin): Fractals for Kernelization Lower Bounds

Nov 12, 2018 | 04:00 PM s.t.

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-bounded 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 kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique 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 structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier. (Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)

Time & Location

Nov 12, 2018 | 04:00 PM s.t.

Humboldt-Universität zu Berlin
Institut für Informatik
Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading])
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)