Kernel bounds for structural parameterizations of pathwidth

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

17 Citaten (Scopus)
25 Downloads (Pure)


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 is in 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.
Originele taal-2Engels
StatusGepubliceerd - 20 jul 2012
Extern gepubliceerdJa

Bibliografische nota

This paper contains the proofs omitted from the extended abstract published in the proceedings of Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012


Duik in de onderzoeksthema's van 'Kernel bounds for structural parameterizations of pathwidth'. Samen vormen ze een unieke vingerafdruk.

Citeer dit