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

作者：

Highlights：

• 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 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.

论文关键词：Kernelization complexity,Parameterization by vertex cover

论文评审过程：Received 12 November 2012, Revised 30 August 2013, Accepted 23 September 2013, Available online 30 September 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.09.004