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 »