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.