A better kernel for treewidth-t modulator

Marek Cygan, Lukasz Kowalik,Marcin Pilipczuk,Somnath Sikdar, Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak,Felix Reidl,Peter Rossmanith, Fernando Sanchez,Daniel Lokshtanov, Fedor Fomin, Jianer Chen, Henning Fernau, Iyad A. Kanj

semanticscholar(2013)

引用 0|浏览2
暂无评分
摘要
Treedepth-d modulator as a parameter Somnath Sikdar The recent kernelization algorithms in very general sparse graph classes such as graphs of bounded expansion use the structural parameter of a constant-treedepth modulator [1]. The parameter seems natural in these graph classes, but we have not yet investigated its full power also in general graphs. What natural problems admit a polynomial kernel with respect to this parameter in general graphs? Are there many examples of natural problem that, under this parameterization, admit a polynomial kernel in sparse graph classes, but not in general graphs?
更多
查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要