Kernelization using structural parameters on sparse graph classes
作者：
Highlights：
• Meta-theorems for linear kernels have been the subject of intensive research.
• We follow the line toward even larger graph classes using stronger parametrization.
• FII problems have linear kernels on graphs of bounded expansion, parameterized by the size of a treedepth-modulator.
• For nowhere dense classes, this yields almost-linear kernels.
• FII is required only on graphs of bounded treedepth.
摘要
•Meta-theorems for linear kernels have been the subject of intensive research.•We follow the line toward even larger graph classes using stronger parametrization.•FII problems have linear kernels on graphs of bounded expansion, parameterized by the size of a treedepth-modulator.•For nowhere dense classes, this yields almost-linear kernels.•FII is required only on graphs of bounded treedepth.
论文关键词：Parameterized complexity,Kernelization,Nowhere dense graphs,Finite integer index,Treedepth
论文评审过程：Received 9 April 2015, Revised 22 May 2016, Accepted 9 September 2016, Available online 8 October 2016, Version of Record 14 November 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.09.002
