Major open problems on polynomial kernel (non) existence We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-existence of a polynomial kernel under reasonable complexity-theoretic assumptions). So we are searching for major open problems that could be used in a parameter-preserving reduction to &quot;underline its hardness&quot;.

What are major parameterized NP-complete problems for which it is unknown if they have a polynomial kernel ? Is there a survey/technical report on the subject?

An example could be ODD CYCLE TRANSVERSAL (OCT), the task of making an undirected graph bipartite by deleting as few vertices as possible, parameterized by the number of allowed vertex deletions (though Stefan Kratsch and Magnus Wahlström recently showed a randomized polynomial kernel for OCT)
Currently, I would say the 3 major open cases are:


Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution
Planar Vertex Deletion (make a graph planar by deleting at most k vertices)
Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ensure all the terminals end up in a different connected component)


For all of these, the relevant parameter is the size of the solution. You can have a look at the open problem list from the 2013 Workshop on Kernelization ( http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf ) for others. Pointers to other (but older) open problem lists in parameterized complexity can be found here: http://fpt.wikidot.com/open-problems .