@inbook{d605a220aad94ea78ab9a8394d06391b,
title = "Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds",
abstract = "On the occasion of Hans Bodlaender{\textquoteright}s 60th birthday, I give a personal account of our history and work together on the technique of cross-composition for kernelization lower bounds. I present several simple new proofs for polynomial kernelization lower bounds using cross-composition, interlaced with personal anecdotes about my time as Hans{\textquoteright} PhD student at Utrecht University. Concretely, I will prove that Vertex Cover, Feedback Vertex Set, and the H-Factor problem for every graph H that has a connected component of at least three vertices, do not admit kernels of (formula presented) bits when parameterized by the number of vertices n for any (formula presented), unless (formula presented). These lower bounds are obtained by elementary gadget constructions, in particular avoiding the use of the Packing Lemma by Dell and van Melkebeek.",
keywords = "Cross-composition, Graph problems, Kernelization lower bounds",
author = "Jansen, {Bart M.P.}",
year = "2020",
month = apr,
day = "21",
doi = "10.1007/978-3-030-42071-0_8",
language = "English",
isbn = "978-3-030-42070-3",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "89--111",
editor = "Fomin, {Fedor V.} and Stefan Kratsch and {van Leeuwen}, {Erik Jan}",
booktitle = "Treewidth, Kernels, and Algorithms",
address = "Germany",
}