Fractals for Kernelization Lower Bounds
VCLA hosted a talk by Danny Hermelin on March 6, 2017
|DATE:||Monday, March 6, 2017|
|VENUE:||Seminarraum von Neumann (Favoritenstrasse 11)|
In this talk I will present a construction that can be used for excluding polynomial kernels for a few parameterized problems of a specific nature. The construction has fractal-like properties, hence the title of the talk. After describing the main ideas behind the construction, I will briefly explain how it can be applied to the Length Bound s,t-Cut problem, resolving an open problem posed by Golovach and Thilikos. The talk will assume only very basic knowledge of parameterized complexity.