Haifa University - Dept. of CS Theory Seminar

Web page: http://cs.haifa.ac.il/~ronen/courses/TheorySeminar2008/theory_sem.html

Speaker : Danny Hermelin, CRI.

Title: "On problems without polynomial kernels".

Date: Thursday, Mar. 6.

Place: Haifa U. Education Building, room 570.

Time: 12:15 - 13:30

Abstract:

Kernelization is a strong and widely-applied technique in the design of fixed-parameter algorithms. In a nutshell, a kernelization algorithm is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernelization algorithm is called a polynomial kernel if the size and parameter of the output are polynomially-bounded by the parameter of the input. In this talk, we give evidence that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. P vs. NP), and evolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which might be of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine which allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. We also show that a polynomial kernel for parameterized problems fulfilling a slightly different criterion implies a distillation algorithm for all coNP-complete problems.

Joint work with M. R. Fellows, J. Flum, M. Müller, and F. Rosamond.