Fractals for Kernelization Lower Bounds

VCLA hosted a talk by Danny Hermelin

ABSTRACT

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.