114 citations · 385 across the 36 of their papers we have counts for
3 papers · 1 filter
Kernel Bounds for Structural Parameterizations of Pathwidth
Hans L. Bodlaender, Bart M. P. 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.…
Kernelization Lower Bounds By Cross-Composition
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to…
Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
Fedor V. Fomin, Bart M. P. Jansen, Michal Pilipczuk
We prove a number of results around kernelization of problems parameterized by the size of a given vertex cover of the input graph. We provide three sets of simple general conditio…