Kernel Bounds for Structural Parameterizations of Pathwidth
Kernel Bounds for Structural Parameterizations of Pathwidth
复制标题
路径宽度结构参数化的核界限
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
H. Bodlaender;B. Jansen;Stefan Kratsch
Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters.
Our main result is that, unless NP ⊆ coNP/poly, Pathwidth admits no polynomial kernelization even when parameterized by the vertex deletion distance to a clique, by giving a cross-composition from Cutwidth. The cross-composition works also for Treewidth, improving over previous lower bounds by the present authors. For Pathwidth, our result rules out polynomial kernels with respect to the distance to various classes of polynomial-time solvable inputs, like interval or cluster graphs.
This leads to the question whether there are nontrivial structural parameters for which Pathwidth does admit a polynomial kernelization. To answer this, we give a collection of graph reduction rules that are safe for Pathwidth. We analyze the success of these results and obtain polynomial kernelizations with respect to the following parameters: the size of a vertex cover of the graph, the vertex deletion distance to a graph where each connected component is a star, and the vertex deletion distance to a graph where each connected component has at most c vertices.
