Major open problems on polynomial kernel (non) existence

Question

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 "underline its hardness".

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)

Answer 1

Currently, I would say the 3 major open cases are:

1. Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution
2. Planar Vertex Deletion (make a graph planar by deleting at most k vertices)
3. 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 .

Answer 2

A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2).

Several of the problems mentioned already remain open:

• Directed Feedback Vertex Set and Planar Vertex Deletion parameterized by the number $k$ of vertex deletions as mentioned by Bart remain open.
• The Interval Completion problem mentioned by Yixin remains open.

One further, by now prominent, open problem is whether Claw-Free Deletion / Editing (decide whether we can make an undirected graph claw-free by at most $k$ edge deletions / modifications) parameterized by the solution size has a polynomial kernel.