Kernelization using structural parameters on sparse graph classes
详细信息 查看全文
- 作者：Jakub Gajarský ; a ; gajarsky@fi.muni.cz" class="auth_mail" title="E-mail the corresponding author ; Petr Hliněný ; a ; hlineny@fi.muni.cz" class="auth_mail" title="E-mail the corresponding author ; Jan Obdržá ; leka ; obdrzalek@fi.muni.cz" class="auth_mail" title="E-mail the corresponding author ; Sebastian Ordyniaka ; sordyniak@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Felix Reidlb ; reidl@cs.rwth-aachen.de" class="auth_mail" title="E-mail the corresponding author ; Peter Rossmanithb ; rossmani@cs.rwth-aachen.de" class="auth_mail" title="E-mail the corresponding author ; Fernando Sá ; nchez Villaamilb ; fernando.sanchez@cs.rwth-aachen.de" class="auth_mail" title="E-mail the corresponding author ; Somnath Sikdarb ; sikdar@cs.rwth-aachen.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Parameterized complexity ; Kernelization ; Nowhere dense graphs ; Finite integer index ; Treedepth
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：219-242
- 全文大小：765 K
文摘
- •
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.