Practical FPT and Foundations of Kernelization
by
Rod Downey
Victoria University of Wellington
Coauthors: Hans Bodlaender, Dannay Hermelin (Utrecht), Mike Fellows (Newcastle Australia)

An approach towards practical tractability for combinatorial problems was pioneered by the speaker and Mike Fellows. It involves looking at fixing some parameter and examining the resulting problem. It has emerged that almost all problems for which this approach works in practice use a technique called kernelization which involves pre-processing to shrink the problem to one whose size depends only on the parameter. We look at the foundations of this subject, giving pseudo-lower bounds on a number of problems. With Fortnow and Santhanam we prove that a wide class of problems, known to be FPT cannot have practical FPT algorithms based on polynomial kernels unless the polynomial time hierarchy collapses to 3 or fewer levels.

Date received: May 1, 2007