Neeldhara Misra, PhD student from IMSc (Chennai, India), recently visited our department at Chalmers. I had the opportunity to attend her well-given talk about the occasional infeasibility of polynomial kernelization. I liked the ideas she presented so I want to share them; you can read her own summary and download her complete work on her website.

#### Idea of Kernelization

Kernelization is about formalising preprocessing for hard problems and figuring out what can and cannot be achieved. In particular, NP-complete problems are studied; for these problems no *fast* (i.e. with polynomial bound on runtime) algorithms have been found yet. The idea is to crunch down a given instance of size to a size that is manageable by — more or less — naive algorithms while preserving equivalence, that is the reduced instance should have a solution if and only if the original instance has one. The notion of *manageability* is captured by a problem and instance dependent parameter ; we say that we have a polynomial kernel if there is an equivalent problem whose size is bounded by a polynomial in (i.e. independent of ). If is small — which is often the case in practical scenarios — the kernel can be solved reasonably quickly. Of course, the reduction process should then also be fast. Remains to mention that has to be chosen wisely; only knowing at least an upper bound for enables useful kernelizations. Read more »