English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Assuming the AND-distillation conjecture, the Pathwidth problem ofdetermining whether a given graph G has pathwidth at most k admits nopolynomial kernelization with respect to k. The present work studies theexistence 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 thevertex deletion distance to a clique, by giving a cross-composition fromCutwidth. The cross-composition works also for Treewidth, improving overprevious lower bounds by the present authors. For Pathwidth, our result rulesout polynomial kernels with respect to the distance to various classes ofpolynomial-time solvable inputs, like interval or cluster graphs. This leads tothe question whether there are nontrivial structural parameters for whichPathwidth does admit a polynomial kernelization. To answer this, we give acollection of graph reduction rules that are safe for Pathwidth. We analyze thesuccess of these results and obtain polynomial kernelizations with respect tothe following parameters: the size of a vertex cover of the graph, the vertexdeletion distance to a graph where each connected component is a star, and thevertex deletion distance to a graph where each connected component has at mostc vertices.

Kernel Bounds for Structural Parameterizations of Pathwidth