Preprocessing subgraph and minor problems: When does a small vertex cover help?

• We study the existence of polynomial kernels for parameterized graph problems.
• The size of a vertex cover of the graph is used as the parameter.
• Three sets of general conditions show when polynomial kernels exist.
• Several kernel size lower bounds explore the limits of tractability.
• A case study is included of minor testing versus induced subgraph testing.

We prove a number of results around kernelization of problems parameterized by the size of a given vertex cover of the input graph. We provide three sets of simple general conditions characterizing problems admitting kernels of polynomial size. Our characterizations not only give generic explanations for the existence of many known polynomial kernels for problems like q-Coloring, Odd Cycle Transversal, Chordal Deletion, η-Transversal, or Long Path, parameterized by the size of a vertex cover, but also imply new polynomial kernels for problems like FF-Minor-Free Deletion, which is to delete at most k   vertices to obtain a graph with no minor from a fixed finite set FF. While our characterization captures many interesting problems, the kernelization complexity landscape of parameterizations by vertex cover is much more involved. We demonstrate this by several results about induced subgraph and minor containment testing.